博弈论

sg函数(Sprague-Garundy)

如何求

要弄明白sg函数首先要明白什么是 必败态 N-position(g(x)一般是 mex{})

对于一个g(x)=0的顶点x，它的所有后继y都满足g(y)!=0。 N

对于一个g(x)!=0的顶点，必定存在一个后继y满足g(y)=0。 P

比如定义一个游戏

有一堆石头个数 为n 两人轮流可以 1~3个

直到不能取的人失败

当n==0时必败 或者说n%4==0时都是必败的

有向无环图上面定义一个sg函数的

从小到大标记 sg函数

x 0 1 2 3 4 5 6 7 8 9 10 11
g(x) 0 1 2 3 0 1 2 3 0 1 2 3 ]

代码实现

//打表
int f[N],sg[N],hash[N];     
void getSG(int n)
{
    bitset<N>vis;
   	vector<int>sg(n+1);
    for(int i=1;i<=n;i++)
    {
      	vis.reset();
        for(int j=1;f[j]<=i;j++)
            vis[sg[i-f[j]]]=1;//f[i]为实现方法
       while(vis[sg[i]])	   //求mes{}中未出现的最小的非负整数
       		sg[i]++;
    }
}

//dfs
int s[110],sg[10010],n;
int SG_dfs(int x)
{
    if(sg[x]!=-1)
        return sg[x];
    bool vis[110];
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)
    {
        if(x>=s[i])
        {
            SG_dfs(x-s[i]);
            vis[sg[x-s[i]]]=1;
        }
    }
    int e;
    for(i=0;;i++)
        if(!vis[i])
        {
            e=i;
            break;
        }
    return sg[x]=e;
}

SG定理

nim

经典nim博弈嗷

如果有n个游戏的话

总游戏 的sg值 为

大概就是这样子啦

阶梯nim博弈

对奇数阶的石头进行 Nim，偶数阶的石头对结果不影响。

为什么是奇数阶？

因为最后石子都要到 0 上，从 1 到 0 就是最后一步，这是从奇数阶到偶数阶，

所以认为从奇数阶上移到偶数阶上相当于取一次石子才能保证状态一致。

寒冬信使2

题意

有长度为n 的只含 b 和w 的字符串(<=10)

现有 两个操作

不能操作的人先输掉

问是否有必胜策略

思路

将 w 看成1 b看出0

然后打表 sg函数 (1~1<<10)应该很小

AC代码

#include<bits/stdc++.h>
#define endl "\n"
#define pii pair<int,int>
#define pll pair<long long,long long>
#define fi first
#define sc second
#define int128 __int128
typedef long long ll;
const double PI = acos(-1.0), eps = 1e-8, EI = exp(1.0);
const int inf32 = 0x3f3f3f3f;
const ll mod = 1000000007, inf64 = 0x3f3f3f3f3f3f3f3f;
const int N = 1e7 + 50, maxn = 1e6 + 50;
using namespace std;
void solve()
{
    vector<int>sg(1<<10+1);
    bitset<105>vis;
    for (int i = 1; i < (1 << 10); i++)
    {
        vis.reset();
        for (int j = 0; j < 10; j++)
        {
            if (i >> j & 1)
            {
                if (j == 0)
                    vis[sg[i ^ (1 << j)]] = true;
                else
                {
                    for (int k = 0; k < j; k++)
                        vis[sg[i ^ (1 << j) ^ (1 << k)]] = true;
                }
            }
        }
        while (vis[sg[i]])
        {
            sg[i]++;
        }
    }
    int t; cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        string str;
        cin >> str;
        int st = 0;
        for (int i = 0; i <n; i++)
        {
            if (str[i] == 'w')
            {
                st|= (1 << i);
            }
        }
        if (sg[st])
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(); cout.tie(0);
    //int t; cin >> t; while (t--)
    solve();
    return 0;
}

高手过招

题意

有个 20*n 的棋盘

每行 有mi个棋子

可以进行以下操作

对于一个棋子，能将它向右移动一格，如果右边有棋子，则向右跳到第一个空格，如果右边没有空格，则不能移动这个棋子，如果所有棋子都不能移动，那么将输掉这场比赛。

思路1

用st打表 1<<20 大概 1e7左右

AC代码1

#include<bits/stdc++.h>
#define endl "\n"
#define pii pair<int,int>
#define pll pair<long long,long long>
#define fi first
#define sc second
#define int128 __int128
typedef long long ll;
const double PI = acos(-1.0), eps = 1e-8, EI = exp(1.0);
const int inf32 = 0x3f3f3f3f;
const ll mod = 1000000007, inf64 = 0x3f3f3f3f3f3f3f3f;
const int N = 1e7 + 50, maxn = 1e6 + 50;
using namespace std;
vector<int>sg(1 << 20);
bitset<105>vis;
void fun(int x)
{
        vis.reset();
        int temp = 1, nxt = -1;
        for (int i = 0; i < 20; i++)
        {
            temp = 1 << i;
            if (x & temp)
            {
                if ((x | (temp >> 1)) != x)
                    vis[sg[x ^ temp ^ (temp >> 1)]] = true;
                else if (nxt!=-1)
                    vis[sg[x ^ temp ^ (1 << (nxt))]] = true;
            }
            else
                nxt = i;
        }
        while (vis[sg[x]])
        {
            sg[x]++;
        }
   
}
void solve()
{
    int n, m;
    cin >> n ;
    int st = 0;
    int ans = 0;
    while (n--)
    {
        cin >> m;
        st = 0;
        for (int i = 1; i <= m; i++)
        {
            int x;
            cin >> x;
            st|=(1 << (20 - x));
        }
        ans ^= sg[st];
    }
    if (ans)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(); cout.tie(0);
    for(int i=0;i<(1<<20);i++)
        fun(i);
    int t; cin >> t; while (t--)
    solve();
    return 0;
}

思路2

变形 的阶梯nim 博弈( )

将相互连接的棋子看作一个阶梯的

在 第21个格子加上一个棋子

进行 阶梯nim 博弈