题解 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即可

代码：

#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]);
}