codeforces 15C. Industrial Nim

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


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

考虑利用异或的性质。

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

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


 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 10010
#define llg long long
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,T,ans,x;
int main()
{
yyj("nim");
cin>>T;
while (T--)
{
llg xo=;
cin>>x>>n;
m=x+n-;
if (x%) xo^=x,n--;
if ((n/)%) xo^=;
if (n%) xo^=m;
ans^=xo;
}
if (ans) cout<<"tolik";else cout<<"bolik";
return ;
}
//对于一个数x%2=0,x^(x+1)=1
上一篇:[转]WIBKIT技术资料


下一篇:Codeforces - 662A 思路巧妙的异或