题解：SP20951 SNIM - Pebbles

· · 题解

每次操作后序列单调不降，可以转换成在差分序列上进行操作，要求差分数组 d_i 恒大于 0。

假设从第 i 堆移走 k 个石子，那么它相邻的两个差分值一个减少 k，一个增加 k。发现原问题转换成了在序列的差分数组上进行阶梯 Nim 游戏。

直接应用结论：先手必败当且仅当奇数堆的石子数异或和为 0。

注意要从右往左编号。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1005;
int n,a[N],c[N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T; cin>>T;
    while(T--){
        cin>>n; int ans = 0;
        for(int i=1;i<=n;i++) cin>>a[i],c[i]=a[i]-a[i-1];
        for(int i=n;i>=1;i-=2) ans^=c[i];
        if(ans) cout<<"TAK"<<endl;
        else cout<<"NIE"<<endl;
    }
    return 0;
}