SG

抽象一个状态为一个节点,状态所能到达的新状态之间有一条有向边,整个游戏构成一个有向无环图(Directed Acyclic Graph, DAG)。
每个节点是P/N-position中的一个。P(revious)意为前手胜,当前手必败,sg值为0;N(ext)意为当前手胜,sg值非0。
终点状态(T-position)是确定的(当前手败),通常sg(0)=0为P-position。若为N则被称为反nim游戏。

关于N,P状态的性质。
若到达一个子局面不存在P(所有都为N),即当前手的对方全为必胜状态,则此时当前手必败,为P;
子局面存在P,即存在一个状态使对手必败,则当前手必胜,为N。

由此定义sg函数。对于一个局面状态,sg(x)=mex{sg(x')}。mex意为第一个不出现在集合中的非负整数。
sg的取值有特定的意义。(还不是很清楚怎么说)

组合nim游戏,是指由若干独立nim游戏组合而成的组合游戏。它的状态由所有子游戏的sg值异或和给出。

SG定理

注意到获胜条件即为
(i)sg(x)=0 必败
(ii)sg(x) neq 0 必胜
而仿照之前nim游戏的思路知道通过适当的调整进到新的局面会使得必败必胜交换。
即是对状态为10001000的异或和sg状态我们可以变为00000000,使得必败态出现。而我们对sg的定义求mex即保证他可以回到比它小的任意状态。
至此sg定理。

Anti-SG

获胜条件与SG相反,故名。

  1. 决策集合为空的操作者胜。
  2. 其余规则与SG游戏一致。

SJ定理

对于任意一个Anti-SG游戏,如果定义所有子游戏的SG值为0时游戏结束,先手必胜的条件:
1、游戏的SG值为0且所有子游戏SG值均不超过1。
2、游戏的SG值不为0且至少一个子游戏SG值超过1。

//以上超多坑还不会证明,待补

HDU 1730

给出若干行,每行黑白棋各一。黑先。棋可左右移动但不可越过另外一个棋子。使得对手无法移动的一方获胜。问先手是否必胜。

注意到1°若黑白间无其他格子,则白棋只需跟着黑棋走即可,白胜。
2°若有则黑棋第一步跟到白棋后面,之后反上述过程,黑胜。
可以发现白在最优策略下绝不往远离黑方向走。否则对(1°)有变为(2°),对(2°)有维持(2°)不变。
所以就是双方对黑白棋之间的空格数做nim了。
然后一步可以取尽也无需计算sg。

码(15ms, 1404K)

#include <cstdio>
#include <cmath>
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        int ans = 0;
        while(n--)
        {
            int a, b; read(a, b);
            ans ^= abs(a - b) - 1;
        }
        puts(ans ? "I WIN!" : "BAD LUCK!");
    }
    return 0;
}

HDU 2999

给出一个集合,一次只能取出连续的并且数量是集合里的数的石子。石子有序且不同编号不相邻。使对方不能取获胜。问先手胜负。

我英语水平没救了Orz
读错题两次Orz
注意到取一段出来有可能会把石子断成两段。
然后看成是组合游戏异或就可以了Orz

码(858ms, 1428K)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1000 + 10;
int sg[maxn] = {0}, a[maxn] = {0}, n;
int calc(int x)
{
    if(~sg[x]) return sg[x];
    bool visit[maxn] = {0};
    memset(visit, 0, sizeof visit);
    for(int i = 0; i < n; i++)
    {
        if(x < a[i]) break;
        int j = x - a[i];
        visit[calc(j)] = true;
        for(int k = 1; k < j; k++)
            visit[calc(k) ^ calc(j - k)] = true;
    }
    int mex = 0; for(; visit[mex]; mex++); return sg[x] = mex;
}
int main()
{
    while(~scanf("%d", &n))
    {
        memset(sg, -1, sizeof sg); sg[0] = 0;
        for(int i = 0; i < n; i++)
            read(a[i]);
        sort(a, a + n);
        int m; read(m);
        while(m--)
        {
            int k; read(k);
            int ans = calc(k);
            puts(ans > 0 ? "1" : "2");
        }
    }
    return 0;
}

HDU 3980

给一个n个点的环,可以给其上连续m个点染色。不能染色者输。问先手胜负。

第一次会把环断成线,以后的会把线断成两部分。然后就是组合nim……
我错了负数特判还判错啦我太弱啦

码(15ms, 1960K)

#include <cstdio>
#include <cstring>
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1000 + 100;
int m;
int sg[maxn] = {0};
int calc(int n)
{
    if(n < 0) return 1;
    if(~sg[n]) return sg[n];
    int j = n - m;
    bool visit[maxn] = {0};
    for(int i = 0; i <= j; i++)
        visit[calc(i) ^ calc(j - i)] = true;
    int mex = 0; for(; visit[mex]; mex++); return sg[n] = mex;
}
int main()
{
    int t; read(t); int cnt = 1;
    while(t--)
    {
        memset(sg, -1, sizeof sg); sg[0] = 0;
        int n; read(n, m);
        printf("Case #%d: %s\n", cnt++, calc(n - m) ? "abcdxyzk" : "aekdycoin");
    }
    return 0;
}

HDU 1524

给定一个DAG。其上一些节点有棋,每次沿一条边移动。问先手胜负。

就是一个sg图,然后对每个节点sg值异或而已……

码(62ms, 1504K)

#include <cstdio>
#include <cstring>
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1000 + 1000;
struct Edge{int v, next;}edges[maxn];
int h[maxn], ecnt = 1;
void add_edge(int u, int v){edges[ecnt] = (Edge){v, h[u]}; h[u] = ecnt++;}
int sg[maxn] = {0};
int calc(int n)
{
    if(~sg[n]) return sg[n];
    bool visit[maxn] = {false};
    for(int i = h[n], v = edges[i].v; i; i = edges[i].next, v = edges[i].v)
        visit[calc(v)] = true;
    int i = 0; for(; visit[i]; i++); return sg[n] = i;
}
int main()
{
    int n, a;
    while(~scanf("%d", &n))
    {
        memset(sg, -1, sizeof sg);
        memset(h, 0, sizeof h); ecnt = 1;
        for(int i = 0; i < n; i++)
        {
            int x; read(x);
            while(x--) read(a), add_edge(i, a);
        }
        int m;
        while(read(m), m)
        {
            int ans = 0;
            while(m--) read(a), ans ^= calc(a);
            puts(ans ? "WIN" : "LOSE");
        }
    }
    return 0;
}

HDU 3094

树上cutting-edge.

有这样的性质:$$ sg(i)= \oplus_{i' \in son_i} sg(i')+1 $$
不会证(捂脸(看不懂
参见[http://wenku.baidu.com/view/70a8d6186bd97f192279e9a0.html]。

码(265ms, 3460K)

#include <cstdio>
#include <cstring>
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 2e5 + 100;
struct Edge{int v, next; } e[maxn];
int h[maxn], ecnt;
inline void add_edge(int u, int v) {e[ecnt] = (Edge){v, h[u]}; h[u] = ecnt++;}
int sg[maxn];
void dfs(int u = 1, int f = 0)
{
    for(int i = h[u], v = e[i].v; i; i = e[i].next, v = e[i].v) if(v != f)
    {
        dfs(v, u);
        sg[u] ^= (sg[v] + 1);
    }
}
int main()
{
    int t; read(t);
    while(t--)
    {
        memset(h, 0, sizeof h); ecnt = 2;
        memset(sg, 0, sizeof sg);
        int n; read(n);
        for(int k = 1, i, j; k < n; k++)
            read(i, j), add_edge(i, j), add_edge(j, i);
        dfs();
        puts(sg[1] ? "Alice" : "Bob");
    }
    return 0;
}

HDU 3590

森林cutting-edge的anti-sg。

码(0, 1440K)

#include <cstdio>
#include <cstring>
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1000 + 1000;
struct Edge{int v, next; } e[maxn];
int h[maxn], ecnt;
inline void add_edge(int u, int v) {e[ecnt] = (Edge){v, h[u]}; h[u] = ecnt++;}
int sg[maxn];
void dfs(int u = 1, int f = 0)
{
    for(int i = h[u], v = e[i].v; i; i = e[i].next, v = e[i].v) if(v != f)
    {
        dfs(v, u);
        sg[u] ^= (sg[v] + 1);
    }
}
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int ans = 0, cnt = 0;
        while(n--)
        {
            memset(h, 0, sizeof h); ecnt = 2;
            memset(sg, 0, sizeof sg);
            int m; read(m);
            for(int k = 1, i, j; k < m; k++)
                read(i, j), add_edge(i, j), add_edge(j, i);
            dfs();
            ans ^= sg[1];
            if(sg[1] > 1) cnt++;
        }
        puts((ans && cnt) || (!ans && !cnt) ? "PP" : "QQ");
    }
    return 0;
}

标签: 博弈论, sg

添加新评论