取火柴游戲

題目描述

輸入 $k$ 及 $k$ 個整數 $n_1,n_2,?,n_k$，表示有 $k$ 堆火柴棒，第 $i$ 堆火柴棒的根數為
$n_i$；接著便是你和計算機取火柴棒的對弈游戲。取的規則如下：每次可以從一堆中取走若干根火柴，也可以一堆全部取走，但不允許跨堆取，也不允許不取。

誰取走最后一根火柴為勝利者。

例如：$k=2$，$n_1=n_2=2$，A 代表你，P 代表計算機，若決定 A 先取：

• A：$(2,2)\to (1,2)$，即從第一堆中取一根。
• P：$(1,2)\to (1,1)$，即從第二堆中取一根。
• A：$(1,1)\to (1,0)$。
• P：$(1,0)\to (0,0)$。P 勝利。

如果決定 $A$ 后取：

• P：$(2,2)\to (2,0)$。
• A：$(2,0)\to (0,0)$。A 勝利。

又如 $k=3$，$n_1=1$，$n_2=2$，$n_3=3$，$A$ 決定后取：

• P：$(1,2,3)\to (0,2,3)$。
• A：$(0,2,3)\to (0,2,2)$。
• A 已將游戲歸結為 $(2,2)$ 的情況，不管 P 如何取 A 都必勝。

編一個程序，在給出初始狀態之后，判斷是先取必勝還是先取必敗，如果是先取必勝，請輸出第一次該如何取。如果是先取必敗，則輸出 lose。

輸入格式

第一行，一個正整數 $k$。

第二行，$k$ 個整數 $n_1,n_2,?,n_k$。

輸出格式

如果是先取必勝，請在第一行輸出兩個整數 $a,b$，表示第一次從第 $b$ 堆取出 $a$
個。第二行為第一次取火柴后的狀態。如果有多種答案，則輸出 $?b,a?$ 字典序最小的答案（ 即 $b$ 最小的前提下，使
$a$ 最小）。

如果是先取必敗，則輸出 lose。

樣例 #1

樣例輸入 #1

3 3 6 9

樣例輸出 #1

4 3 3 6 5

樣例 #2

樣例輸入 #2

4 15 22 19 10

樣例輸出 #2

lose

提示

數據范圍及約定

對于全部數據，$k\le 500000$，$n_i\le 10^9$。

又是參加學校每日題的一天，熟練的點開了題目的算法標簽，想看看這個題我有沒有一點點涉獵（又是及時放棄的一天（bushi））一看：博弈論。瞬間想起了之前在b站刷到過卻放在收藏夾吃灰，于是決定好好看看而不是直接放棄（

讓我們分析分析這道題。經典的Nim游戲 P2197 【模板】Nim 游戲
首先我們需要認識到，僅有一堆棋子存在時，出現勝負決斷

n=1: 先手全拿，先手必勝。

n=2:有兩種情況，一種可能相同，一種情況一堆比另一堆少（多）

    (m,m) 按照“有一學一，照貓畫貓”法，先手必輸。(m,M)先手先從多的一堆中拿出(M-m)個，此時后手面對(m,m)的局面先手必勝。

術語:正經人稱(m,m)的局面為奇異局勢
n=3:(m,m,M)先手必勝局，先手可以先拿M,之后變成了(m,m,0)的局面，是不是很熟悉~

(a1,a2,a3)的話，舉個例子(1,2,3),先手取完之后可能的局面為(0,2,3),(1,1,3),(1,0,3),(1,2,2),(1,2,1),(1,2,0)都是之前講過的，情況如下：


這些的結果可以總結為：異或均為0

這塊的異或到底是怎么躥出來的，我覺得洛谷題解有一篇說的挺有意思

異或有一個特殊的規律，就是一堆數異或時，若在同一個二進制位上1的個數是偶數，那么這一位異或起來以后是0，否則為1

二進制的話就是可以使用0/1表示所有數字

我們來看上一個游戲，我們將這兩堆的剩余的火柴數轉變成二進制。

發現我們先手取走一個數，就是改變其二進制為上的1的個數（只考慮奇偶性），而后手再去取的話就是將其奇偶性再變回來

然后我們再回去看為什么異或和是0時先手必輸，因為先手拿走了某些火柴時，我們可以根據其拿走火柴的二進制表示，在其他一堆中拿走一些一些數字，使得其異或和重新為0；

怎么搞呢？ 我們可以拿走一些數，也就是減某一個數，使得先手拿完后，（啰嗦警告）

所有堆中的每個二進制上的一的個數的和，我們總可以通過加減一個數，達到在某一個二進制位的1的個數進行加一or減一的效果

使得某一位二進制上的1的個數變為偶數。

從而使得游戲又恢復到了一開始的局面
題解

先手必勝，即先手可以拿走一些火柴，使得后手必敗，而必敗態是火柴堆的異或和為零；那么我們求的，就是先手拿走一些火柴后，新的火柴堆異或和為零的方案。設原異或和為X


當(a2 xor X)<a2時，能取走火柴。

#include <iostream>
#include<algorithm>using namespace std;
int k, n[500100], x;int main()
{cin >> k;for (int i = 1; i <= k; i++){cin >> n[i];x ^= n[i];}if (x == 0) { cout << "lose"; return 0; }for (int i = 1; i <= k; i++){if ((n[i] ^ x) < n[i]){cout << n[i] - (n[i] ^ x) << " " << i << endl;n[i] = n[i] ^ x;break;}}for (int i = 1; i <= k; i++){cout << n[i] << " ";}return 0;
}

這里貼一下感覺比較推薦的有關文章
數學知識——博弈論（巴什博奕、尼姆博奕、威佐夫博奕）思路及例題
題解 P1247 【取火柴游戲】
[學習筆記] （博弈論）Nim游戲和SG函數