傳送門
題目：給定長度為n的陣列a，A和B輪流拿走一個數，開始時A和B擁有的v為0，A和B每次拿走一個數時，他的v = v^ ai，A和B都很聰明，問都按照最優的情況考慮，拿完所有數之后A和B的v的大小，
思路：我們可以想到二進制的高低位性質，所以一個人如果有一個最高位二進制為1而另外一個人是0，則前者一定贏，我們可以把所有數的二進制位取下來，我們知如果該二進制位為偶數，說明這個位一定可以變成0；否則如果為奇數，則一定會出現一個人是1，另一個是0的情況，根據列舉一些樣例，可以總結出以下的規律：
（前提：該bit為奇數）
① cnt[bit] % 4 == 1 則前者一定贏，只要前者把這個1拿走
② cnt[bit] % 4 == 3 （*） 如果 （n - cnt[bit]）% 2 == 0（&）,則后者贏，因為后者一定可以讓前者取到（*）多出的1，反之如果為1，則前者把（&）1拿走，讓后者拿（*）多出的1
1 #include<iostream> 2 #include<string> 3 #include<vector> 4 #include<cstdio> 5 6 #define ll long long 7 #define pb push_back 8 9 using namespace std; 10 11 const int N = 1e5; 12 int bit[N]; 13 14 void solve() 15 { 16 int T; 17 cin >> T; 18 while(T--){ 19 int n; 20 cin >> n; 21 22 for(int i = 0; i <= 40; ++i) bit[i] = 0; 23 24 for(int i = 1; i <= n; ++i){ 25 int x, b; 26 cin >> x; 27 b = 0; 28 while(1){ 29 if(!x) break; 30 bit[b++] += (x & 1); 31 x >>= 1; 32 } 33 } 34 35 int inx = -1; 36 for(int i = 40; i >= 0; --i){ 37 if(bit[i] % 2 == 0) continue; 38 inx = i; 39 break; 40 } 41 42 if(inx == -1){ 43 cout << "DRAW" << endl; 44 continue; 45 } 46 47 int a = bit[inx] % 4; 48 int b = (n - a) % 2; 49 50 if(a == 3 && b == 0) cout << "LOSE" << endl; 51 else cout << "WIN" << endl; 52 } 53 54 } 55 56 int main() { 57 58 ios::sync_with_stdio(false); 59 cin.tie(0); 60 cout.tie(0); 61 solve(); 62 //cout << "ok" << endl; 63 return 0; 64 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/3875.html
標籤：其他