本文主要是介绍1740 A New Stone Game，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
有N堆石头，两人分别从这N堆石头中取走石头，去石头的规则是：玩家必须从任一堆石头中取走至少一块石头，可以全部取走。如果没有全部取走，可以把剩下的石头任意数目一道其他任一堆石头上去，最后不能取时候的人为输。
解题思路：
对于博弈题目做的毕竟还是少，很多的博弈题的规律还没有找到，从网上看了一下解题报告，想法真的很好，代码实现起来也很简单。废话少说，切入正题：
首先讨论对于N堆石头数目两两相等的情况，假设为x,x,y,y,z,z，那么先取者必输，因为无论先取得人如何操作，后取的人都可以做同样的操作（先取者取走一堆中任意数目的石头，后取者都可以从和这堆石头数目相同的那一堆中取走数目相同的石头数，如果先取者把石头移动到其他堆上去，那么后取者也可以移动相同数目的石头到对应的石头堆上去），直至后者把最后的石头取完。
由这个结论，就可以把N堆石头中数目相同的两对去掉，只讨论两两不相同的情况：
1、只有一对石头，数目为x，则先取者胜。
2、只有两堆石头，数目为x,y(递增的顺序)，则先取者胜。先取者可以从数目为y的那堆石头中取走y-x块石头，这样两堆石头数目相同。
3、只有三堆石头，数目为x,y,z（递增顺序）,从第三堆石头中取走z-y+x块石头，然后把剩下的y-x块石头移动到第一堆中，变只有两对，数目为y,y的局势。还是先取者获胜。
4、以此类推，只要堆石头数目最大的那一堆进行操作，总能达到两两相等的局势，所以只要石头的数目不全是两两相等，那么先取者必胜。
代码：
#include<cstdio>
#include<cstring>int main(){int n,num[20];int mark[105];while(scanf("%d",&n), n){memset(mark,0,sizeof(mark));for(int i=0; i<n; i++){scanf("%d",&num[i]);if(mark[num[i]]) mark[num[i]]--;else mark[num[i]]++;}int flag=0;for(int i=0;i<105;i++){ //统计是不是全部都两两相等if(mark[i]) flag++;}//printf("flag=%d\n",flag);if(flag) printf("1\n");else printf("0\n");}return 0;
}
这篇关于1740 A New Stone Game的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
