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

算法笔记–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

代码:

算法笔记--sg函数详解及其模板
算法笔记--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 = 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

思路:树上删边博弈

代码:

算法笔记--sg函数详解及其模板
算法笔记--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 = 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缩边双转换成树上删边博弈

代码:

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

#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

思路:

圆扫描线+树上删边博弈

代码:

算法笔记--sg函数详解及其模板
算法笔记--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 = 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和树上删边结合起来,大概是看了论文后才出的题(雾

代码:

算法笔记--sg函数详解及其模板
算法笔记--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;
}

View Code

 

转载于:https://www.cnblogs.com/widsom/p/7172386.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108318.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Python中numpy数组的拼接、合并

    Python中numpy数组的拼接、合并Python中numpy数组的合并有很多方法,如np.append()np.concatenate()np.stack()np.hstack()np.vstack()np.dstack()其中最泛用的是第一个和第二个。第一个可读性好,比较灵活,但是占内存大。第二个则没有内存占用大的问题。假设有两个数组a,b分别为:&gt;&gt;&gt;aarray([0,…

  • Vim 基本配置和经常使用的命令

    Vim 基本配置和经常使用的命令

  • 系统运维架构 DevOps

    系统运维架构 DevOps一套大而全的系统架构体系与具体落地方案 写在最前面上次参加DBAplus举办的敏捷运维峰会时,一个兄弟的提问一直萦绕耳边,由于时间有限没有进行深入的交流,甚是遗憾。那个问题是:你们公司的IT系统架构是怎样的?又如何具体落地?采用了哪些开源或是商业的技术?其实之前也写过或是做过一些关于系统架构的分享,或多或少的个人或其它限制,总觉得未能尽兴,留有遗憾。因此经过最近一个多月的总结和梳理…

  • DIV ID用途_纸的用途

    DIV ID用途_纸的用途我是超级链接这个例子是一个很简单的超级链接。用到了DIV,实际上DIV就相当于一个肉眼看不到盒子,盒子里边可以放入很多的文字、图片、flash等等。而盒子里边内容的样式,就全部靠DIV的id所对应的

  • cshtml的美化

    cshtml的美化c#webapp美化工作美化工作更改css框架css在cshtml中的位置网上的bootstrap模板资源1.从网站上下载模板2.使用模板更多的资料美化工作默认大家已经掌握了MVC框架的概念和使用方式,本文章只将如何在MVC基础上进行简单的美化工作更改css框架css在cshtml中的位置对html语言有所了解的各位应该知道,css一般写在头中,也就是<head></head>所在的位置中,在cshtml中也是这样。注意看MVC框架的_Layout.cshtml中的

  • ViewPager基本用法

    ViewPager基本用法step1:在layout中定义一个ViewPager组件。step2:在Activity中获取ViewPager的引用。step3:为ViewPager设置适配器,step4:为ViewPa

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号