首页 > 代码库 > bzoj 1115: [POI2009]石子游戏Kam -- 博弈论
bzoj 1115: [POI2009]石子游戏Kam -- 博弈论
1115: [POI2009]石子游戏Kam
Time Limit: 10 Sec Memory Limit: 162 MBDescription
有N堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。
Input
第一行u表示数据组数。对于每组数据，第一行N表示石子堆数，第二行N个数ai表示第i堆石子的个数(a1<=a2<=……<=an)。 1<=u<=10 1<=n<=1000 0<=ai<=10000
Output
u行，若先手必胜输出TAK，否则输出NIE。
Sample Input
2
2
2 2
3
1 2 4
2
2 2
3
1 2 4
Sample Output
NIE
TAK
TAK
HINT
感谢MT大牛翻译.
Source
阶梯博弈 （orz mjy0724 http://www.cnblogs.com/mjy0724/p/4465355.html）
描述大概就是：
两个人在阶梯上玩推石子游戏，每人操作可以将某堆的任意多石子向左推一阶
所有的石子都推到阶梯下了即算成功
我们可以只考虑在奇数堆上的操作，这样整个游戏就可以转化成NIM的模型
玩家将奇数堆中的石子推到偶数堆，可以看做是从奇数堆中取走了若干石子
两人一直把奇数堆的石子推向偶数堆，就可以用SG函数来判断胜负
然而如何考虑偶数堆呢？如果对方将偶数堆的石子推向了奇数堆
那么我们就可以把这些石子再往左推推向更左边的偶数堆
这样一个回合，奇数堆中的状态并没有改变，玩家的顺序也并没有改变
但是偶数堆却慢慢地向阶梯下移
也就是说偶数堆的情况我们完全不用去考虑
#include<cstdio>#define N 1010char xB[1<<15],*xS=xB,*xTT=xB;#define getc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++)#define isd(c) (c>=‘0‘&&c<=‘9‘)inline int read(){ char xchh; int xaa; while(xchh=getc(),!isd(xchh));(xaa=xchh-‘0‘); while(xchh=getc(),isd(xchh))xaa=xaa*10+xchh-‘0‘;return xaa;}int u,n,a[N],tp;int main(){ u=read(); while(u--) { n=read();tp=0; for(int i=0;i<n;i++) a[i]=read(); for(int i=n-1;i>=0;i-=2) tp^=(a[i]-a[i-1]); puts(tp?"TAK":"NIE"); } return 0;}
bzoj 1115: [POI2009]石子游戏Kam -- 博弈论
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。