算法学习:博弈论(1)
KONGJUNE / / ACM / 阅读量

学习自博客:https://www.cnblogs.com/lfri/p/10662291.html

博弈论是二人在平等的对局中各自利用对方的策略变换自己的对抗策略,达到取胜的目的。

——百度百科

ACM中博弈论题目有以下特点:

  1. 有两名选手进行轮流的决策;
  2. 每个步骤均只能在有限个行为中进行决策;
  3. 游戏会在有限的步骤内决出胜负;
  4. 公平博弈,即两人进行决策所遵循的规则相同。

常见的博弈有:巴什博弈斐波那契博弈威佐夫博弈尼姆博弈以及SG定理等。

巴什博弈

在一堆共有 $n$ 个物品的箱子中,两个人轮流取出 $1$ ~ $m$ 个物品,最终取光者胜。

结论:若 $n\mod(m + 1) = 0$ 则先手输。

证明:对于任意的一个 $n > m$ 都可以写成 $n = k * (m + 1) + r$ 的形式。我们先不管 $r$ 的存在,如果 $n$ 是 $m + 1$ 的倍数,则每一次先手都最多只能拿 $m$ 个。设单次轮回先手拿 $x$ 个,则后手完全可以拿 $m + 1 - x$ 个,这样最后一定是后手先拿到,所以当 $r = 0$ 时先手必败。而当 $r \leq 0$ 时,先手先拿 $r$ 个,则可以将必输局面转移给后手,此时先手必胜。

例题:HDU 2149

Public Sale

Problem Description

虽然不想,但是现实总归是现实, Lele 始终没有逃过退学的命运,因为他没有拿到奖学金。现在等待他的,就是像 FarmJohn 一样的农田生涯。

要种田得有田才行,Lele 听说街上正在举行一场别开生面的拍卖会,拍卖的物品正好就是一块20亩的田地。于是,Lele 带上他的全部积蓄,冲往拍卖会。

后来发现,整个拍卖会只有 Lele 和他的死对头 Yueyue。

通过打听,Lele 知道这场拍卖的规则是这样的:刚开始底价为 $0$,两个人轮流开始加价,不过每次加价的幅度要在 $1~N$ 之间,当价格大于或等于田地的成本价 $M$ 时,主办方就把这块田地卖给这次叫价的人。

Lele 和 Yueyue 虽然考试不行,但是对拍卖却十分精通,而且他们两个人都十分想得到这块田地。所以他们每次都是选对自己最有利的方式进行加价。

由于 Lele 字典序比 Yueyue 靠前,所以每次都是由 Lele 先开始加价,请问,第一次加价的时候,Lele 要出多少才能保证自己买得到这块地呢?

Input

本题目包含多组测试,请处理到文件结束(EOF)。每组测试占一行。
每组测试包含两个整数 $M$ 和 $N$ (含义见题目描述,$0<N$,$M<1100$)

Output

对于每组数据,在一行里按递增的顺序输出 Lele 第一次可以加的价。两个数据之间用空格隔开。
如果 Lele 在第一次无论如何出价都无法买到这块土地,就输出 "none"。

Sample Input

4 2
3 2
3 5

Sample Output

1
none
3 4 5

注意当 $M < N$ 时,先手可以一举买断,所以此时有多种开价方式。

AC代码:

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    int m, n;
    while (cin >> m >> n) {
        int r = m % (n + 1);
        if (r == 0) 
            cout << "none" << endl;
        else {
            if (n > m){
                for (int i = r; i <= n; i++) {
                    if (i == r) {
                        cout << i;
                    } else cout << " " << i;
                }
                cout << endl;
            } else {
                cout << r << endl;
            }            
        }
    }
}

威佐夫博弈

在两堆物品中轮流取物,每次可以在任意一堆取出至少一个物品或者从两堆中取出同样多的至少每堆一个物品,最后取光者胜。

以下内容假设:设当前局势为 $(x,y)$。

结论:当有$|a-b| \cdot\frac{1+\sqrt5}{2} = \min(a, b)$ 成立时,后手胜。

证明:我们先分析几个局势。

  1. 当当前局势为 $(0, 0)$,先手输。(可以看作是后手在上一局取完了)
  2. 当当前局势为 $(1, 2)$:
    • 如果先手取走 $x$ 中的 $1$ 个,那么后手就可以把 $y$ 中剩余的两个取走,这样后手胜。
    • 如果先手取走 $y$ 中的 $2$ 个,那么后手就可以把 $x$ 中剩余的一个取走,这样后手胜。
    • 如果先手在 $x$ 与 $y$ 各取走一个,那么后手就可以把 $y$ 中剩余的一个取走,这样后手胜。

前人总结出了一些先手必输的局势,有:$(0, 0)$、$(1,2)$、$(3,5)$、$(4,7)$、$(6,10)$、$(8, 13)$……将这些局势称为**“奇异局势”**。他们有如下规律:

  1. 两个数的差值成公差为 $1$ 的等差数列:$0, 1, 2, 3, 4, 5, 6\cdots n$
  2. 每种局势的第一个值总是前面局势没有出现过的最小的自然数
  3. 每种奇异局势的第一个值总是等于当前局势的差值乘上 $1.618$($\frac{1 + \sqrt 5}{2}$)并取向下约值(黄金分割率 $+1$)。

例题:HDU 2177

取(2堆)石子游戏

Problem Description

有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。如果你胜,你第1次怎样取子?

Input

输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都不大于1,000,000,且a<=b。a=b=0退出。

Output

输出也有若干行,如果最后你是败者,则为0,反之,输出1,并输出使你胜的你第1次取石子后剩下的两堆石子的数量x,y,x<=y。如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜,先输出取走相同数量的石子的情况.

Sample Input

1 2 
5 8
4 7
2 2
0 0

Sample Output

0
1
4 7
3 5
0
1
0 0
1 2

问题在于这道题还要求要输出方案。

直接想我应该怎么取比较难,不如转换成构造满足条件的局势,然后按照这个局势进行取石子。只要构造必输局势($|a-b| \cdot\frac{1+\sqrt5}{2} = \min(a, b)$ 成立)扔给对方就可以了。

#include <bits/stdc++.h>
using namespace std;
void swap(int *a, int *b) {
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
int main() {
    ios::sync_with_stdio(false);
    int a; int b;
    while(cin >> a >> b && (a || b)){
        if (b < a) {
            swap(a, b);
        }
        double r = (1.0 + sqrt(5)) / 2.0;
        int s = b - a;
        int k = floor(s * r);
        if (k == a) {
            cout << 0 << endl;
        } else {
            cout << 1 << endl;
            if (a - k == b -(k + s) && a >= k){
                cout << k << " " << k + s << endl;
            }
            for (int i = 0;; i++) {
                int newAns = floor(i * r);
                if (newAns + i > b) {
                    break;
                }
                if ((newAns == a && newAns + i < b) || (newAns < a && newAns == b) || (a == newAns + i && newAns < b)){
                    cout << newAns << " " << newAns + i << endl;
                }
            }
        }
    }
}
支付宝捐赠
请使用支付宝扫一扫进行捐赠
微信捐赠
请使用微信扫一扫进行赞赏
有 0 篇文章