首页 > 代码库 > BZOJ1115: [POI2009]石子游戏Kam
BZOJ1115: [POI2009]石子游戏Kam
1115: [POI2009]石子游戏Kam
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 500 Solved: 308
[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大牛翻译.
Source
题解：
考虑将问题转化到阶梯NIM上来。
首先初始 i 格可以移掉的石子数 为 a[i]-a[i-1]
事实上，若我们从 i 处取走了 x 个石子，那么下一次及以后就可以在 i+1 处多取 x 个，相当于 把 i 处的 x 个石子加到了 i+1处。
问题就转化成了阶梯NIM。
orz
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 100514 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 int n,cs,ans,a[maxn];32 int main()33 {34 freopen("input.txt","r",stdin);35 freopen("output.txt","w",stdout);36 cs=read();37 while(cs--)38 {39 n=read();40 for1(i,n)a[n+1-i]=read();a[n+1]=0;41 ans=0;42 for1(i,n)if(i&1)ans^=a[i]-a[i+1];43 if(ans)printf("TAK\n");else printf("NIE\n");44 }45 return 0;46 }
BZOJ1115: [POI2009]石子游戏Kam
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。