[ARC208A] Bitwise OR Game 题解

linjunye · 2025-10-17 18:03:55 · 题解

我们回想起学过的 Nim 游戏。

一般的 Nim 游戏就是先手不断让一个数 x 变成另一个数 y，使得接下来的 n 个数的异或和为 0，而后手一定要选数使得异或和不为 0，这样先手必然会取光，后手输。

我们把它带入这道题做一下。我们发现，每一位必然需要留下一个 1。那么我们把这些 1 扣掉，就又变成了普通的 Nim 游戏。所以，如果按位或和等于异或和，先手必败；否则，先手必胜。证明可以感性参考一般 Nim 游戏的证明。

代码很短。好像这一场 ARC 前三题都很短？

#include<bits/stdc++.h>
#define int long long
using namespace std;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
const int N=1000010;
int n;
int a[N];
void solve(){
    cin>>n;
    int x=0,y=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        x|=a[i];
        y^=a[i];
    }
    if((x^y)==0)cout<<"Bob\n";//x^y==0 就是 x==y
    else cout<<"Alice\n";
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int Tc=1;
    cin>>Tc;
    while(Tc--)solve();
    return 0;
}
/*

*/