2017-03-02

【bzoj1115】石子游戏Kam

本文为博主原创，未经许可不得转载

AC通道

题解

每堆石子的个数不少于前一堆石子的个数可以看成是相邻两堆石子时间的个数差保持非负。

于是可以把这些石子差看做石子，每次操作会将其中一堆石子减去一个值，又会将它后面的一堆加上相等的值，就可以看做是把这一堆推到它后面的一堆。

于是转化成了阶梯博弈。

手瞎眼瞎的博主犯了很低级的错误：把输出中的”NIE”打成了”NIM”，然后就是无限wa

参考代码

#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
int n,a[1010];
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,f=1;  char ch=getc();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
		return x*f;
	}
}using namespace INIT;
void solve(){
	n=read(); int ans=0;
	for(int i=1;i<=n;++i)  a[i]=read();
	for(int i=n;i>=1;i-=2)  ans^=(a[i]-a[i-1]);
	puts(ans?"TAK":"NIE");
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	for(int T=read();T;--T)  solve();
	return 0;
}

本文标题:【bzoj1115】石子游戏Kam

文章作者:chty

发布时间:2017年03月02日 - 08时52分

最后更新:2018年03月02日 - 17时32分

许可协议:本文为博主原创，未经许可不得转载。