题解 P1247 【取火柴游戏】
revenger
2017-05-09 21:00:43
经典Nim游戏模型
这个游戏的SG值就是各堆数量的异或和，当SG为0时先手必败，否则先手就要把SG变为0
先检验SG值，如果是0输出lose，否则我们按照以下原则行动
有n个数的异或值不为0 现在要减少一个数使异或值为0
假设n个数：a1 ,a2,a3...an
a1^a2^a3^..^an=k
那么我们可以对一个数进行操作,假设这个数是a1，设a1^k=a'，a'^a2^a3^...^an=a1^a2^a3^...^an^k=k^k=0;
所以我们只需要从头到尾检验每个数异或k的值是否比它小(因为是要减少)，遇到小的直接输出ai-ai^k即可
代码：
```cpp
#include<cstdio>
int k,n[500002];
int main()
{
scanf("%d",&k);int x=0;
for(int i=1;i<=k;i++)
{
scanf("%d",&n[i]);
x^=n[i];
}
if(!x){puts("lose");return 0;}
for(int i=1;i<=k;i++)
{
if((n[i]^x)>=n[i]) continue;
printf("%d %d\n",(n[i]-(n[i]^x)),i);
n[i]=n[i]^x;
break;
}
for(int i=1;i<=k;i++)
printf("%d ",n[i]);
}
```