Codeforces 15C Industrial Nim

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

题意:有n个采矿厂,每个采矿场有m_i台倒石头的机器,每个机器依次有x_i,x_i+1,\dots,x_i+m_i-1个石头,然后玩NIM游戏,问先手必胜还是必败。

思路:怎么点开games标签都不太是博弈论。。。NIM博弈结论知道以后就是要快速求[x_i,x_i+m_i+1]的异或和,区间连续异或和转成前缀异或和,打个表发现是以4为周期的,然后就做完了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9')f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
ll cnt(ll x){
    ll tmp=x%4;
    if (tmp==1) return 1LL;
    else if (tmp==2) return x+1LL;
    else if (tmp==3) return 0LL;
    else return x;
}
int n;
ll m,x,res;
int main(){
    for (read(n);n--;){
        read(x),read(m);
        res^=cnt(x-1);
        res^=cnt(x+m-1);
    }
    puts(res==0?"bolik":"tolik");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注