【题目来源】 https://www.luogu.com.cn/problem/P1247 【题目描述】 输入 k 及 k 个整数 n1, n2, …, nk，表示有 k 堆火柴棒，第 i 堆火柴棒的根数为 ni。接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。 谁取走最后一根火柴为胜利者。 例如：k=2，n1=n2=2，A 代表你，P 代表计算机，若决定 A 先取： • A：(2,2)→(1,2)，即从第一堆中取一根。 • P：(1,2)→(1,1)，即从第二堆中取一根。 • A：(1,1)→(1,0)。 • P：(1,0)→(0,0)。P 胜利。 如果决定 A 后取： • P：(2,2)→(2,0)。 • A：(2,0)→(0,0)。A 胜利。 又如 k=3，n1=1，n2=2，n3=3，A决定后取： • P：(1,2,3)→(0,2,3)。 • A：(0,2,3)→(0,2,2)。 • A 已将游戏归结为 (2,2) 的情况，不管 P 如何取 A 都必胜。 编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输出第一次该如何取。如果是先取必败，则输出 lose。 【输入格式】 第一行，一个正整数 k。 第二行，k 个整数 n1，n2,，nk。 【输出格式】 如果是先取必胜，请在第一行输出两个整数 a，b，表示第一次从第 b 堆取出 a 个。第二行为第一次取火柴后的状态。如果有多种答案，则输出 <b, a> 字典序最小的答案（即 b 最小的前提下，使 a 最小）。 如果是先取必败，则输出 lose。 【输入样例一】 3 3 6 9 【输出样例一】 4 3 3 6 5 【输入样例二】 4 15 22 19 10 【输出样例二】 lose 【数据范围】 对于全部数据，k≤500000，ni≤10^9。 【算法分析】 ● 经典 Nim 博弈定理：对于任意的 {a1, a2, a3, …, an}，若 S=a1⊕a2⊕a3⊕⋯⊕an 的值不等于 0，先手必胜，记为 N-position（先手必胜态）。若 S=a1⊕a2⊕a3⊕⋯⊕an 的值等于 0，先手必败，记为 P-position（先手必败态）。 ● 根据经典 Nim 博弈定理，若要让对手进入必败态（P-position），需通过一步操作将总异或和 S=a1⊕a2⊕a3⊕⋯⊕an 变为 0。即若设对第 i 堆石子操作后，第 i 堆剩余的石子数量为 t，则此时对手进入必败态的条件为：a1⊕a2⊕⋯⊕t⊕⋯⊕an=0。 由于异或满足交换律 / 结合律，故可将上式变形，得：(a1⊕a2⊕⋯⊕ai⊕⋯⊕an)⊕ai⊕t=0，代入 S=a1⊕a2⊕⋯⊕an，得 S⊕ai⊕t=0。 由于异或满足性质（x⊕x=0 及 0⊕x=x），故可由 S⊕ai⊕t=0 推得第 i 堆剩余的石子数量 t=S⊕ai。进而可得，从第 i 堆拿走的石子数为 ai-S⊕ai。 ● Nim 博弈的合法操作是从第 i 堆拿走若干石子（至少 1 个），即操作后第 i 堆剩余的石子数 t 需满足 0≤t<ai。结合上文结论 t=S⊕ai，可得“先手必胜”的充要条件为：S⊕ai<ai。 ● 设 S=a1⊕a2⊕⋯⊕an，k 是 S 的二进制表示中「最左边的 1 所在的位置」。则在 a1，a2，⋯，an 中，只有满足第 k 位为 1 的 ai（其中，i∈[1~n]），才能通过合法操作（拿走若干石子），将总异或和变为 0，使对手进入必败态。 证明：要让对手必败，你必须做到两件事： （1）有效：修改完 ai 后新的总异或和变成 0。 若要使总异或和变为 0，必须将 ai 改为 S⊕ai，无其他可能。 这是因为，设原来总异或和 S=a1⊕a2⊕⋯⊕ai⊕⋯⊕an，现在若只把 ai 换成一个新数 t，让新的总异或和等于 0（必败状态），即让 a1⊕a2⊕⋯⊕t⊕⋯⊕an=0。等价于，(a1⊕a2⊕⋯⊕ai⊕⋯⊕an)⊕ai⊕t=0，即 t=S⊕ai。 （2）合法：只能拿走石子，不能加。 由于 k 是 S 的二进制表示中「最左边的 1 所在的位置」，即最高位，所以这一位决定 S 的大小。 ① 如果 ai 的第 k 位等于 1，则第 i 堆剩余的石子数量 t=S⊕ai 的第 k 位变成 1⊕1=0。则 t=S⊕ai 一定变小，即 t=S⊕ai<ai。显然，合法（拿走石子）且有效（异或和变 0）。 ② 如果 ai 的第 k 位等于 0，则第 i 堆剩余的石子数量 t=S⊕ai 的第 k 位变成 0⊕1=1。则 t=S⊕ai 一定变大，即 t=S⊕ai>ai。显然，不合法（要加石子）、无效（最高位还是 1，异或和不可能为 0）。 ● 为什么一定要从 S=a1⊕a2⊕⋯⊕ai⊕⋯⊕an 的二进制表示的「最左边的 1 所在的位置」开始判断？ 答：设 k 是 S=a1⊕a2⊕⋯⊕ai⊕⋯⊕an 的二进制表示中「最左边的 1 所在的位置」。因为只有这一位，能保证第 i 堆剩余的石子数量 t=ai⊕S 与 ai 的大小关系绝对确定。原因是： 1. 若 ai 第 k 位等于 1，则 S⊕ai 的第 k 位等于 0 => S⊕ai<ai。 2. 若 ai 第 k 位等于 0，则 S⊕ai 的第 k 位等于 1 => S⊕ai>ai。 而在 k 右边的任意低位，都无法保证上述大小关系。 例如，S=3^6^9=12，对应的二进制为 1100。现在故意不用 S「最左边的 1 所在的位置」，改用 S「最右边的 1 所在的位置」，看会发生什么？ 由于 S=3^6^9=12「最右边的 1 所在的位置」为 2（下标从 0 开始）。则： 3 = 0011 → 第 2 位 = 0 6 = 0110 → 第 2 位 = 1 9 = 1001 → 第 2 位 = 0 按上述规则，改第 2 位是 1 的堆，也就是 6 这堆，可得 12^6=10。 可见：10>6 → 要加石子，非法！ ● 异或运算的基本性质（https://blog.csdn.net/hnjzsyjyj/article/details/154304346） 异或运算（XOR）具有以下重要性质： 交换律：a ^ b = b ^ a 结合律：a ^ (b ^ c) = (a ^ b) ^ c 自反性：a ^ a = 0 零元素：a ^ 0 = a 可逆性：如果 a ^ b = c，那么 a = c ^ b 【算法代码】
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N];
int n;
int main() {
int s=0;
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
s^=a[i];
}
if(s) {
int k=0;
//Find left-most bit '1' in binary of s
for(int i=31; i>=0; i–) {
if(s>>i & 1) {
k=i;
break;
}
}
//Find 1st stone heap where k-th bit is '1'
for(int i=1; i<=n; i++) {
if(a[i]>>k & 1) {
cout<<a[i]-(s^a[i])<<" "<<i<<endl;
//remaining stones in i-th pile is s^a[i]
a[i]=s^a[i];
break;
}
}
for(int i=1; i<=n; i++) cout<<a[i]<<" ";
} else cout<<"lose\\n";
return 0;
}
/*
in:
3
3 6 9
out:
4 3
3 6 5
*/
【参考文献】 https://blog.csdn.net/hnjzsyjyj/article/details/158731890 https://blog.csdn.net/hnjzsyjyj/article/details/158728832 https://www.acwing.com/solution/content/13187/ https://blog.csdn.net/hnjzsyjyj/article/details/154304346 https://www.acwing.com/file_system/file/content/whole/index/content/12084580/ https://blog.csdn.net/hnjzsyjyj/article/details/158704426 https://blog.csdn.net/hnjzsyjyj/article/details/154310120
