Codeforce 1383 B. GameGame 解析(思維、博弈)

今天我們來看看CF1383B
題目連結

題目
兩個人在玩遊戲，有一個長度為$n$的數列$a$，每次每個人選一個數字和目前自己的分數XOR(初始為0分)，最後拿到最多分數的人贏，求誰會贏?

前言

博弈的題目一直不是很會做，這次這題有個我平時可能不會想到的新想法:可以嘗試讓其中一個玩家跟隨另一個玩家做動作，如果被跟隨的那個玩家最後會輸，那麼跟隨的那個玩家就會贏。這是因為我們給出了一個明確的移動方法。

想法

首先要知道一件事:如果一個玩家能夠使得分數有最高位的bit，並且另外一個人沒有，那麼就贏了。這是因為在右邊的bit不管有多少，都比不上最左邊的bit(正式來說:$2^n>\sum\limits_{i=0}^{n-1}2^i\ \forall n\in\mathbb{N}_{\ge1}$)。
那麼我們可以先統計對於bit有幾個元素有這個bit，接著我們從最左邊的bit開始「考慮」:
分為兩種情況:

1. 這個bit有偶數個，那麼由於兩個玩家只有2種拿的方法

   • 偶偶
   • 奇奇

   不管玩家怎麼拿，這個bit最後的狀態都是一樣的，所以我們可以完全不用考慮這個bit。

2. 這個bit有奇數個，也就是玩家要去搶這個bit: 首先另$x=$有這個bit的元素的數量，$y=n-x$也就是剩下的數字的數量(這個bit是$0$)。由於玩家們拿了$4$個$1$等同於沒有改變狀態，因此有以下的分類:

   1. $x\mod 4=1$ and $y\mod 2=0$: 先手先拿一個$1$，接著完全照搬後手的行動。如此易發現先手會贏。
   2. $x\mod 4=1$ and $y\mod 2=1$: 先手先拿一個$1$，接著完全照搬後手的行動，直到後手拿走了最後一個$0$，那麼接著就剩下要拿偶數個$1$，並且是先手先拿。由於是$x\mod 4=1$，所以最後是先手贏。
   3. $x\mod 4=3$ and $y\mod 2=0$: 後手完全照搬先手的行動，最後先手一定會拿到偶數個$1$，所以後手贏。
   4. $x\mod 4=3$ and $y\mod 2=1$: 先手先拿一個$0$，那麼就是3.的情況了，先手贏。

程式碼:

const int _n=1e5+10;  
int t,n,a[_n],cnt[32];  
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);  
  cin>>t;while(t--){  
    cin>>n;rep(i,0,n)cin>>a[i]; memset(cnt,0,sizeof cnt);  
    rep(j,0,30)rep(i,0,n)cnt[j]+=((a[i]&(1<<j))?1:0);  
    per(i,0,30){  
      if(cnt[i]%2==0)continue;  
      int x=cnt[i],y=n-x;  
      if(x%4==3 and y%2==0){cout<<"LOSE\n";goto A;}  
      else {cout<<"WIN\n";goto A;}  
    }cout<<"DRAW\n";  
    A:;  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission