首页 > 代码库 > 【BZOJ 1115】 [POI2009]石子游戏Kam
【BZOJ 1115】 [POI2009]石子游戏Kam
1115: [POI2009]石子游戏Kam
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 551 Solved: 339
[Submit][Status]
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
2
2 2
3
1 2 4
Sample Output
NIE
TAK
TAK
HINT
感谢MT大牛翻译.
此题是一道阶梯博弈题。
详见 《我谈阶梯博弈》。
对于这道题，当你从i处拿走x个石子，那么i+1处就可以多拿走x个石子，相当于把i堆的x个移动到了i+1堆。
这样就转化成了阶梯博弈，只要考虑奇数堆即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
int a[10005];
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
int ans=0,n;
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=n;i>1;i-=2)
ans^=(a[i]-a[i-1]);
if (n&1) ans^=a[1];
if (ans) printf("TAK\n");
else printf("NIE\n");
}
return 0;
}
感悟：
这道题还是很巧妙的：
奇数堆只保留与前面偶数堆的差值；
把偶数堆的移走相当于移到他后面的奇数堆，那么此时先手再把移到奇数堆的移到后面的偶数堆，以此类推，最终偶数堆没有了，只剩下奇数堆的，按找nim游戏的必胜策略来取即可（一定是符合题意的）。
导致最终结果与偶数堆没有一点关系。
【BZOJ 1115】 [POI2009]石子游戏Kam
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。