---
title: Codeforce 1383 B. GameGame 解析(思維、博弈)
description: "Codeforce 1383 B. GameGame 解析(思維、博弈)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 1383 B. GameGame 解析(思維、博弈)">
<!-- toc -->

# Codeforce 1383 B. GameGame 解析(思維、博弈)
今天我們來看看CF1383B
[題目連結](https://codeforces.com/problemset/problem/1383/B)

> **題目**
兩個人在玩遊戲，有一個長度為$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](https://codeforces.com/contest/1383/submission/90386752)