自动搬运

查看原文

来自洛谷，原作者为

	Vatyr **

搬运于2025-08-24 21:49:25，当前版本为作者最后更新于2017-10-22 18:43:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设a[i]表示第i堆石子的个数，c[i]表示a[i]-a[i-1],则我们每堆可以拿的石子数即为c[i]。当我们在第i堆拿了x个时，c[i]变成了c[i]-x，c[i+1]变成了c[i+1]+x，相当于我们把第i堆中可拿的石子转移到了i+1堆，由此我们可以把此题转化为一道反着的阶梯nim游戏。

下面简单讲解一下阶梯nim，如果不懂的话可以去网上搜一下。

阶梯nim是指，有n堆石子，每次我们可以从第i堆的石子中拿走一部分放到第i-1堆中，或者把第1堆中的石子拿走一部分，无法操作的人算输。先说结论：阶梯nim的游戏结果与只看奇数堆的石子数的普通nim结果相同。

假设我先手，那么我可以按照必胜策略把奇数堆中的石子转移到偶数堆，当对方拿的时候我们分情况讨论：

1. 对方拿奇数堆中的石子到偶数堆，相当于进行对于奇数堆的普通nim，我们继续按照必胜策略拿奇数堆中的石子；

2. 对方把偶数堆的石子拿到奇数堆，则我们可以把这部分石子继续向下拿，对于奇数堆相当于局势没有变动。

以上，我们简单证明了阶梯nim与奇数堆普通nim的等价。下面贴上渣代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int u;
int n;
int a[10004];
int c[10004];
int main()
{
    scanf("%d",&u);
    while(u--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            c[i]=a[i]-a[i-1];
        int ans=0;
        for(int i=n;i>=1;i-=2)
            ans^=c[i];
        if(ans)printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}

一定要注意这道题是从第i堆拿到第i+1堆，所以要反着跑阶梯nim！！