洛谷 P3480 [POI2009]KAM-Pebbles

https://www.luogu.org/problemnew/solution/P3480

讲不清楚。。。

首先对原序列做差分；设原序列为a，差分序列为d

那么，每一次按题意在原序列位置i处取走石子x个，相当于在差分序列的位置i处拿石子x个到位置i+1处（要求差分序列任意元素始终非负）（如果i=n那么抛弃这x个石子）

如果抽离出所有与n奇偶性相同的i，得到d[i]形成序列，对于nim游戏满足后手必胜，对于后手一方，如果对方上一次操作了位置i，有如下应对策略：

1.对于所有与n奇偶性不同的位置i，如果对方从d[i]处移动x个到d[i+1]处，则自身就从d[i+1]处移动x个到d[i+2]处；

2.对于所有与n奇偶性相同的位置i，将这些位置抽离出来，单独形成序列，用nim游戏的策略去做就行了，因为每一次从d[i]移动x个到d[i+1]，d[i+1]并没有在抽离出的序列里，对于对方进行的所有方式1的移动，又可以用以上策略消去其对抽离出序列构成的影响

因此，抽离出所有与n奇偶性相同的i，得到d[i]形成序列，那个nim游戏的结果就是该游戏的结果

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int n,a[],b[];

 int main()

 {

     int T,i,t;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

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

         t=;

         for(i=n;i>=;i-=)    t^=b[i];

         puts(t?"TAK":"NIE");

     }

     return ;

 }