题目链接: ヾ (≧?≦*) http://poj.org/problem?id=2975
大致题意: 给定一个 n, 给定 n 堆石子, 问有多少种第一步可以让你必胜
Solution:
我们知道, 在 NIM 游戏中, 若各堆石子异或和为 0, 则先手必败, 否则先手必胜
当先手必胜时, 每一堆最多只有一种取法让局势转换为先手必败(先手后手是在不停的互换的).
那么我们只需要检验在每一堆中是否存在一种取法让各堆异或和为 0 就行了
要注意的是, 本题读入到 0 结束
- Code:
- #include<ctype.h>
- #include<cstdio>
- #define N 1001
- using namespace std;
- int n,now,ans,a[N],k[N];
- int read(){
- int x=0,f=1;char ch=getchar();
- while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
- while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
- return x*f;
- }
- int main(){
- begin:n=read();
- if(!n)goto end;
- now=0;ans=0;
- for(int i=1;i<=n;i++)a[i]=read(),now=a[i]^now;
- if(!now){puts("0");goto begin;}
- for(int i=1;i<=n;i++)k[i]=now^a[i];
- for(int i=1;i<=n;i++)if(a[i]>=k[i])ans++;
- printf("%d\n",ans);goto begin;
- end:return 0;
- }
来源: http://www.bubuko.com/infodetail-2907434.html