ACM 1740 A New Stone Game http://acm.pku.cn/JudgeOnline/problem?id=1740

题目大意:有N堆石头,每堆石头数目在1到100之间,最多有10堆.两人分别取走石头.取石头的规则是:每次只能从1堆中取,每次取走至少1个.取过后还可以把这堆的石头任意分配到其它堆上(这些堆必须有石头,废话呵呵),当然也可以不分配.问给定这些石头堆的情况,两人轮流取,谁先取完谁胜利,问是先取的胜利还是后取的胜利.双方最优策略. 我就直接说结论了: 首先讨论石头堆两堆两堆相等的情况,例如x,x,y,y,z,z.6堆的情况.在这种情况下先取的必输,很简单,先取的那人怎么取后取的那人就怎么取(如果对方把石头分配到一堆上,你就分配到与之对应的堆上),总之保持这个相等的均势不变,这样到最后,后取的人就将取走最后一堆石头. 知道这个结论后,就可以把N堆中两两相等的堆去掉,来讨论互不相等的堆来. 第一,只有一堆x,第一个人直接全部取走就胜利了.(显然x,y,y的情况也是第一人胜,所以忽略相等的石头); 第二,x,y的形式(这里不妨假设递增,下同).第一人从第二堆中取走(y-x)个石头,这样两堆相等,最终还是第一人胜; 第三,x,y,z的形式.第一人从最后一堆中取走(z+x-y)个石头,再将(y-x)个石头移到第一堆上(z>y-x一定成立),这样还是第一人胜.

依此类推,移动个数最多的石头堆然后再分配总可以前面变成两两相等的情况.可见只要开始不全是两两相等,那先取者必胜

#include<stdio.h> 
int main() 
{ int n,i,j,k,d[10],f[10],q; 
scanf("%d",&n); 
while (n!=0) 
{ 
j=0; q=0; 
for (i=0;i<n;i++) 
{ f[i]=1; scanf("%d",&k);for (j=0;j<q;j++) { if (d[j]==k) { f[j]++;break; } }if (j==q)d[q++]=k; 
}
for (i=0,j=0;i<q;i++) if (f[i]%2!=0) j++; if (j==0) printf("0\n");else printf("1\n"); scanf("%d",&n); 
} 
return 0; 
}

转载于:https://www.cnblogs.com/Chinese-Coder-Clarence/articles/2039334.html

总结

以上是生活随笔为你收集整理的ACM 1740 A New Stone Game http://acm.pku.cn/JudgeOnline/problem?id=1740的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。