黑板上有一些数字,Alice和Bob轮流操作,每次操作可以选择黑板上的两个数(两个数可以相同),然后在黑板上写下这两个数的异或。谁先写出k谁赢。
首先重复的数字是没有用的,进而可以推出除整局游戏的第一步之外,都可以选择保持当前的局面不变.
比如如果一个玩家面对的是一个必输的局面,他就可以选择保持局面不变再将这个局面送给对面。
因为这个性质的存在,所以游戏的发展有如下三种情况。
1、 先手一步获胜。
这就要求存在\(a_i \bigoplus a_j = k\)
2、先手无法一步获胜,并且无论先手选择哪两个,后手都可以获胜。
也就是对于任意的\(i , j\)都存在\(p\),满足\(a_i \bigoplus a_j = a_p \bigoplus k\)
将这个式子的左边两项都异或上k
\[(a_i \bigoplus k)\bigoplus (a_j \bigoplus k) = a_p \bigoplus k \]然后用\(a^`\)来代替\(a\)则有
\[a^`_i \bigoplus a^`_j = a^`_p \]也就是\(a^`\)对于异或操作是封闭的。
也就是等价于,\(a^`\)中不同的数字的个数==2^(线性基的维数)
3、先手不能一步获胜,后手也不满足条件,所以两者就会一直僵持下去,最终平局。
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 1e6+10;
int n , m , k;
int A[N] , B[N] , p[30];
void Solve()
{
int tmp , pos , num;
cin >> n >> k;
for(int i = 1 ; i <= n ; ++i) cin >> A[i] , B[i] = A[i];
sort(B + 1 , B + 1 + n);
m = unique(B + 1 , B + 1 + n) - B - 1;
for(int i = 1 ; i <= n ; ++i)
{
tmp = A[i] ^ k;
pos = lower_bound(B + 1 , B + 1 + m , tmp) - B;
if(pos <= m && B[pos] == tmp) { cout << "Alice" << '\n'; return ; }
}
for(int i = 0 ; i < 30 ; ++i) p[i] = 0;
for(int i = 1 ; i <= n ; ++i)
{
tmp = A[i] ^ k;
for(int j = 29 ; j >= 0 ; --j)
{
if(tmp & (1 << j))
{
if(!p[j]) { p[j] = tmp; break; }
else tmp ^= p[j];
}
}
}
num = 0;
for(int i = 0 ; i < 30 ; ++i) if(p[i]) num++;
if((1 << num) == m)
cout << "Bob" << '\n';
else
cout << "Draw" << '\n';
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T;
cin >> T;
while(T--) Solve();
return 0;
}
标签:include,int,异或,黑板,牛客,Game,bigoplus,校赛,获胜
From: https://www.cnblogs.com/sybs5968QAQ/p/17636834.html