题解：SP20951 SNIM - Pebbles

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

d_i

恒大于

0

。

假设从第

i

堆移走

k

个石子，那么它相邻的两个差分值一个减少

k

，一个增加

k

。发现原问题转换成了在序列的差分数组上进行阶梯 Nim 游戏。

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

0

。

注意要从右往左编号。

CPP

#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;
}

题解：SP20951 SNIM - Pebbles

文章操作

相关推荐

评论

题解：SP20951 SNIM - Pebbles