首页 > 代码库 > CodeForces 15C Industrial Nim

CodeForces 15C Industrial Nim

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

题意:nim博弈变形,第一行给出N表示有N个采石场,接下来N行每一行一个Mi一个Xi,表示第i个采石场有Mi量车,第1辆车的石头量是Xi,第二是Xi+1,第Mi辆车的石头的数量是Xi+Mi-1。有两个人玩nim博弈,最后一个取完的赢,先手赢输出tolik,后手赢输出bolik。

 

思路:这题如果直接进行异或运算,数据量太多,会超时,再加上这些数都是有连续的,然后貌似我就1^2^3^...^n打了个表找了下规律,发现是结果以4为周期的,根据规律打了份代码,aa(x)就是求从1,2一直进行异或运算直到x。因为异或运算的性质是相同的数异或起来是0,所以算从a一直连续异或到b可以先计算从1~b,用得出的结果再异或从1~(a-1)(感觉就像减法,1~b减去1~a-1,就是a~b)。

然后异或所有的a~b就知道答案了。

代码:

技术分享
ll aa(ll b){    ll sum=0;    if(b%4==1)        return (b+1)^b;    else if(b%4==2)    {        return b+1;    }    else if(b%4==3)    {        return 0;    }    else        return b;}int main(){//    std::ios::sync_with_stdio(false);    ll sum=0;    int t;    cin>>t;    ll a,b;    while(t--)    {        cin>>a>>b;        b+=a-1;        sum^=aa(a-1)^aa(b);    }    if(sum)    {        puts("tolik");    }    else    {        puts("bolik");    }
View Code

 

 

关于nim博弈:是两个人在若干堆中轮流取石子,每次每人可以选择一堆,从中取出最少数量为1个,最多为一堆的石子,先手取完胜。

如果只有一堆,那么就先手直接取完一堆,先手胜。

如果两堆,那么主要看这两堆石子是否数量相同,若最初不相同,则先手可以将其取至相同状态,不论后手取多少,先手都可以在另一堆取相同数量,然后维持到游戏结束,否则后手可以维持这个平衡状态,一直到取最后一次。

所以在有很多堆时,就可以通过看他们所有堆的二进制的相对位上的和是否是偶数,若都是偶数,那就是达到了平衡态,否则可以将非平衡态的非平衡二进制数位上拿走1,使他再次达到平衡态。

所以若堆上的相对数位和为偶数,那么他们这一位进行连续异或运算得出来的答案为0,所以若达到平衡态,则所有数位进行异或结果都是0。

所以就得出了那个结论,当所有堆进行异或 答案为0时,后手赢,否则先手赢。

我之前是只知结论不知缘由,于是百度了一下找原理。

上面是我理解的,可能我会有些错误或者表述不清,具体可以参考网址:http://www.cnblogs.com/exponent/articles/2141477.html

CodeForces 15C Industrial Nim