bzoj1115&&POJ1704&&HDU4315——阶梯Nim

BZOJ1115

题意：阶梯Nim游戏大意：每个阶梯上有一堆石子，两个人在阶梯上玩推石子游戏。每人可以将某堆的任意多石子向左推一阶，所有的石子都推到阶梯下了即算成功，即不能推的输。

分析：根据阶梯Nim的思想，推偶数堆（索引为偶数的）是没有意义的（详见链接），只需将奇数堆求Nim和，即异或和。

#include<bits/stdc++.h>

using namespace std;

int a[];

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        int ans=,n;

        scanf("%d",&n);

        for(int i=;i<=n;++i)   scanf("%d",&a[i]);

        for(int i=n;i>;i-=)   ans^=(a[i]-a[i-]);

        if(n&) ans^=a[];

        printf(ans ? "TAK\n" : "NIE\n");

    }

    return ;

}

P2575

题目

现在给你一个n*20的棋盘，以及棋盘上有若干个棋子，问谁赢？akn先手！

游戏规则是这样的：

对于一个棋子，能将它向右移动一格，如果右边有棋子，则向右跳到第一个空格，如果右边没有空格，则不能移动这个棋子，如果所有棋子都不能移动，那么将输掉这场比赛。

分析：两个空格之间棋子的个数视为一堆，同样只需求奇数堆的Nim和。

#include<cstdio>

#include<cstring>

int T,N,K,cnt,tot,x,ans1,ans2;

bool vis[];//vis[i]==true表示i位置有石子

int main()

{

    scanf(" %d",&T);

    while(T--)

    {

        scanf(" %d",&N);ans2=;//整个数据的SG值用ans2储存

        while(N--)

        {

            scanf(" %d",&K);

            memset(vis,false,sizeof(vis));

            cnt=-K+;tot=;ans1=;//cnt即C,tot储存当前阶梯棋子个数，ans1储存本行SG值

            while(K--)

            {

                scanf(" %d",&x);

                vis[x]=true;//标记有石子

            }

            for(int i=;i<=;++i)

            {

                if(!vis[i])

                {

                    if((--cnt)&)ans1^=tot;//奇数级阶梯，异或

                    tot=;

                }

                else ++tot;//加棋子到阶梯上

            }

            ans2^=ans1;//SG定理应用

        }

        if(ans2)printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

参考链接：

1. https://blog.csdn.net/liangzhaoyang1/article/details/51213003

2. https://www.luogu.org/problemnew/solution/P2575

3. https://blog.csdn.net/zP1nG/article/details/79072716