博弈论

博弈论两道题

牛客—处女座和小姐姐

分析：

作者：儒生雄才1
链接：https://ac.nowcoder.com/discuss/152781?type=101&order=0&pos=1&page=1
来源：牛客网

显然处女座十分牛逼，因此输出“cnznb”即可
咳咳……至于正确的做法。首先因为每次在右边砍掉一个头就相当于在左边会多出来一个头，所以可以把每𝑛次操作看作一轮，每轮的操作都是从01串右边向左边对每个位置在原位依次进行操作。我们考虑这种做法，从右到左我们首先看到1就把他变成0，0的话让他随机，直到第一次出现有0变成了1的情况。如果没有出现这种情况那么这个串已经符合了要求，如果有0变成1发生，那么在这之后的1我们都继续变成1。这样一轮结束之后，这个01串所表示的二进制数的的大小一定是严格增加了的（因为虽然你可能把一些1变成了0但是有一个高位的0变成了1）而这个二进制数的大小是有限的，因此在有限步内一定可以把这串数变成全0串。

HDU6312—GAME

参考：

https://blog.csdn.net/qq_37025443/article/details/81214403

上面两大题都是输出一个结果，无论输入的是什么。这只是博弈论之一，博弈论还有其他的内容

博弈论常见类型

参考:https://blog.csdn.net/lgdblue/article/details/15809893

巴什博弈

问题模型：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个，最后取光者得胜。
解决思路：当n=m+1时，由于一次最多只能取m个，所以无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜，所以当一方面对的局势是n%(m+1)=0时，其面临的是必败的局势。所以当n=（m+1)*r+s，（r为任意自然数，s≤m)时,如果先取者要拿走s个物品，如果后取者拿走x（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。
变形：条件不变，改为最后取光的人输。
结论：当一方面对的局势是n%(m+1)=0时，其面临的是必败的局势

具体来说，当m大于等于n时肯定是先手赢，所以这是必胜点，而m = n+1就是必败点了，因为这时你至少加1，至多加n，达不到n+1，而后手肯定能补满到n+1，如果m是（n+1）的倍数，那么也是必败点；因为后手只是每次保持m是（n+1）的倍数，最后一轮，肯定又出现n+1的必败点。相反m不是（n+1）的倍数，那么就是必胜点，因为我们只要加价让剩余价格是（n+1）的倍数，就可以到达必败点

HDU2188—悼念512汶川大地震遇难同胞——选拔志愿者

巴什博弈应用题

/*
 *Submit Time	2019-01-27 15:25:37	
 */
#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    int n ,m;
    while(t--)
    {
        cin >> n >> m;
        if(n % (m + 1) == 0)
            cout << "Rabbit" << endl;
        else
            cout << "Grass" << endl;
    }
    return 0;
}

HDU2149—Public Sale

参考:http://blog.sina.com.cn/s/blog_a16dd6d101013lha.html

结果可以分三种情况：

当n>=m，即先手第一次可以加的价格大于等于田地的成本价，此时可以加的价格依次为m~n；②
当m%(n+1)==0时，后手必赢，即此时输出“none”；
当m%(n+1)!=0时，题目要求输出第一次报价，枚举每一种可能的出价，只要能使结果满足m%(n+1) == 0，就是一次合理的出价

/*
 *Submit Time	2019-01-27 16:06:11	
 */
#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n ,m;
    while(cin >> m >> n)
    {
        if(m % (n + 1) == 0)
            cout << "none" << endl;
        else
        {
            int ans[10000];
            int num = 0;
            for(int i = 1; i <= n; i++)
            {
                //第二种情况或者保持给对手留下（m+1）的倍数，就能最后获胜
                if(m-i<=0 || (m-i)%(n+1)==0) 
                    ans[num++] = i;
            }
            //注意题目输出要求，不能多余空格，不然报PE
            for(int i = 0; i < num-1; i++)
                cout << ans[i] << " ";
            cout << ans[num - 1] << endl;
        }
    }
    return 0;
}

威佐夫博奕

问题模型：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

证明可参考：

https://blog.csdn.net/qq_41311604/article/details/79980882

HDU1527—取石子游戏

裸威佐夫博奕题

/*
 *Submit Time	2019-01-27 18:08:52
 */
#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    while(cin >> n >> m)
    {
        int MIN = n;
        if(n > m)
            MIN = m;
        double r = (sqrt(5.0)+1)/2;
        int num = (int)(abs(n - m) * r);
        if(num == MIN)
            cout << "0" << endl;
        else
            cout << "1" << endl;
    }
    return 0;
}

斐波那契博弈(Fibonacci Nim)

参考:https://blog.csdn.net/dgq8211/article/details/7602807

有一堆个数为n(n>=2)的石子，游戏双方轮流取石子，规则如下：

先手不能在第一次把所有的石子取完，至少取1颗；
之后每次可以取的石子数至少为1，至多为对手刚取的石子数的2倍。

约定取走最后一个石子的人为赢家，求必败态。

结论：当n为Fibonacci数的时候，必败。

f[i]：1,2,3,5,8,13,21,34,55,89……

HDU2516—取石子游戏

斐波那契博弈裸题

/*
 *Submit Time	2019-01-27 18:18:24
 */
#include <iostream>
#include <cmath>
using namespace std;

const int MAXN = 1E2;
int f[MAXN];

void init()
{
    f[0] = f[1] = 1;
    for(int i=2;i<MAXN;i++)
        f[i] = f[i-1] + f[i-2];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    init();
    int n;
    while(cin >> n && n)
    {
        int flag = 0;
        for(int i = 0; i < MAXN; i++)
        {
            if(n == f[i])
            {
                flag = 1;
                break;
            }
        }
        if(flag)
            cout << "Second win" << endl;
        else
            cout << "First win" << endl;
    }
    return 0;
}

尼姆博弈

问题模型：有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜

可参考:https://blog.csdn.net/tianweidadada/article/details/80091063

HDU1847—Good Luck in CET-4 Everybody!

裸尼姆博弈题

参考:https://blog.csdn.net/a1214034447/article/details/78872034

/*
 *Submit Time	2019-01-27 18:33:03
 */
#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    while(cin >> n && n)
    {
        if(n%3==0)
            cout << "Cici" << endl;
        else
            cout << "Kiki" << endl;
    }
    return 0;
}