精华内容
下载资源
问答
  • sg函数的一些

    2017-06-04 20:49:59
    模板1如下(SG打表): //f[]:可以取走的石子个数  //sg[]:0~n的SG函数值  //hash[]:mex{}  int f[K],sg[N],hash[N];  void getSG(int n)  {   memset(sg,0,sizeof(sg));   for(int i=1; i; i++) {

    模板1如下(SG打表):

    //f[]:可以取走的石子个数  
    //sg[]:0~n的SG函数值  
    //hash[]:mex{}  
    int f[K],sg[N],hash[N];  
    void getSG(int n)  
    {  
            memset(sg,0,sizeof(sg));  
            for(int i=1; i<=n; i++) {  
                    memset(hash,0,sizeof(hash));  
                    for(int j=0; f[j]<=i && j < k; j++) //k是f[]的有效长度  
                            hash[sg[i-f[j]]]=1;  
                    for(int j=0; ; j++) {   //求mes{}中未出现的最小的非负整数  
                            if(hash[j]==0) {  
                                    sg[i]=j;  
                                    break;  
                            }  
                    }  
            }  
    }  

    模板2如下(dfs):

    //注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍  
    //n是集合s的大小 S[i]是定义的特殊取法规则的数组  
    int s[N],sg[N],n;  
    int getSG(int x)  
    {  
            if(sg[x]!=-1)  
                    return sg[x];  
            bool vis[M];  
            memset(vis,0,sizeof(vis));  
            for(int i=0; i<n; i++) {  
                    if(x>=s[i])  
                            vis[getSG(x-s[i])]=1;  
            }  
            for(i=0;; i++)  
                    if(!vis[i]) {  
                            sg[x]=i;  
                            break;  
                    }  
            return sg[x];  
    }  

    例一: hdu 1536 S-Nim

    题意:首先输入K 表示一个集合的大小 之后输入集合 表示对于这对石子只能去这个集合中的元素的个数

    之后输入 一个m 表示接下来对于这个集合要进行m次询问

    之后m行 每行输入一个n 表示有n个堆 每堆有n1个石子 问这一行所表示的状态是赢还是输 如果赢输入W否则L

    思路:对于n堆石子 可以分成n个游戏 之后把n个游戏合起来就好了

    代码:

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #include <math.h>
    using namespace std;
    typedef long long LL;
    const int MAXN = 108;
    int a[MAXN*MAXN], pre[MAXN], k;
    
    void init() {
        int f[MAXN];
        for(int i = 1; i <= 10000; i++) {
            a[i] = 0;
            memset(f, 0, sizeof(f));
            for(int j = 1; j <= k && pre[j] <= i; j++)
                f[a[i-pre[j]]] = 1;
            for(int j = 0; ; j++)
                if (!f[j]) {
                    a[i] = j;
                    break;
                }
        }
    }
    
    int main() {
        int  m;
        //freopen("in.txt", "r", stdin);
        while (scanf("%d", &k) && k) {
            for(int i = 1; i <= k; i++)
                scanf("%d", pre+i);
            sort(pre+1, pre+k+1);
            init();
            scanf("%d", &m);
            while (m--) {
                int n;
                scanf("%d", &n);
                int res = 0;
                for(int i = 1; i <= n; i++) {
                    int t;
                    scanf("%d", &t);
                    res ^= a[t];
                }
                if (res) printf("W");
                else printf("L");
            }
            puts("");
        }
        return 0;
    }

    例二:
    Gym - 101128GGame of Cards

    题意:有n堆扑克牌,两个人轮流玩游戏,游戏规则:

    先选一堆扑克牌,然后拿走堆顶0-k张,剩余的堆顶那一张牌上是几就必须再拿走几张,当某一方无牌可拿或者剩余张数不够必须拿走的张数时则该方输

    代码:

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #include <math.h>
    using namespace std;
    typedef long long LL;
    const int MAXN = 1008;
    int a[MAXN], k, val[MAXN];
    
    void init() {
        int f[22];
        for(int i = 1; i <= 1000; i++) {
            a[i] = 0;
            memset(f, 0, sizeof(f));
            for(int j = 0; j <= k; j++)
            if (i-j-val[i-j] >= 0)//这里注意一下就好了;
                f[a[i-j-val[i-j]]] = 1;
            for(int j = 0; ; j++)
                if (!f[j]) {
                    a[i] = j;
                    break;
                }
        }
    }
    
    int main() {
        int m;
        //freopen("in.txt", "r", stdin);
        scanf("%d%d", &m, &k);
        val[0] = 1;
        int res = 0;
        while (m--) {
            int n;
            scanf("%d", &n);
            for(int i = 1; i <= n; i++)
                scanf("%d", val+i);
            init();
            res ^= a[n];
        }
        if (res) printf("Alice can win.\n");
        else printf("Bob will win.\n");
        return 0;
    }


    sg函数巧用

    hdu 1729  Stone Game

    1、设当前的箱子容量为si,求出一个t满足:t + t * t < si,如果当前箱子里有ci颗石头,

    1、ci > t 则必胜;

    2、ci == t 则必败;

    3、ci < t不能确定,将t作为si递归调用函数。

    当满足ci > t时,return si - ci 作为当前状态的sg值。因为:

    如图:

    当ci在si点时,为有向图的端点,出度为0,也就是必败点,所以sg值为0;

    当ci 位于si - 1时,ci的端点可能的sg值构成的集合为{0},所以当前sg值 为1;

    当ci 位于si - 2 时,ci的端点可能的sg值构成的集合为{0, 1},所以当前的sg值为2;

    可得,ci所在位置的sg值为si - ci;

    代码:

    //#include<bits/stdc++.h>
    #include <iostream>
    #include <string>
    #include <queue>
    #include <map>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    using namespace std;
    typedef long long LL;
    const int MAXN = 1000008;
    
    int sg(int c, int s) {
        int q = sqrt(s);
        while (q*(q+1) >= s) q--;
        if (c > q) return s-c;
        else return sg(c, q);//和暴力不一样有点小灵活
    }
    
    int main() {
        int n, p = 1;
        while (scanf("%d", &n) && n) {
            printf("Case %d:\n", p++);
            int res = 0;
            while (n--) {
                int s, c;
                scanf("%d%d", &s, &c);
                res ^= sg(c, s);
            }
            if (res) puts("Yes");
            else puts("No");
        }
        return 0;
    }

    sg 水水的;

    hdu 1730 Northcott Game

    要理解sg函数啊

    代码:

    //#include<bits/stdc++.h>
    #include <iostream>
    #include <string>
    #include <queue>
    #include <map>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    using namespace std;
    typedef long long LL;
    const int MAXN = 1000008;
    
    int main() {
        int n, m;
        while (~scanf("%d%d", &n, &m)) {
            int res = 0;
            while (n--) {
                int s, c;
                scanf("%d%d", &s, &c);
                res ^= int(abs(s-c)-1);
            }
            if (res) puts("I WIN!");
            else puts("BAD LUCK!");
        }
        return 0;
    }


    hdu 2524 A Chess Game

    题意:给一些点和有向边,组成一个有向无环图(不止一个头结点,因为这个wa一次.....);在一些点上放一些棋子,2个人进行游戏,每次进行的操作是根据有向边来移动一个棋子;直到没有棋子移动,那个人就输了;

    题解:明显的sg函数

    代码:

    //#include<bits/stdc++.h>
    #include <iostream>
    #include <string>
    #include <queue>
    #include <map>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <vector>
    using namespace std;
    typedef long long LL;
    const int MAXN = 1008;
    int sg[MAXN], adjList[MAXN][MAXN], adjN[MAXN];
    int n;
    
    int dfs(int k) {
        int num[MAXN] = {0};
        if (sg[k]) return sg[k];
        for(int i = 0; i < adjN[k]; i++) {
            num[dfs(adjList[k][i])] = 1;
        }
        for(int i = 0; ; i++)
            if (!num[i]) return sg[k] = i;
    }
    
    int main() {
        //freopen("in.txt", "r", stdin);
        while (~scanf("%d", &n)) {
            memset(sg, 0, sizeof(sg));
            for(int i = 0; i < n; i++) {
                scanf("%d", adjN+i);
                for(int j = 0; j < adjN[i]; j++) {
                    scanf("%d", &adjList[i][j]);
                }
            }
            for(int i = 0; i < n; i++)
                dfs(i);
            int m;
            while(scanf("%d", &m) && m) {
                int res = 0;
                while(m--) {
                    int t;
                    scanf("%d", &t);
                    res ^= sg[t];
                }
                if (res) puts("WIN");
                else puts("LOSE");
            }
        }
        return 0;
    }


    展开全文
  • SG函数模板总结

    2020-02-13 07:52:59
    把kkk堆石子的博弈分解成kkk个子问题再把它们的 SG\text{SG}SG 函数值异或起来,sg[i]sg[i]sg[i]表示iii个石子的 SG\text{SG}SG 函数值,记忆化搜索即可,注意:搜索过程中算mexmexmex时visvisvis的大小就是操作集合...

    S-Nim

    HDU 1536

    应该是最板的一道题了 q w q qwq qwq

    k k k堆石子的博弈分解成 k k k个子问题再把它们的 SG \text{SG} SG 函数值异或起来, s g [ i ] sg[i] sg[i]表示 i i i个石子的 SG \text{SG} SG 函数值,记忆化搜索即可,注意:搜索过程中算 m e x mex mex v i s vis vis的大小就是操作集合的大小。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int M = 10005;
    int read()
    {
        int x=0,flag=1;char c;
        while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
        while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
        return x*flag;
    }
    int n,m,k,f[105],sg[M];
    int get(int x)
    {
        if(x==0) return 0;
        if(sg[x]!=-1) return sg[x];
        bool vis[105]={};
        for(int i=1;i<=n && f[i]<=x;i++)
            vis[get(x-f[i])]=1;
        for(int i=0;;i++)
            if(!vis[i])
                return sg[x]=i;
    }
    int main()
    {
        while(~scanf("%d",&n) && n)
        {
            memset(sg,-1,sizeof sg);
            for(int i=1;i<=n;i++)
                f[i]=read();
            sort(f+1,f+1+n);
            m=read();
            while(m--)
            {
                k=read();
                int flag=0;
                for(int i=1;i<=k;i++)
                    flag^=get(read());
                if(flag) putchar('W');
                else putchar('L');
            }
            puts("");
        }
    }

    A New Tetris Game(2)

    点此看题

    很暴力的一道题了,我们直接把图搞成字符串然后拿去跑 SG \text{SG} SG函数。

    注意每一行后面要插入一个特殊字符,复杂度就别问我了(你觉得我算的出来吗? ),感性理解,状态数不会很多 ,然后就贴一个我的代码。

    #include <cstdio>
    #include <iostream>
    #include <map>
    using namespace std;
    int read()
    {
        int x=0,flag=1;char c;
        while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
        while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
        return x*flag;
    }
    int n,r,c;char g[55][55];
    map<string,int> sg;
    string _str()
    {
        string s;
        for(int i=0;i<r;i++)
        {
            s+=g[i];
            s+='*';
        }
        return s;
    }
    int get()
    {
        string x=_str();
        if(sg.count(x)) return sg[x];
        int vis[55]={};
        for(int i=1;i<r;i++)
            for(int j=1;j<c;j++)
                if(g[i][j]=='0' && g[i-1][j]=='0' && g[i][j-1]=='0' && g[i-1][j-1]=='0')
                {
                    g[i][j]=g[i-1][j]=g[i][j-1]=g[i-1][j-1]='1';
                    vis[get()]=1;
                    g[i][j]=g[i-1][j]=g[i][j-1]=g[i-1][j-1]='0';
                }
        for(int i=0;;i++)
            if(!vis[i])
                return sg[x]=i;
    }
    int main()
    {
        while(~scanf("%d",&n))
        {
            int flag=0;
            while(n--)
            {
                r=read();c=read();
                for(int i=0;i<r;i++) scanf("%s",g[i]);
                flag^=get();
            }
            if(flag) puts("Yes");
            else puts("No");
        }
    }
    

    Nim游戏(hihocoder)

    点此看题

    还是把原问题 n n n个子问题,考虑 SG \text{SG} SG函数,设 s g [ i ] sg[i] sg[i] i i i堆石子的 SG \text{SG} SG函数值,转移如下:
    s g [ i ] = m e x { s g [ j ] , s g [ j ] ⊕ s g [ j − i ] } sg[i]=mex\{sg[j],sg[j]\oplus sg[j-i]\} sg[i]=mex{sg[j],sg[j]sg[ji]}然后就是打表找规律下面给出我打的表:

    k     0 1 2 3 4 5 6 7 8 9 10 11 12sg(k) 0 1 2 4 3 5 6 8 7 9 10 12 11

    规律很容易看出来,贴个代码 q w q qwq qwq

    #include <cstdio>
    int read()
    {
        int x=0,flag=1;
        char c;
        while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
        while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
        return x*flag;
    }
    int n,ans;
    int main()
    {
        n=read();
        for(int i=1;i<=n;i++)
        {
            int x=read();
            if(x%4==3) x++;
            else if(x%4==0) x--;
            ans^=x;
        }
        if(ans) puts("Alice");
        else puts("Bob");
    }
    
    展开全文
  • SG函数详解

    2020-09-22 14:42:56
    SG函数详解关于概念必胜点和必败点必胜点和必败点的性质组合游戏SG函数的分析与推导取石子问题Sprague-Grundy定理(SG定理):SG函数小习题 简介: sg函数和sg定理是公平组合游戏中的重要组成部分,这篇文章是结合...


    简介:
    sg函数和sg定理是公平组合游戏中的重要组成部分,这篇文章是结合博客(末尾会贴博客链接)和我之前写博弈论题目的总结与反思,因为之前并没有系统的学习sg函数,所以做博弈论的题目可谓是一波三折,可以说学习sg函数的相关内容加深了我对博弈论的理解,让我对博弈论题目有了一个系统的思考。这篇博客是一篇小小的总结,以后提高最重要的方法还是需要多刷题。

    关于概念

    必胜点和必败点

    这个在我之前推导博弈论的题目时就有了比较深刻的概念和印象,对于必胜点的推导与总结是博弈论的必经之路。
    P点:必败点,换而言之,就是谁处于此位置,则在双方操作正确的情况下必败。
    N点:必胜点,处于此情况下,双方操作均正确的情况下必胜。

    必胜点和必败点的性质

    1、所有终结点是 必败点 P 。(我们以此为基本前提进行推理,换句话说,我们以此为假设)
    2、从任何必胜点N 操作,至少有一种方式可以进入必败点 P。
    3、无论如何操作,必败点P 都只能进入 必胜点 N。

    组合游戏

    在竞赛中,组合游戏的题目一般有以下特点

    题目描述一般为

    1. A,B 2人做游戏
    2. A B交替进行某种游戏规定的操作,每操作一次,选手可以在有限的操作(操作必须合法)集合中任选一种。
    3. 对于游戏的任何一种可能的局面,合法的操作集合只取决于这个局面本身,不取决于其它因素(跟选手,以前的所有操作无关)
    4. 如果当前选手无法进行合法的操作,则为负

    SG函数的分析与推导

    取石子问题

    我们以取石子问题为例
    有1堆n个的石子,每次只能取{ 1, 3, 4 }个石子,先取完石子者胜利,那么各个数的SG值为多少?

    这题非常直白的问你sg的值是多少?但是我们如果抛开这个sg不看,仔细观察这个题面,你可以总结出一些很明显的特征
    1.2人的公平游戏
    2.交替操作
    3.操作方法一样
    4.无法操作的时候为负(这点其实非常重要,在后面的题目中有涉及到)
    我们发现这其实就是一个模型,就像二分图,dp那些题目都有一个固定的模型,我们解决这道题目就必须找出模型里面的要素,上面的四个要素便是博弈论或者说是公平组合游戏中最重要的四个要素。
    到这里我们就需要了解SG函数的概念了

    Sprague-Grundy定理(SG定理):

    游戏和的SG函数等于各个游戏SG函数的Nim和。这样就可以将每一个子游戏分而治之,从而简化了问题。而Bouton定理就是Sprague-Grundy定理在Nim游戏中的直接应用,因为单堆的Nim游戏 SG函数满足 SG(x) = x。

    SG函数

    首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的最小非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

    对于任意状态 x , 定义 SG(x) = mex(S),其中 S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为 SG(da),SG(db),SG(dc),那么SG(x) = mex{SG(da),SG(db),SG(dc)}。 这样 集合S 的终态必然是空集,所以SG函数的终态为 SG(x) = 0,当且仅当 x 为必败点P时

    下面这里就是介绍这道题目的思路(贴得别人写的思路):
    博客链接:链接
    SG[0]=0,f[]={1,3,4},

    x=1 时,可以取走1 - f{1}个石子,剩余{0}个,所以 SG[1] = mex{ SG[0] }= mex{0} = 1;

    x=2 时,可以取走2 - f{1}个石子,剩余{1}个,所以 SG[2] = mex{ SG[1] }= mex{1} = 0;

    x=3 时,可以取走3 - f{1,3}个石子,剩余{2,0}个,所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;

    x=4 时,可以取走4- f{1,3,4}个石子,剩余{3,1,0}个,所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;

    x=5 时,可以取走5 - f{1,3,4}个石子,剩余{4,2,1}个,所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;

    以此类推…

    x 0 1 2 3 4 5 6 7 8…

    SG[x] 0 1 0 1 2 3 2 0 1…

    由上述实例我们就可以得到SG函数值求解步骤,那么计算1~n的SG函数值步骤如下:

    1、使用 数组f 将 可改变当前状态 的方式记录下来。

    2、然后我们使用 另一个数组 将当前状态x 的后继状态标记。

    3、最后模拟mex运算,也就是我们在标记值中 搜索 未被标记值 的最小值,将其赋值给SG(x)。

    4、我们不断的重复 2 - 3 的步骤,就完成了 计算1~n 的函数值。
    代码:

    //f[N]:可改变当前状态的方式,N为方式的种类,f[N]要在getSG之前先预处理
    //SG[]:0~n的SG函数值
    //S[]:为x后继状态的集合
    int f[N],SG[MAXN],S[MAXN];
    void  getSG(int n){
        int i,j;
        memset(SG,0,sizeof(SG));
        //因为SG[0]始终等于0,所以i从1开始
        for(i = 1; i <= n; i++){
            //每一次都要将上一状态 的 后继集合 重置
            memset(S,0,sizeof(S));
            for(j = 0; f[j] <= i && j <= N; j++)
                S[SG[i-f[j]]] = 1;  //将后继状态的SG函数值进行标记
            for(j = 0;; j++) if(!S[j]){   //查询当前后继状态SG值中最小的非零值
                SG[i] = j;
                break;
            }
        }
    }
    
    

    小习题

    接下来就可以做一个小练习:
    杭电小习题
    代码:

    #include<bits/stdc++.h>
    using namespace std;
    const int N = 1000;
    typedef long long ll;
    int n ,m , p;
    ll f[N+10];
    ll s[N+10];
    ll sg[N+10];
    int main(){
        f[1] = 1;
        f[0] = 1;
        for(int i = 2;i <= N ;i ++ ){
            f[i] = f[i-1] + f[i-2];
        }
        memset(sg , -1, sizeof sg);
        sg[0] = 0;
        for(int i = 1;i <= N ; i ++){
            memset(s,0,sizeof s);
            for(int j = 0 ; f[j] <= i && j <= N ;j ++){
                s[sg[i-f[j]]] = 1;
            }
            for(int j = 0 ; ; j ++){
                if(!s[j]){
                    sg[i] = j;
                    break;
                }
            }
        }
    
        while(~scanf("%d %d %d" ,&n ,&m ,&p)){
            if(n + m + p == 0)break;
            if(sg[n] ^ sg[m] ^ sg[p] ){
                puts("Fibo");
            }
            else puts("Nacci");
        }
    }
    
    
    展开全文
  • 这篇文章写的很,值得转发。 首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。 例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。 对于一个给定...

    这篇文章写的很好,值得转发。



    首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。


    例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

    对于一个给定的有向无环图,定义关于图的每个顶点的Sprague-Grundy函数g如下:g(x)=mex{ g(y) | y是x的后继 },这里的g(x)即sg[x]

    例如:取石子问题,有1堆n个的石子,每次只能取{1,3,4}个石子,先取完石子者胜利,那么各个数的SG值为多少?

    sg[0]=0,f[]={1,3,4},

    x=1时,可以取走1-f{1}个石子,剩余{0}个,mex{sg[0]}={0},故sg[1]=1;

    x=2时,可以取走2-f{1}个石子,剩余{1}个,mex{sg[1]}={1},故sg[2]=0;

    x=3时,可以取走3-f{1,3}个石子,剩余{2,0}个,mex{sg[2],sg[0]}={0,0},故sg[3]=1;


    x=4时,可以取走4-f{1,3,4}个石子,剩余{3,1,0}个,mex{sg[3],sg[1],sg[0]}={1,1,0},故sg[4]=2;

    x=5时,可以取走5-f{1,3,4}个石子,剩余{4,2,1}个,mex{sg[4],sg[2],sg[1]}={2,0,1},故sg[5]=3;

    以此类推.....

    x 0 1 2 3 4 5 6 7 8....

    sg[x] 0 1 0 1 2 3 2 0 1...

    计算从1-n范围内的SG值。

    f(存储可以走的步数,f[0]表示可以有多少种走法)

    f[]需要从小到大排序

    1.可选步数为1~m的连续整数,直接取模即可,SG(x) = x % (m+1);

    2.可选步数为任意步,SG(x) = x;

    3.可选步数为一系列不连续的数,用GetSG()计算


    上述是自jumping_frog博文的建立SG模板时的解释。


    HDU 1848,有了上述方法,就简单了。 首先建立f数组,就是Fibonacci数列。 然后预处理求1000以内的SG数组,通过模板:

    // 获得SG数组函数模板,t代表f数组的个数,n代表要求的sg数组上限
    // f数组就是能取的个数(对于此题就是Fibonacci数列
    // 有时,对于t已知就不需要单独传参
    void get_sg(int t,int n)
    {
        int i,j;
        memset(sg,0,sizeof(sg));
        for(i=1;i<=n;i++)
        {
            memset(mex,0,sizeof(mex));
            // 对于属于g(x)后继的数置1
            for( j=1 ;j<=t && fib[j]<=i ;j++ )
                mex[sg[i-fib[j]]]=1;
            // 找到最小不属于该集合的数
            for( j=0 ; j<=n ; j++ )
                if(!mex[j])
                    break;
            sg[i] = j;
        }
    }


    SG的题,很多都可以看成是多个Nim博弈。 然后就可以分析奇异态,非奇异态来确定答案了。
    然后就是此题完整代码:


    下面这是我的AC代码(不是原作者的):


    /************************************************
    ┆  ┏┓   ┏┓ ┆  
    ┆┏┛┻━━━┛┻┓ ┆
    ┆┃       ┃ ┆
    ┆┃   ━   ┃ ┆
    ┆┃ ┳┛ ┗┳ ┃ ┆
    ┆┃       ┃ ┆
    ┆┃   ┻   ┃ ┆
    ┆┗━┓    ┏━┛ ┆
    ┆  ┃    ┃  ┆      
    ┆  ┃    ┗━━━┓ ┆
    ┆  ┃  AC代马   ┣┓┆
    ┆  ┃           ┏┛┆
    ┆  ┗┓┓┏━┳┓┏┛ ┆
    ┆   ┃┫┫ ┃┫┫ ┆
    ┆   ┗┻┛ ┗┻┛ ┆     
    ************************************************ */
    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    int fib[50], SG[1005], mex[1005];
    int getSG(int n){
    	int i, j;
    	SG[0] = 0;
    	for(i = 1; i <= n; ++i){
    		memset(mex, 0, sizeof mex);
    		for(j = 1; fib[j] <= i; ++j){
    			mex[SG[i-fib[j]]] = 1;
    		}
    		for(j = 0; ; ++j){
    			if(!mex[j]) break;
    		}
    		SG[i] = j;
    	}
    	return SG[n];
    }
    int main(){
    	ios::sync_with_stdio(0);
    	int n, m, p, i, j, mx;
    	fib[1] = 1; fib[2] = 2;
    	for(i = 2; fib[i] < 1000; ++i){
    		fib[i+1] = fib[i] + fib[i-1];
    	}
    	while(cin >> n >> m >> p){
    		if(n == 0 && m == 0 && p == 0) break;
    		if(getSG(n)^getSG(m)^getSG(p)) cout << "Fibo" << endl;
    		else cout << "Nacci" << endl;
    	}
    	return 0;
    }

    原文:  http://www.2cto.com/kf/201405/297489.html


    展开全文
  • 【博弈 —— SG函数详解+例题解析】

    千次阅读 2019-04-09 19:55:42
    SG函数解析: 博弈游戏的本质是一个有向图游戏,每个状态(局面)是一个图中一个节点,每个节点可以通向其他多个状态,而每个节点又由nnn个子游戏组成。 如下图所示,y1y_1y1​、y2y_2y2​、y3y_3y3​…都是一个状态...
  • sg函数入门

    2015-07-24 20:10:49
    poj 2311: 题意: ...用sg函数来找必胜态和必败态,然后类似记忆化搜索,不断往下找。 代码: #include #include #include #include #include #include #include #include #include #inc
  • ACWing 893. 集合-Nim游戏   容斥原理和博弈论视频课 给定n堆石子以及一个由k个不同正整数构成的数字集合S。...现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子...SG函数的第一个,还要多刷题。
  • 好久没写博弈论的了,写几道复习一下,博弈论SG主要由两大部分组成:SG函数和SG定理 SG(x)=mex(S),其中S是x的后继状态的SG函数值集合,mex(S)表示不在S内的最小非负整数。 SG定理:游戏和的SG函数等于各子游戏SG...
  • SG函数

    2018-03-21 17:05:00
    为什么要学习这个呢?因为每次看到题解的第一句话总是这种的: ...首先呢,可以把这个做一做,是一个很的博弈。题目链接:HDOJ5754 HDOJ5754题解 这个,解释了博弈的很经典一个思路
  • 题解:因为要多个串到达尾部把T串,我们可以在某点到达的状态建成一个图然后 ,就是多个有向图的SG函数 #include #include #include #include #include #include #include #include #include #include #include #...
  • 博弈论 SG函数

    万次阅读 多人点赞 2016-04-12 21:36:28
    别被文章长度吓到,学会博弈(SG)只用看前1/10。 鉴于讲明白博弈要写好多字,于是找了些论文拼凑,对疑难点加了注释并配上“美图”助解。 Nim游戏 重点结论:对于一个Nim游戏的局面(a1,a2,...,an),它是P-position当...
  • 博弈 - SG函数和SG定理

    2017-03-30 20:42:44
    在介绍SG函数和SG定理之前我们先介绍介绍必胜点与必败点吧. 必胜点和必败点的概念:  P点:必败点,换而言之,就是谁处于此位置,则在双方操作正确的情况下必败。  N点:必胜点,处于此情况下,双方操作均正确...
  • = -1: return labels[x] connect = set() # 用于记录连接的sg值 for t in takes: if x - t >= 0: connect.add(sg(x - t)) i = 0 while True: if i not in connect: labels[x] = i break i += 1 return labels[x] res...
  • SG函数题目

    2019-04-18 22:41:09
    关于SG函数:https://www.cnblogs.com/ECJTUACM-873284962/p/6921829.html # include # include using namespace std ; # define MAXN 1000 + 5 # define N 20 int f [ N ] , SG [ MAXN ]...
  • 在介绍SG函数和SG定理之前我们先介绍介绍必胜点与必败点吧. 必胜点和必败点的概念:  P点:必败点,换而言之,就是谁处于此位置,则在双方操作正确的情况下必败。  N点:必胜点,处于此情况下,双方...
  • 题目大意:已知一次可拿个数的种类;求出先手是否胜利,若...SG函数模板:#include const int N = 10008; int a[110],sg[N],f[N]; void sgt(int *a,int y,int z) { int i,j; memset(sg,0,sizeof(sg)); for(i=1;i;i
  • 博弈论与SG函数

    2020-03-02 21:53:53
    裸的打表SG函数,求sg函数的模板。 将输入的三个值对应的sg函数进行异或,异或值为0则后手胜,否则先手胜。 # include using namespace std ; const int N = 1010 ; bool vis [ N ] ; int a , b ...
  • 在介绍SG函数和SG定理之前我们先介绍介绍必胜点与必败点吧. 必胜点和必败点的概念:  P点:必败点,换而言之,就是谁处于此位置,则在双方操作正确的情况下必败。  N点:必胜点,处于此情况下,双方操作均正确...
  • //注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1边 //不需要每求一个数的SG就初始化一边 int SG[10100],n,m,s[102],k;//k是集合s的大小 S[i]是定义的特殊取法规则的数组 int dfs(int x...
  • = -1: return labels[stone] connect = set() for i in range(stone): for j in range(i+1): connect.add(sg(i)^sg(j)) i = 0 while True: if i not in connect: labels[stone] = i break i += 1 return labels...
  • Nim游戏和SG函数

    2018-05-22 21:15:49
    那么我们可以发现,对于此游戏的一种局面,ICG上的多个sg函数的值,如果看做多个石堆的话,就相当于一个nim游戏!我们来一步步推导: 首先来个引理,s≥sg(x)s≥sg(x),这个用归纳法证,应该说简单。 如果...
  • 题目大意:给出n张牌,两...题目分析:简单sg打表,先预处理出sg表,然后O(1)查询即可 #include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio...
  • sg函数模板

    2018-10-29 17:51:51
    首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的...对于一个给定的有向无环图,定义关于图的每个顶点的Sprague-Grundy函数g如下:g(x)=mex{ g(y) | y是x的后继 },这里...
  • memset(sg,-1,sizeof(sg)) ; memset(in,0,sizeof(in)) ; for(int i = 0 ; i ; ++i) { int m; scanf("%d",&m); for(int j = 0 ; j ; ++j) { int temp; ; scanf("%d",&temp) ; in...
  • 博弈论中SG函数的解释与运用

    千次阅读 2016-04-21 21:52:39
    为了正确地玩游戏和我们需要推广P-状态和N-状态,它就是Sprague-Grudy函数(或者简称为g函数) 4、Sprague-Grudy定理: 令N = {0, 1, 2, 3, ...} 为自然数的集合。Sprague-Grundy 函数给游戏中的每...
  • SG函数: 首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。 这一步应该是非常简单的,就是定义了新的运算为mex...
  • SG函数和SG定理【详解】

    千次阅读 2017-07-25 09:23:49
    在介绍SG函数和SG定理之前我们先介绍介绍必胜点与必败点吧. 必胜点和必败点的概念:  P点:必败点,换而言之,就是谁处于此位置,则在双方操作正确的情况下必败。  N点:必胜点,处于此情况下,双方操作均正确...
  • hdu 1536 S-Nim (SG函数经典

    千次阅读 2013-08-10 15:47:42
    题目大意:有一个集合S,里面有k个数,玩取石子游戏,每次只能取S中的一个数,玩n次,分别判断先手胜负。...昨天一直听别人说SG什么的,不知道是什么,今天去学了一下,挺厉害的~~ 自己第一道SG题

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,480
精华内容 1,792
热门标签
关键字:

sg函数好题