题目类型 博弈题
题目意思
给出 n 堆石子 (1 <= n <=1e5) 每堆石子有 Mi 种, 第1种有 Xi 个, 第2种有 Xi+1个, 依次类推 (1 <= Xi, Mi <=1e16)
两个人轮流从 n 堆石子中取石子, 每一次可以从 n 堆石子中其中一堆取其中一种的一部分(最少取这种石子的1个,最多可以全部取完) 不能取石子的输 假设两个人以最优方式来取 问最终赢的是谁
解题方法
基本模型是 Nim 游戏 传送门 -> 博弈论的一点资料，关于NIM和SG函数
最暴力的方法 就是把所有种类的石子数量 异或起来 看是0还是非0 但是显然会超时
可以这样考虑 对于第 1 堆石子, 这堆石子的 M1种石子的数量分别是 X1, X1+1, X1+2, X1+3, ..., X1+M1-1
要求的是 X1 ^ (X1+1) ^ (X1+2) ^ (X1+3) ^ ... ^ (X1+M1-1) 的结果
如果用 Ri 表示 0 ^ 1 ^ 2 ^ 3 ^... ^ i 的结果, 那么上式的结果 = R(X1+M1-1) ^ R(X1-1) 因为 R(X1-1) ^ R(X1-1) == 0
所以只需 求 R(X1+M1-1) 和 R(X1-1)即可
对于0-16的二进制
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
可以发现 前 x 个数的最右边的那一位(即权值为pow(2,0)那位)上的1的数量 = x/(1<<(0+1)) * (1<<0) + x%(1<<(0+1))-(1<<0)
倒数第二位(即权值为pow(2,1)那位)上的1的数量 = x/(1<<(1+1)) * (1<<1) + x%(1<<(1+1))-(1<<1)
........................................................................................
即前 x 个数的从右往左数的第 i 位(i从0开始) 上1的数量 = x/(1<<(i+1)) * (1<<i) + x%(1<<(i+1))-(1<<i)
(即第0位上每两个数就有1个1 第1位上每4个数有2个1 第2位上每8个数有4个1)
如果要求前 x 个数异或起来的结果 那么相当于 这x个数的二进制形式下每一位异或的结果加起来的值 而每一位异或起来的结果取决于前x个数
的二进制形式在这一位上的1的数量, 如果为奇数则异或结果为1,否则为0
对于每一堆石子都可以这样求出里面 Mi 种石子异或起来的结果 再把这 n 个结果异或起来就是所有种类的石子异或起来的结果
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 10;
LL a[MAXN], b[MAXN];
LL Solve(LL ta, LL tb) {
tb += ta;
LL res = 0;
for( int i=0; i<60; i++ ) {
LL na = ta / (1LL<<(i+1)) * (1LL<<i);
na += max(ta % (1LL<<(i+1)) - (1LL<<i), 0LL);
LL nb = tb / (1LL<<(i+1)) * (1LL<<i);
nb += max(tb % (1LL<<(i+1)) - (1LL<<i), 0LL);
if((nb-na)&1) res += (1LL<<i);
}
return res;
}
int main() {
int n;
while(cin>>n) {
LL res = 0;
for( int i=0; i<n; i++ ) {
cin>>a[i]>>b[i];
LL tmp = Solve(a[i], b[i]);
res ^= tmp;
}
if(res) printf("tolik\n");
else printf("bolik\n");
}
return 0;
}