首页 > 代码库 > codeforces 15C. Industrial Nim

codeforces 15C. Industrial Nim

题目链接:http://codeforces.com/problemset/problem/15/C


$NIM$游戏是次要的,直接异或石头堆就可以了,问题在于给出的石头堆的数量极多。

考虑利用异或的性质。

一共给出了$n$段石头堆,每段中石头堆的数量是连续的。

在$x$是偶数时${x^(x+1)=1}$,利用这个性质我们就可以${O(1)}$的算出每一段石头的异或和。


 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1001010 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);12 llg n,m,T,ans,x;13 int main()14 {15     yyj("nim");16     cin>>T;17     while (T--)18     {19         llg xo=0;20         cin>>x>>n;21         m=x+n-1;22         if (x%2) xo^=x,n--;23         if ((n/2)%2) xo^=1;24         if (n%2) xo^=m;25         ans^=xo;26     }27     if (ans) cout<<"tolik";else cout<<"bolik";28     return 0;29 }30 //对于一个数x%2=0,x^(x+1)=1

 

codeforces 15C. Industrial Nim