算法笔记-sg函数详解及其模板

大家好，又见面了，我是全栈君。

算法笔记

参考资料：https://wenku.baidu.com/view/25540742a8956bec0975e3a8.html

sg函数大神详解：http://blog.csdn.net/luomingjun12315/article/details/45555495

sg[i]定义，从i走一步能到达的j的sg[j]以外的最小值，那么从sg函数值为x的状态出发，我们能转移到sg值为0,1,…,x-1的状态

对于某个人来说，0是他的必败态，sg[0] = 0

我们从这个状态出发，用dp求sg函数的值

sg[n] = 0，表示必败，否则，表示必胜

如果sg[n] > 0，说明肯定能转移到必败态，则必胜

如果sg[n] = 0, 说明无论怎么转移都是必胜态，则必败

模板：

int f[N],SG[N];
bool S[M];
void getSG(int n)
{
    memset(SG,0,sizeof(SG));
    for(int i=1;i<=n;i++)
    {
        memset(S,false,sizeof(S));
        for(int j=1;f[j]<=i&&j<M;j++)
        {
             S[SG[i-f[j]]]=true;
        }
        while(S[SG[i]]) SG[i]++;
    }
}

例题：http://www.cnblogs.com/widsom/p/7171428.html

　　　http://www.cnblogs.com/widsom/p/7170891.html

sg函数拓展：

反sg博弈：

先手必胜：（所有单一局面sg值都不超过1&&总局面sg值为0） || （存在一个单一局面sg值超过1&&总局面sg值不为0）

否则后手必胜。

HDU 1907

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";

const int N = 55, M = 5e3 + 5;
int a[N], sg[M], T, n;
int main() {
    for (int i = 0; i < M; ++i) sg[i] = i;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        int cnt = 0, s = 0;
        for (int i = 1; i <= n; ++i) {
                if(sg[a[i]] > 1) ++cnt;
                s ^= sg[a[i]];
        }
        if((!cnt && !s) || (cnt && s)) printf("John\n");
        else printf("Brother\n");
    }
    return 0;
}

View Code

树上删边博弈：

定理：叶子节点的sg值为0，其他节点u的sg[u]值等于它儿子v的(sg[v]+1)的亦或和。

图上删边博弈：

将偶环缩成点，奇环缩成一个点加一条边，就可以转换成树上删边博弈了。

具体证明看最上面的链接。

HDU 3094

思路：树上删边博弈

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";

const int N = 1e5 + 5;
vector<int> g[N];
int T, n, u, v;
int sg(int u, int o) {
    int res = 0;
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if(v != o) res ^= sg(v, u) + 1;
    }
    return res;
}
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for (int i = 1; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);
        if(sg(1, 1)) printf("Alice\n");
        else printf("Bob\n");
        for (int i = 1; i <= n; ++i) g[i].clear();
    }
    return 0;
}

View Code

POJ 3710

思路：tarjan缩边双转换成树上删边博弈

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";

const int N = 105;
vector<int> g[N];
int t, n, m, u, v;
int stk[N], sg[N], low[N], dfn[N], cnt = 0, top = 0;
bool vis[N], vv[N];//vv标记环上的点是否被删掉
void tarjan(int u, int o) {
    dfn[u] = low[u] = ++cnt;
    stk[++top] = u;
    vv[u] = vis[u] = true;
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if(v == o) continue;
        if(!dfn[v]) tarjan(v, u), low[u] = min(low[u], low[v]);
        else if(vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]) {
        int c = 0;
        while(stk[top] != u) {
            vv[stk[top]] = false;
            vis[stk[top--]] = false;
            ++c;
        }
        vis[stk[top--]] = false;
        ++c;
        if(c > 1 && c%2) sg[u] ^= 1;
    }
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if(v == o) continue;
        if(vv[v]) sg[u] ^= sg[v]+1;
    }
}
int main() {
    while(~scanf("%d", &t)) {
        int s = 0;
        while(t--) {
            scanf("%d %d", &n, &m);
            for (int i = 0; i < m; ++i) {
                scanf("%d %d", &u, &v);
                g[u].pb(v);
                g[v].pb(u);
            }
            tarjan(1, 1);
            s ^= sg[1];
            for (int i = 1; i <= n; ++i) low[i] = dfn[i] = sg[i] = vis[i] = vv[i] = 0;
            cnt = top = 0;
            for (int i = 1; i <= n; ++i) g[i].clear();
        }
        if(s) printf("Sally\n");
        else printf("Harry\n");
    }
    return 0;
}

View Code

HDU 5299

思路：

圆扫描线+树上删边博弈

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";

const int N = 2e4 + 5;
int nowx;
struct circle {
    int x, y, r;
}p[N];
double Y(int id, int ty) {
    if(ty == 0) return p[id].y - sqrt(p[id].r*1.0*p[id].r - (nowx-p[id].x)*1.0*(nowx-p[id].x));
    else return p[id].y + sqrt(p[id].r*1.0*p[id].r - (nowx-p[id].x)*1.0*(nowx-p[id].x));
}
struct node {
    int id, ty;
    bool operator < (const node &rhs) const {
        if(id == rhs.id) return ty < rhs.ty;
        else return Y(id, ty) < Y(rhs.id, rhs.ty);
    }
};
set<node> s;
vector<int> g[N];
int T, n, dp[N], fa[N], sg[N];
piii t[N*2];
void dfs(int u, int o) {
    sg[u] = 0;
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if(v != o) {
            dfs(v, u);
            sg[u] ^= sg[v] + 1;
        }
    }
}
int main() {
    p[0].x = p[0].y = 0;
    p[0].r = 100000;
    s.insert({
     
     0, 0});
    s.insert({
     
     0, 1});
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].r);
        for (int i = 1; i <= n; ++i) {
            t[i].fi.fi = p[i].x - p[i].r;
            t[i].fi.se = 0;
            t[i].se = i;
            t[n+i].fi.fi = p[i].x + p[i].r;
            t[n+i].fi.se = 1;
            t[n+i].se = i;
        }
        sort(t+1, t+1+2*n);
        for (int i = 1; i <= 2*n; ++i) {
            nowx = t[i].fi.fi;
            int id = t[i].se;
            node tmp = {id, 1};
            if(t[i].fi.se == 0) {
                auto l = s.lower_bound(tmp); --l;
                auto r = s.upper_bound(tmp);
                if((*l).id == (*r).id) {
                    dp[id] = dp[(*l).id] + 1;
                    fa[id] = (*l).id;
                }
                else if(dp[(*l).id] >= dp[(*r).id]) {
                    dp[id] = dp[(*l).id];
                    fa[id] = fa[(*l).id];
                }
                else {
                    dp[id] = dp[(*r).id];
                    fa[id] = fa[(*r).id];

                }
                g[fa[id]].pb(id);
                s.insert({id, 1});
                s.insert({id, 0});
            }
            else {
                s.erase({id, 1});
                s.erase({id, 0});
            }
        }
        dfs(0, 0);
        if(sg[0]) printf("Alice\n");
        else printf("Bob\n");
        for (int i = 0; i <= n; ++i) g[i].clear(), sg[i] = fa[i] = dp[i] = 0;
    }
    return 0;
}

View Code

HDU 3590

思路：

出题人真是个机灵鬼，将反-sg和树上删边结合起来，大概是看了论文后才出的题（雾

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";

const int N = 105;
vector<int> g[N];
int t, n, u, v;
int dfs(int u, int o) {
    int sg = 0;
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if(v != o) sg ^= dfs(v, u) + 1;
    }
    return sg;
}
int main() {
    while(~scanf("%d", &t)) {
        int cnt = 0, s = 0;
        while(t--) {
            scanf("%d", &n);
            for (int i = 1; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);
            int sg = dfs(1, 1);
            s ^= sg;
            if(sg > 1) ++cnt;
            for (int i = 0; i <= n; ++i) g[i].clear();
        }
        if((cnt && s) || (!cnt && !s)) printf("PP\n");
        else printf("QQ\n");
    }
    return 0;
}