P17128 [ICPC 2025 Shanghai R] AGI 题解
_ego_
·
·
题解
感谢 wyyinput 提供的 HACK 现已修改。
题意
有 2n 个数，Menji 先手，每回合选一个数 x，把 S 异或上 x 然后删掉这个数。Bot 后手，每回合删一个数但不影响 S。两人轮流，直到数全部删完。如果最终
## 思路
这道题的核心是搞清楚 Menji 的选数对最终结果的影响，以及 Bot 的删数能不能干扰。
先把所有数按数值分组，统计每种数出现的次数。出现偶数次的数，无论 Menji 选不选到它们，最终异或起来都会被抵消掉（因为异或偶数个相同数等于 $0$）。真正决定最终
$S$ 的，**只有那些出现次数为奇数的数**。
我们可以设出现奇数次的数值种类数为 $e$。
- 如果 $e$ 是奇数，那么这些数两两配对后还会剩下一个落单的，最终 $S$ 一定非零，Menji 无论如何都赢不了，Bot 赢。
- 如果 $e$ 是偶数，Menji 可以通过策略保证自己选到的数恰好让异或和为 $0$。Bot 虽然能删数，但删不掉 Menji 已经选过的数，也改变不了奇偶性的格局，所以 Menji 能赢。
::::warning[But]
特殊情况：$n = 1$ 时只有两个数，Menji 只能选一个，Bot 删另一个。如果两个数中有一个是 $0$，Menji 选 $0$，最终 $S = 0$，赢。 否则 $S$ 非零，输。
::::
综上，做法也就简单明了了：**统计每种数的出现次数，数一下有多少种出现次数是奇数，然后按上面的规则判断。**
## 代码
```cpp line-number
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int T;cin>>T;
while(T--){
int n;cin>>n;
unordered_map<int,int> cnt;
cnt.reserve(2*n+5);
for(int i=0;i<2*n;i++){
int x;cin>>x;
cnt[x]++;
}
int odd=0,s=0;
int o1=-1,o2=-1;
for(auto &p:cnt){
int x=p.first,c=p.second;
if(c&1){
odd++;
if(o1==-1) o1=x;
else o2=x;
}
int h=c/2;
if(h&1) s ^= x;
}
if(odd>2){cout<<"Bot\n";continue;}
if(odd==0){
if(s==0) cout<<"Menji\n";
else cout<<"Bot\n";
continue;
}
int ok=0;
if(o1==s || o2==s) ok=1;
if(ok) cout<<"Menji\n";
else cout<<"Bot\n";
}
return 0;
}
```
还是很简单的，完结撒花！