【ybt高效進階6-5-1】【luogu P1247】取火柴遊戲（博弈論）（NIM遊戲）

取火柴遊戲

題目連結：ybt高效進階6-5-1 / luogu P1247

題目大意

給你 k 堆石子，第 i 堆 ni 個。

然後兩個人輪流選一堆石子取走一定數量的石子，但不能不取。

誰沒得取，誰就輸了，問你先手必勝還是後手必勝。

如果是先手必勝，要輸出第一次怎麼取。（如果多種方案，就先取前面堆的石子）

思路

這個就是經典的 NIM 遊戲模型了，首先給出定理：

當且僅當 n 1   x o r   n 2   x o r   . . .   x o r   x k = x ≠ 0 n_1\ xor\ n_2\ xor\ ...\ xor\ x_k=x\neq0 n1​ xor n2​ xor ... xor xk​=x​=0 的時候，先手必勝。

這裡給一下證明：

首先，如果所有東西都沒了，那就是先手必敗（因為已經沒有東西了），那顯然異或得到的是 0 0 0。

那接着考慮任意一個局面，分為兩種：異或得到的是 0 0 0 或者不是 0 0 0。

首先我們看不是 0 0 0 的情況，那 n 1   x o r   n 2   x o r   . . .   x o r   x k = x ≠ 0 n_1\ xor\ n_2\ xor\ ...\ xor\ x_k=x\neq0 n1​ xor n2​ xor ... xor xk​=x​=0，設 x x x 的二進制表示下最高位的 1 1 1 是第 k k k 位，那至少有一堆石子 n i n_i ni​ 它的第 k k k 位是 1 1 1。那也就是說，對于這一堆石子，會有： n i   x o r   x < n i n_i\ xor\ x<n_i ni​ xor x<ni​。

那我們可以從 n i n_i ni​ 中取若幹個（ n i − ( n i   x o r   x ) n_i-(n_i\ xor\ x) ni​−(ni​ xor x)）石子，使得它變成 n i   x o r   x n_i\ xor\ x ni​ xor x，這樣子就變成了異或得到的是 0 0 0 的局面。

那如果是 0 0 0，就無論你怎麼取石子，得到的最終都不是 0 0 0。（如果你要最終得到的是 0 0 0 就要不取但是不能不取）

那就證明了結論。

然後至于找方案你就直接從左往右找第一個滿足 n i   x o r   x < n i n_i\ xor\ x<n_i ni​ xor x<ni​ 的，然後就按着那個減的方法搞。

代碼

#include<cstdio>

using namespace std;

int k, n[500001], ans;

int main() {
	scanf("%d", &k);
	for (int i = 1; i <= k; i++) {
		scanf("%d", &n[i]);
		ans ^= n[i];
	}
	
//	if (!ans) printf("Lose");//一本通就是這個
	if (!ans) printf("lose");//luogu就是這個
		else {
			for (int i = 1; i <= k; i++)
				if ((n[i] ^ ans) < n[i]) {
					printf("%d %d\n", n[i] - (n[i] ^ ans), i);
					n[i] -= (n[i] - (n[i] ^ ans));
					break;
				}
			for (int i = 1; i <= k; i++)
				printf("%d ", n[i]);
		}
	
	return 0;
}