[ARC208A] Bitwise OR Game 题解

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

一般的 Nim 游戏就是先手不断让一个数

x

变成另一个数

y

，使得接下来的

n

个数的异或和为

0

，而后手一定要选数使得异或和不为

0

，这样先手必然会取光，后手输。

我们把它带入这道题做一下。我们发现，每一位必然需要留下一个

1

。那么我们把这些

1

扣掉，就又变成了普通的 Nim 游戏。所以，如果按位或和等于异或和，先手必败；否则，先手必胜。证明可以感性参考一般 Nim 游戏的证明。

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

CPP

#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;
}
/*

*/

[ARC208A] Bitwise OR Game 题解

文章操作

相关推荐

评论

[ARC208A] Bitwise OR Game 题解