SG函数

SG函数

对于任意状态 x , 定义 SG(x) = mex(S),其中 S 是 x 后继状态的 SG 函数值的集合。如 x 有三个后继状态分别为 SG(a),SG(b),SG(c),那么 SG(x)=mex{SG(a),SG(b),SG(c)}。 这样集合 S 的终态必然是空集,所以SG函数的终态为 SG(x)=0,当且仅当 x 为必败点P时。
注:
mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
SG 定理:游戏和的SG函数等于各个游戏SG函数的Nim和。
Nim和 :各个数相异或的结果

//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;
        }
    }
}

尼姆博弈(Nimm Game):

尼姆博弈指的是这样一个博弈游戏:有任意堆物品,每堆物品的个数是任意的,双方轮流从中取物品,每一次只能从一堆物品中取部分或全部物品,最少取一件,取到最后一件物品的人获胜。
结论:把每堆物品数全部异或起来,如果得到的值为0,那么先手必败,否则先手必胜。
SG定理:
图片说明 ,先手必胜。
图片说明 ,先手必败。

新玩法

  1. 取到最后一件物品的人失败。
    结论:当每堆石子数量都不超过 1 时,n 为奇数先手必败。剩下的就和尼姆博奕的结论一致。
  2. 可以把一堆石子分成不相等的两堆,不能操作为败
void getSG(int n) {
//    memset(sg, 0, sizeof(sg));
    for(int i = 1; i <= n; ++ i) {
        memset(s, 0, sizeof(s));                            //S[]:为x后继状态的集合
        for(int j = 1; j*2 < i; ++ j) s[sg[j]^sg[i-j]] = 1; // sg定理
        while(s[sg[i]]) ++sg[i];                            // mex(...)
    }
}
  1. 尼姆博奕先手必胜,第一步有几种走法。
    结论:把一堆石头移出游戏,去掉一部分再加入游戏,看此时 sg 是否能为零,即 (ans^a[i]) < a[i]。
    long long ans = 0;
    for(int i = 1; i <= n; ++ i) {
        scanf("%lld", &a[i]);
        ans ^= a[i];
    }
    int res = 0;
    for(int i = 1; i <= n; ++ i) {
        if ((ans^a[i]) < a[i]) res ++;
    }

巴什博弈

只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取 1 个,最多取 m 个,最后取光者得胜。
结论:若 n % (m+1) == 0,则先手必败,否则先手必胜

高级玩法

取石子的数量,不是 1~m 内的连续数字,而是只能在数组 a 中选。
方法一:定义 P 为先手必败,N 为先手必胜,P 的后继全是 N,N 的后继包含 P,依次类推寻找周期即可。
方法二:sg函数打表。

void getSG(int n, int t[], int m) { // 石块数量,拿去规则
//    memset(sg, 0, sizeof(sg));
    for(int i = 1; i <= n; ++ i) {
        memset(s, 0, sizeof(s));                                      //S[]:为x后继状态的集合
        for(int j = 1; t[j] <= i && j <= m; ++ j) s[sg[i-t[j]]] = 1;  //将后继状态的SG函数值进行标记
        while(s[sg[i]]) ++sg[i];                           // mex(...)
    }
}

威佐夫博奕(Wythoff's game)

有两堆各若干个物品,两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品,规定每次至少取一个,至多不限,最后取光者胜利。
结论:若 a == int((b-a)*1.618),则先手必败,否则先手必胜。

斐波那契数列

只有一堆n个物品,两个人轮流从这堆物品中取物,规则是先手不能在第一次把所有的石子取完,之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)。约定取走最后一个石子的人为赢家。
结论:若 n 为斐波那契数,先手必败,否则先手必胜。

数学 文章被收录于专栏

关于acm竞赛数论的个人笔记

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-23 14:10
柴子木:找个工作你还发上脾气了🤣
点赞 评论 收藏
分享
来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务