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

相关推荐

  • Python中获取当前日期的格式

    Python中获取当前日期的格式

    2021年11月26日
  • java分割String字符串成list

    java分割String字符串成list示例:Stringsn=“1234,567,8910”;List<String>snList=Arrays.asList(sn.split(“,”));

  • ALLuxio_Alluxio公司怎么样

    ALLuxio_Alluxio公司怎么样一、什么是AlluxioAlluxio(之前名为Tachyon)是世界上第一个以内存为中心的虚拟的分布式存储系统。它统一了数据访问的方式,为上层计算框架和底层存储系统构建了桥梁。应用只需要连接Alluxio即可访问存储在底层任意存储系统中的数据。此外,Alluxio的以内存为中心的架构使得数据的访问速度能比现有常规方案快几个数量级。在大数据生态系统中,Alluxio介于计算框架(如Apache…

    2022年10月22日
  • Scanner的hasNext()方法

    Scanner的hasNext()方法一、实例代码importjava.util.*;publicclassScannerKeyBoardTest{publicstaticvoidmain(String[]args){System.out.println("请输入若干单词,以空格作为分隔");Scannersc=newScanner(System…

  • quota什么意思(binding quota)

    什么是quotaquota的用途quota的一般作用对象quota的限制quota的使用重新挂devsdb1文件系统并添加usrquotagrpquota参数添加用户组和用户生成quota配置文件启动quota功能修改quota配置文件配置文件内容如下修改权限再写入一个大文件切换quota2用户修改警告时间查看quota1的quota信息查询quota2的quota信息

  • RestSharp_简单搜索怎么使用

    RestSharp_简单搜索怎么使用C#使用restsharp调用接口

发表回复

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

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