首页 > 代码库 > POJ 1740
POJ 1740
这题，通过多次试验，可以发现，当只存在两堆（以下称对）相等的石子时，先手必输。更进一步，当N对这样的石子存在时，先手必输。
于是，若1要赢，一种方法是，把石子都变成相等的对。
考虑石子中无对的情况，若存在对，我们把那些对忽略，因为先手对于这些对是必输的。
当N为奇数时，随机考虑这样的情况(有序)a<b<c<d<e。可知，先手必定能把这些石子变成对。因为e>=(b-a)+(d-c)，只需从e中取走若干后把剩余的分配即可。
当N为偶数时，考虑a<b<c<d<e<f。先手同样必胜，因为(f-a)>=(c-b)+(e-d)。
于是，当初始均为对时，先手输，否则先手胜。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int N=105; 7 int co[N]; 8 int n; 9 10 int main(){11 int tmp;12 while(scanf("%d",&n)!=EOF){13 if(n==0) break;14 memset(co,0,sizeof(co));15 for(int i=1;i<=n;i++){16 scanf("%d",&tmp);17 co[tmp]=(co[tmp]+1)%2;18 }19 int ans=0;20 for(int i=1;i<=100;i++){21 if(co[i])22 ans++;23 }24 if(ans) printf("1\n");25 else printf("0\n");26 }27 return 0;28 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。