题解 P3480 【[POI2009]KAM-Pebbles】

· · 题解

设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！！