题解：P17128 [ICPC 2025 Shanghai R] AGI

· · 题解

不妨先考虑所有数字都不相同的情况，不难发现这时候后手必胜。因为最后一步是不可控的，当先手选完 n-1 个数时剩下至多一个数能使先手获胜，而后手可以把它取走。

那么我们再考虑存在相同的情况怎么做。对于先手，若两个数相同，都取掉是不劣的。后手不能满足先手的条件，所以在先手取了一个数时后手会相应地取走另一个与它相等的数。这启发我们把相等的数两两配对（多次配多对）。根据策略，先手只能取配好对的一半。

问题变成了有一个初始值 S，先后手在剩下 m 个互不相等的数中选，最后先手取数让 S 变成 0 获胜。我们分类讨论：

  1. 对于 m \ge 4 的情况和上面假设所有数字都不相同是类似的，不难发现先手必败。
  2. 对于 m=2，与上面不同的是先手可以抢占最后一个值。若剩下两个数中有一个 S，则先手把它取了获胜，否则失败。
  3. 对于 m=0，当且仅当 S=0 先手获胜。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int t,n,a[N<<1],pre,s,rst,q[3];
bool chk(){
    sort(a+1,a+2*n+1);
    a[2*n+1]=-1;
    pre=1,s=rst=0;
    for(int i=2;i<=2*n+1;i++){
        if(a[i]!=a[i-1]){
            if((i-pre>>1)&1)s^=a[i-1];
            if((i-pre)&1){
                if(rst<2)q[++rst]=a[i-1];
                else return 0;
            }
            pre=i;
        }
    }
    for(int i=1;i<=rst;i++){
        if(s==q[i])return 1;
    }
    return rst==0&&s==0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=2*n;i++)cin>>a[i];
        cout<<(chk()?"Menji\n":"Bot\n");
    }
    return 0;
}