首页 > 代码库 > 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"); }
关于nim博弈:是两个人在若干堆中轮流取石子,每次每人可以选择一堆,从中取出最少数量为1个,最多为一堆的石子,先手取完胜。
如果只有一堆,那么就先手直接取完一堆,先手胜。
如果两堆,那么主要看这两堆石子是否数量相同,若最初不相同,则先手可以将其取至相同状态,不论后手取多少,先手都可以在另一堆取相同数量,然后维持到游戏结束,否则后手可以维持这个平衡状态,一直到取最后一次。
所以在有很多堆时,就可以通过看他们所有堆的二进制的相对位上的和是否是偶数,若都是偶数,那就是达到了平衡态,否则可以将非平衡态的非平衡二进制数位上拿走1,使他再次达到平衡态。
所以若堆上的相对数位和为偶数,那么他们这一位进行连续异或运算得出来的答案为0,所以若达到平衡态,则所有数位进行异或结果都是0。
所以就得出了那个结论,当所有堆进行异或 答案为0时,后手赢,否则先手赢。
我之前是只知结论不知缘由,于是百度了一下找原理。
上面是我理解的,可能我会有些错误或者表述不清,具体可以参考网址:http://www.cnblogs.com/exponent/articles/2141477.html
CodeForces 15C Industrial Nim