1. 数组价值
米小游有一个长度为 n 的数组，其中第 i 个元素为 ai。现在定义数组的价值是最大的相邻数字的乘积。
例如数组为 [3,5,1,2] ，相邻元素的乘积分别是 35=15,51=5和1*2=2 ，则数组的价值是这些数字中的最大值，即 15。
现在米小游想要任选数组中的某两个相邻的元素进行交换（你必须使用这次交换机会），他想知道最大可以将数组的价值更改为多少？
观察计算相邻和间隔一位乘积最大值即可
int main() {
int n;
cin>>n;
vector<int> nums(n);
for(int i=0;i<n;i++)
cin>>nums[i];
long long res = 0;
for(int i=0;i<n-1;i++){
if(i<n-2) res = max(res,(long long)nums[i]*nums[i+2]);
res = max(res,(long long)nums[i]*nums[i+1]);
}
cout<<res;
return 0;
}
2. 米小游买商品
商店里有 n个商品，分别编号为 1~n ，每个商品都有一个价值 vali和体积 wi，米小游有一个有一个 m 容量的背包，他能够装得下任意多个体积之和不超过 m 的商品。
米小游认为有些东西一起购买会带来灾难，比如可莉的角色立牌和蹦蹦炸弹的小手办，
所以他设定了 k组互斥关系，每组关系给定两个数字 a,b，表示编号为 a 的商品和编号为 b的商品不能同时购买。
米小游希望装下的物品的价值之和最大，请你帮帮他求出最大价值。
暴力回溯搜索，注意撤回选择的时候，不能把另一个互斥关系撤回，所以要采用多重加锁
int main() {
int n,m,k;//商品数量，背包容量，互斥关系
cin>>n>>m>>k;
vector<vector<int>> items(n,vector<int>(2));
vector<vector<int>> relation(k,vector<int>(2));
for(int i=0;i<n;i++)
cin>>items[i][0]>>items[i][1];//体积和价值
unordered_map<int,int> mp;//互斥关系1~n
for(int i=0;i<k;i++){
cin>>relation[i][0]>>relation[i][1];
mp[relation[i][0]-1] = relation[i][1]-1;
mp[relation[i][1]-1] = relation[i][0]-1;
}
//正常是背包动态规划，但由于数据量n很小，以及存在互斥，直接使用暴搜
function<int(int,int,vector<int>&)> dfs = [&](int i,int capacity,vector<int>&h)->int{
if(i==n) return 0;//访问完毕边界
int res = 0;
res = max(res,dfs(i+1,capacity,h));//不选
if(h[i]==0&&items[i][0]<=capacity){//选
h[mp[i]]++;
res = max(res,items[i][1]+dfs(i+1,capacity-items[i][0],h));
h[mp[i]]--;
}
return res;
};
vector<int> memo(n,0);
cout<<dfs(0,m,memo);
return 0;
}
3. 删点
米小游和派蒙在进行一场游戏。游戏在一个基环树（点数与边数相等的无向简单连通图）上进行，
定义图中一个点的度数为与其相连的边数，二人轮流进行以下操作：
选择图中一个度数为 1 的点，删除这个点以及与这个点相连的边。
图中有一个特殊的点 x ，删除了点 x 的玩家即获得胜利。现在，由米小游先进行操作。在双方都采取最优策略的情况下，胜者是谁？
拓扑排序，同时找出规律
也就是位于环上，即度不能为1，找不到，不位于环上，若是第一个，则玩家一胜利，否则看找到前能删除的点个数是奇数还是偶数
int main() {
int T;
cin>>T;
while(T--){
int n,x;
cin>>n>>x;
vector<vector<int>> graph(n+1);
queue<int> q;//入度为1的队列
vector<int> cnt(n+1);//入度的数量
for(int i=0;i<n;i++){
int from,to;
cin>>from>>to;
graph[from].push_back(to);
graph[to].push_back(from);
cnt[from]++;
cnt[to]++;
}
for(int i=1;i<=n;i++)
if(cnt[i]==1) q.push(i);
bool find = false;
bool first = true;
int res = 0;
while(!q.empty()){
int cur = q.front();
q.pop();
if(cur==x){
find = true;
continue;
}
for(auto next:graph[cur]){
if(next==x) first = false;
cnt[next]--;
if(cnt[next]==1) q.push(next);
}
res++;
}
if(find==false) cout<<"Draw";
else{
if(first||res%2==0) cout<<"Xiaoyo";
else cout<<"Pyrmont";
}
}
return 0;
}