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

时间：2021-10-14 23:33:09

算法笔记

参考资料：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,,sizeof(SG));

    for(int i=;i<=n;i++)

    {

        memset(S,false,sizeof(S));

        for(int j=;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 = , M = 5e3 + ;

int a[N], sg[M], T, n;

int main() {

    for (int i = ; i < M; ++i) sg[i] = i;

    scanf("%d", &T);

    while(T--) {

        scanf("%d", &n);

        for (int i = ; i <= n; ++i) scanf("%d", &a[i]);

        int cnt = , s = ;

        for (int i = ; i <= n; ++i) {

                if(sg[a[i]] > ) ++cnt;

                s ^= sg[a[i]];

        }

        if((!cnt && !s) || (cnt && s)) printf("John\n");

        else printf("Brother\n");

    }

    return ;

}

树上删边博弈：

定理：叶子节点的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 + ;

vector<int> g[N];

int T, n, u, v;

int sg(int u, int o) {

    int res = ;

    for (int i = ; i < g[u].size(); ++i) {

        int v = g[u][i];

        if(v != o) res ^= sg(v, u) + ;

    }

    return res;

}

int main() {

    scanf("%d", &T);

    while(T--) {

        scanf("%d", &n);

        for (int i = ; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);

        if(sg(, )) printf("Alice\n");

        else printf("Bob\n");

        for (int i = ; i <= n; ++i) g[i].clear();

    }

    return ;

}

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 = ;

vector<int> g[N];

int t, n, m, u, v;

int stk[N], sg[N], low[N], dfn[N], cnt = , top = ;

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 = ; 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 = ;

        while(stk[top] != u) {

            vv[stk[top]] = false;

            vis[stk[top--]] = false;

            ++c;

        }

        vis[stk[top--]] = false;

        ++c;

        if(c >  && c%) sg[u] ^= ;

    }

    for (int i = ; i < g[u].size(); ++i) {

        int v = g[u][i];

        if(v == o) continue;

        if(vv[v]) sg[u] ^= sg[v]+;

    }

}

int main() {

    while(~scanf("%d", &t)) {

        int s = ;

        while(t--) {

            scanf("%d %d", &n, &m);

            for (int i = ; i < m; ++i) {

                scanf("%d %d", &u, &v);

                g[u].pb(v);

                g[v].pb(u);

            }

            tarjan(, );

            s ^= sg[];

            for (int i = ; i <= n; ++i) low[i] = dfn[i] = sg[i] = vis[i] = vv[i] = ;

            cnt = top = ;

            for (int i = ; i <= n; ++i) g[i].clear();

        }

        if(s) printf("Sally\n");

        else printf("Harry\n");

    }

    return ;

}

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 + ;

int nowx;

struct circle {

    int x, y, r;

}p[N];

double Y(int id, int ty) {

    if(ty == ) 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*];

void dfs(int u, int o) {

    sg[u] = ;

    for (int i = ; i < g[u].size(); ++i) {

        int v = g[u][i];

        if(v != o) {

            dfs(v, u);

            sg[u] ^= sg[v] + ;

        }

    }

}

int main() {

    p[].x = p[].y = ;

    p[].r = ;

    s.insert({, });

    s.insert({, });

    scanf("%d", &T);

    while(T--) {

        scanf("%d", &n);

        for (int i = ; i <= n; ++i) scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].r);

        for (int i = ; i <= n; ++i) {

            t[i].fi.fi = p[i].x - p[i].r;

            t[i].fi.se = ;

            t[i].se = i;

            t[n+i].fi.fi = p[i].x + p[i].r;

            t[n+i].fi.se = ;

            t[n+i].se = i;

        }

        sort(t+, t++*n);

        for (int i = ; i <= *n; ++i) {

            nowx = t[i].fi.fi;

            int id = t[i].se;

            node tmp = {id, };

            if(t[i].fi.se == ) {

                auto l = s.lower_bound(tmp); --l;

                auto r = s.upper_bound(tmp);

                if((*l).id == (*r).id) {

                    dp[id] = dp[(*l).id] + ;

                    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, });

                s.insert({id, });

            }

            else {

                s.erase({id, });

                s.erase({id, });

            }

        }

        dfs(, );

        if(sg[]) printf("Alice\n");

        else printf("Bob\n");

        for (int i = ; i <= n; ++i) g[i].clear(), sg[i] = fa[i] = dp[i] = ;

    }

    return ;

}

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 = ;

vector<int> g[N];

int t, n, u, v;

int dfs(int u, int o) {

    int sg = ;

    for (int i = ; i < g[u].size(); ++i) {

        int v = g[u][i];

        if(v != o) sg ^= dfs(v, u) + ;

    }

    return sg;

}

int main() {

    while(~scanf("%d", &t)) {

        int cnt = , s = ;

        while(t--) {

            scanf("%d", &n);

            for (int i = ; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);

            int sg = dfs(, );

            s ^= sg;

            if(sg > ) ++cnt;

            for (int i = ; i <= n; ++i) g[i].clear();

        }

        if((cnt && s) || (!cnt && !s)) printf("PP\n");

        else printf("QQ\n");

    }

    return ;

}

相关文章