题解：SP20951 SNIM - Pebbles

思路

首先，题目说明了保证单调不降。考虑差分：将某一位的数字，差分后转移到隔壁（必定单调不降）。

如果在位置 Ind 取石子，那么：相对应的差分数组 Sub[Ind] 就会变少，而 Sub[Ind+1] 就会变多。跟阶梯 Nim 很类似。

在阶梯 Nim 中，只考虑奇数阶梯的石子堆的异或和，若结果非

{0}

，则先手必胜，否则必败。因为偶数阶梯的操作可以通过对称策略被抵消，因此不影响胜负。

例 1

CPP

[In]3 1 2 5 4

CPP

[Process]
Index^Stairs=Result
[1]->[5]=3
[2]->[4](Skipped)
[3]->[3]=2
[4]->[2](Skipped)
[5]->[1]=1

由于异或和为

{1}

。

CPP

[Out]TAK

例 2

CPP

[In]1 2 3 4

CPP

[Process]
Index^Stairs=Result
[1]->[4](Skipped)
[2]->[3]=1
[3]->[2](Skipped)
[4]->[1]=0

由于异或和为

{0}

。

CPP

[Out]NIE

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,ans=0,a=0,b;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>b;
			int step_pos=n-i+1;
			if(step_pos%2==1)
			{
				ans^=(b-a);
			}
			a=b;
		}
		puts(ans?"TAK":"NIE");
	}
	return 0;
}

题解：SP20951 SNIM - Pebbles

文章操作

思路

例 1

例 2

代码

相关推荐

评论

题解：SP20951 SNIM - Pebbles