Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 1115: [POI2009]石子游戏Kam

题目链接

传送门

Description

有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

Sample Output

NIE

TAK

题解

考虑这个题的限制条件
面对一个 当你选择把这堆中的几个石子拿出去带来的影响是什么呢
首先当然了场上的石子减少了
其次是精髓 当我们拿走了这堆中的石子的时候 这堆可供拿出去的石子变少了 这堆的上面那堆可供拿出的石子变多了 而且这两个变化量是相等的
想到这里了自然想到了阶梯博弈

代码

One Comment

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏