首页 > 代码库 > [原博客] POJ 1740 A New Stone Game
[原博客] POJ 1740 A New Stone Game
题目链接
题意：有n堆石子，两人轮流操作，每次每个人可以从一堆中拿走若干个扔掉（必须），并且可以从中拿走一些分到别的有石子的堆里（可选），当一个人不能拿时这个人输。给定状态，问是否先手必胜。
我们参考普通取石子游戏可知，如果只有一堆，先手必胜。
如果有两堆一样，先手必败，对称博弈，第一个人怎么取，第二个人也可以怎么取，直到第一个人无法取为止。
如果有四堆两两一样，还是先手必败，第一个人无论如何取，第二个人可以再次取成两两一样。
如果有2*k堆两两一样，还是先手必败。
注意：除了上述情况，都是先手必胜。
因为先手无论奇偶总能把最多的那堆匀到其他堆上使之两两相等，（若堆数是奇数那么最多的那堆就不剩了，若堆数是偶数，那么最多的那堆应该剩下和最小的一堆进行匹配）。
证明如下图。设一共有9堆分别是1，2，3，3，5，7，8，9，11（排序后）。
最大堆为11，蓝色的为原来高度，绿色的为要补的，可以看出绿色的和总小于最大值（黄色）。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring> //by zrt//problem:using namespace std;typedef long long LL;const int inf(0x3f3f3f3f);const double eps(1e-9);bool f[105];int n;int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif while(scanf("%d",&n),n){ int ans=0; memset(f,0,sizeof f); for(int i=0,x;i<n;i++){ scanf("%d",&x); if(f[x]) ans++; else ans--; f[x]=!f[x]; } if(ans) puts("1"); else puts("0"); } return 0;}
[原博客] POJ 1740 A New Stone Game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。