浅谈博弈论

封面来源

Pixiv dirty rabbit-68874698

一、巴什博弈(Bash Game)

A和B报数，最少报1个，最多报n个，最后取到的获胜

就是同余原理

1
2
3
4
5
6


if(n%(m+1)){
    cout<<"后手\n";
}
else{
    cout<<"先手\n";
}

二、威佐夫博弈(Wythoff’s game)

两堆物品，两人轮流从其中一堆去除至少一件物品，或者从两堆中取相同件物品，最后取完的获胜

看是否满足$ |{x1-x2}|\times \frac {\sqrt{5}+1}2 =\min(x1,x2)$

例题: P2252 SHOI2002取石

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


int a,b;
const double Gol = (sqrt(5.0)+1.0)/2.0;
int main(){
    cin>>a>>b;
    if(a<b){
        swap(a,b);
    }
    int del = a-b;
    if(b==int(Gol*double(del))){
        cout<<0;
        return 0;
    }
    cout<<1;
}

三、尼姆博弈(Nimm Game)

有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。

异或理论

把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜。

例题: P2197 nim 游戏

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


int t,n;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        int ans = 0;
        for(register int i=1;i<=n;++i){
            int t;
            cin>>t;
            ans^=t;
        }
        if(ans){
            cout<<"Yes\n";
        }
        else{
            cout<<"No\n";
        }
    }
}

四、斐波那契博弈

有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜

物品总数不是斐波那契数时先手胜

例题： HDU 2516

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


const int N = 55;
int f[N];
void Init() {
    f[0] = f[1] = 1;
    for (int i = 2; i < N; i++)
        f[i] = f[i - 1] + f[i - 2];
}
int main() {
    Init();
    int n;
    while (cin >> n) {
        if (n == 0)
            break;
        bool flag = 0;
        for (int i = 0; i < N; i++) {
            if (f[i] == n) {
                flag = 1;
                break;
            }
        }
        if (flag)
            puts("Second win");
        else
            puts("First win");
    }
    return 0;
}