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

BZOJ1115

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

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

#include<bits/stdc++.h>
using namespace std;
int a[10005];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int ans=0,n;
        scanf("%d",&n);
        for(int i=1;i<=n;++i)   scanf("%d",&a[i]);
        for(int i=n;i>1;i-=2)   ans^=(a[i]-a[i-1]);
        if(n&1) ans^=a[1];
        printf(ans ? "TAK
" : "NIE
");
    }
    return 0;
}

P2575

题目

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

游戏规则是这样的：

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

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

#include<cstdio>
#include<cstring>
int T,N,K,cnt,tot,x,ans1,ans2;
bool vis[23];//vis[i]==true表示i位置有石子
int main()
{
    scanf(" %d",&T);
    while(T--)
    {
        scanf(" %d",&N);ans2=0;//整个数据的SG值用ans2储存
        while(N--)
        {
            scanf(" %d",&K);
            memset(vis,false,sizeof(vis));
            cnt=20-K+1;tot=0;ans1=0;//cnt即C,tot储存当前阶梯棋子个数，ans1储存本行SG值
            while(K--)
            {
                scanf(" %d",&x);
                vis[x]=true;//标记有石子
            }
            for(int i=1;i<=20;++i)
            {
                if(!vis[i])
                {
                    if((--cnt)&1)ans1^=tot;//奇数级阶梯，异或
                    tot=0;
                }
                else ++tot;//加棋子到阶梯上
            }
            ans2^=ans1;//SG定理应用
        }
        if(ans2)printf("YES
");
        else printf("NO
");
    }
    return 0;
}

参考链接：

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