【算法】博弈论

已经看了好几次博弈论了,前几次没记最后都忘了,所以这次试着记一下,以后忘了还可以顺着记忆找回来
日常安利 [学习笔记] (博弈论)Nim游戏和SG函数
博弈论一般都是从nim游戏开始的,这是博弈论中最为经典的问题之一。一般都是给你n堆石子,两个人轮流去拿一堆里面的石子,最少1个最多全拿走,然后问你先手必胜还是必败
这个东西是有结论的,我们可以把每一堆作为一个子游戏去考虑的话,分别求出他们的sg函数,之后求一个异或和,如果异或和为0必败,异或和不为0必胜
为什么?我们这么考虑,假设有n堆石子,现在轮到后手操作,之前先手把异或和变为了非0,既异或和\(x \neq 0\),那么一定存在一堆石子\(a_{i}\)的,他的最高位和\(x\)最高位都为1,那么我们可以让这堆石子变小,变成\(a_{i} xor x\)(\(a_{i} xor x\)一定小于\(a_{i}\)的),那么我们既消掉了最高位,又消掉了后面那些1,所以异或和又变为了0。因此无论怎么改变对于先手异或和都为0,这个过程肯定不是无限的,所以最后到先手手上的时候一定必败
那么sg函数是什么
sg函数就是说给你一些数,其中最小的没有出现的非负整数即为sg函数
那么对于一个空集,\(sg(x) = 0\)
因此对于\(sg(x) \neq 0\)的情况来说,在他的集合里面一定存在一个数为0;反之亦然
这和博弈论有什么关系
引入接下来两个定义
P-position:在当前的局面下,先手必败
N-position:在当前的局面下,先手必胜
那么我们将nim游戏看成一张图,对于每次转移都建边,sg函数的集合就是他能到达的点的sg值。对于一个必胜态,一定sg值不为0,否则为0
那么结合上面的来看我们可以通过在这个图上移动实现必胜态必败态之间的转换
这就是sg值和博弈论的关系
那么sg值怎么求?
对于从1-m的转移,\(sg(x)=x%(m+1\))
对于全部都能取的情况,\(sg(x)=x\)
对于不连续的转移,我们需要背模板
先写一个第二种情况的(其实与第一种情况是一样的)
luogu P2197 nim游戏

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int t, n, lx;

int main()
{
    re(t);
    while(t --)
    {
        re(n), lx = 0;
        for(ri i = 1, j; i <= n; i ++)
            re(j), lx ^= j;
        if(lx > 0)
            printf("Yes\n");
        else
            printf("No\n");
    }
}

除了nim游戏还有一些模型,比如二分图博弈
二分图博弈的思想就是先将博弈转化成二分图最大匹配,这个时候如果二分图完美匹配的话,先手必胜,否则先手就可以通过选择匹配点获得胜利
难就难在所有可能匹配点的都是答案,我习惯写dinic来判断二分图最大匹配,这个时候怎么做?
从源点出发找出所有源点能到达的,并且本来与源点也相连的点,汇点也这么干一次(目前不理解,就先这么咕咕咕)
luogu P4055 [JSOI2009] 游戏

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int n, m, t, tot = -1, cnt, head[10010], he[10010], pos[110][110], px[10010], py[10010];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, de[10010], q[10010];

int ax[10010], ay[10010];

char lx;

bool mmp[110][110], flag[10010], col[10010];

struct in
{
    int to, ne, co;
}ter[100010];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

inline bool bfs()
{
    int hh = 0, tt = 0;
    q[0] = 0, memset(de, 0, sizeof(de)), de[0] = 1;
    while(hh <= tt)
    {
        int qaq = q[hh ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co > 0 && de[to] == 0)
                q[++ tt] = to, de[to] = de[qaq] + 1;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co > 0 && de[to] == de[no] + 1)
        {
            int rt = dfs(to, min(fl, ter[i].co));
            if(rt > 0)
            {
                ter[i].co -= rt, ter[i ^ 1].co += rt; return rt;
            }
        }
    }
    return 0;
}

void dfss(int no, int f)
{
    flag[no] = 1;
    if(col[no] == f)
        ax[++ cnt] = no;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co == f && flag[to] == 0)
            dfss(to, f);
    }
}

int main()
{
    re(n), re(m), memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
    {
        while((lx = getchar()) != '#' && lx != '.');
        for(ri j = 1; j <= m; j ++)
        {
            mmp[i][j] = (lx == '.');
            if(mmp[i][j] > 0)
                pos[i][j] = ++ cnt, px[cnt] = i, py[cnt] = j;
            lx = getchar();
        }
    }
    t = ++ cnt;
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
            if(mmp[i][j] == 1)
            {
                if((i + j) & 1)
                {
                    build(0, pos[i][j], 1), col[pos[i][j]] = 1;
                    for(ri k = 0; k < 4; k ++)
                    {
                        int tx = i + dx[k], ty = j + dy[k];
                        if(tx < 1 || tx > n || ty < 1 || ty > m || mmp[tx][ty] == 0)
                            continue;
                        build(pos[i][j], pos[tx][ty], 1);
                    }
                }
                else
                    build(pos[i][j], t, 1);
            }
    int nu = 0, x = 0;
    while(bfs())
    {
        memcpy(he, head, sizeof(he));
        while(x = dfs(0, 1000000007))
            nu += x;
    }
    if((nu << 1) == cnt - 1)
    {
        printf("LOSE"); return 0;
    }
    printf("WIN\n");
    cnt = 0, col[t] = 1;
    dfss(0, 1), memset(flag, 0, sizeof(flag)), dfss(t, 0);
    sort(ax + 1, ax + 1 + cnt);
    for(ri i = 1; i <= cnt; i ++)
        if(ax[i] != 0 && ax[i] != t)
            printf("%d %d\n", px[ax[i]], py[ax[i]]);
}

博弈论还可以打表,luogu P2148 [SDOI2009]E&D
这个题目首先你可以暴力去算,对于a+b来说,他一定能够化成c+d的形式,我们按照按照a来算,然后每次枚举被拆成了哪两个数,异或起来,然后这样得到了sg值集合。我们发现,a+b异或起来之后的答案,就是从最低位开始数第一个0出现在第几位上?所以我们可以logn去算?完了?
整个题目就是通过打表找规律实现的?蛇皮操作啊

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int t, n, lx, ly, ans;

inline int mex(int x)
{
    int rt = 0;
    while(x & 1)
        x >>= 1, rt ++;
    return rt;
}

int main()
{
    re(t);
    while(t --)
    {
        re(n), ans = 0;
        for(ri i = 1; i <= n; i += 2)
            re(lx), re(ly), ans ^= mex((lx - 1) | (ly - 1));
        printf("%s\n", ans ? "YES" : "NO");
    }
}

博弈论还可以脑洞清奇一点,不使用sg函数。luogu P4101 [HEOI2014] 人人尽说江南好
这个题目脑洞实在是太过于清奇了,清奇的妙不可言
首先可以这么考虑,合并次数为奇数先手必胜,偶数后手必胜,那么两个人都会尽可能向着自己想要的方向去发展,结果就是……这两个人把比赛拉到最长(感性理解下)
之后我们要考虑,如果最长的合并次数是偶数次,那么一定后手能必胜
分开讨论下,当\(n \leq m\)时,这种情况最后肯定能合成一堆qwq,我们管这个比较大的堆叫【大堆】,假如说现在轮到先手操作,先手还没动,这个时候最长合并次数为偶数次,那么先手有两种可能性,把后面一个堆丢进大堆里面,这样后手再丢一个小堆进去,或者把后面两个堆合成一个,那么后手就可以把这个合成的直接丢进去。无论怎么做,后手都能保证每轮完了之后,大堆的石子会增加两个,那么合并次数也会-2,一直保持为偶数。直到最后先手合无可合。
那么\(n > m\)呢?我们假设\(n = m + 1\),并且m是奇数,最后合成次数最多的情况一定是\((m, 1)\)对于前m个,合成次数为偶数,我们就像刚才那么操作,最后一个1直接不用管。所以后手必赢。同样的我们可以把情况扩展到\(n = km + b\)这种情况。前k个\(m\)一样合并,后面也一样。
所以我们只需要算出合并次数就可以了
[BZOJ3609]-[Heoi2014]人人尽说江南好-神分析+博弈 dalao写的好qwq

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int t, n, m;

int main()
{
    re(t);
    while(t --)
    {
        re(n), re(m);
        lo x = (n / m) * (m - 1) + (n % m ? n % m - 1 : 0);
        printf("%d\n", (x & 1) ? 0 : 1);
    }
}

发表评论

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