当前位置: 首页 > article >正文

acwing算法基础之数学知识--Nim游戏和集合Nim游戏

目录

  • 1 基础知识
  • 2 模板
  • 3 工程化

1 基础知识

(一)
Nim游戏: n n n堆物品,每堆有 a i a_i ai个,两个玩家轮流取走任意一堆的任意个物品,但不能不取。取走最后一个物品的人获胜。

结论:如果这n个数异或之和为0,则先手必败,否则先手必胜。
代码表示为,

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int res = 0;
    while (n--) {
        int x;
        cin >> x;
        res = res ^ x;
    }
    
    if (res) puts("Yes");
    else puts("No");
    
    return 0;
}

(二)
集合Nim游戏:在Nim游戏的基础上,对每次取走的石子做了限制,每次取走的石子数必须在集合 S S S内。判断是否先手必胜。

抽象建模为,
有向图游戏和SG函数:在一个有向无环图中,只有一个起点,上面有一个棋子,两个玩家轮流沿有向边推动棋子,不能走的玩家判负。

定义mex函数的值为,不属于集合S中的最小非负整数,即:
m e x ( S ) = m i n { x }   ( x ∉ S , x ∈ N ) mex(S)=min\{x\} \ (x\notin S, x\in N) mex(S)=min{x} (x/S,xN)
例如mex({0,2,3}) = 1, mex({1,2}) = 0。

对于状态 x x x和它的所有 k k k个后继状态 y 1 , y 2 , ⋯   , y k y_1,y_2,\cdots,y_k y1,y2,,yk,定义SG函数:
S G ( x ) = m e x { S G ( y 1 ) , S G ( y 2 ) , ⋯   , S G ( y k ) } SG(x)=mex\{SG(y_1), SG(y_2), \cdots, SG(y_k)\} SG(x)=mex{SG(y1),SG(y2),,SG(yk)}

而对于由n个有向图组成的组合游戏,设它们的起点分别为 s 1 , s 2 , ⋯   , s n s_1,s_2,\cdots,s_n s1,s2,,sn,则有定理:当且仅当这 n n n个数 S G ( s 1 ) , S G ( s 2 ) , ⋯   , S G ( s n ) SG(s_1),SG(s_2),\cdots,SG(s_n) SG(s1),SG(s2),,SG(sn)的异或和不为0时,这个游戏是先手必胜的,否则,是先手必败的。

C++代码如下,

#include <iostream>
#include <unordered_set>
#include <cstring>

using namespace std;

const int N = 110, M = 1e4 +10;
int n, m;
int s[N]; //每次可以取的石子数目
int f[M]; //这堆有x个石子,求sg[x]的值

int sg(int x) {
    if (f[x] != -1) return f[x];
    
    unordered_set<int> S;//x能走到的结点的sg函数值
    for (int i = 0; i < n; ++i) {
        if (x - s[i] >= 0) S.insert(sg(x-s[i]));
    }
    
    for (int i = 0; ; ++i) {
        if (S.count(i) == 0) {
            f[x] = i;
            break;
        }
    }
    return f[x];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> s[i];
    
    int res = 0;
    memset(f, -1, sizeof f);
    cin >> m;
    while (m--) {
        int x;
        cin >> x;
        res ^= sg(x);
    }
    
    if (res) puts("Yes");
    else puts("No");
    
    return 0;
}

2 模板

暂无。。。

3 工程化

题目1:拆分Nim游戏,取走一堆,放回两堆规模更小的石子。

解题思路:重点在于如何确认某一堆的sg值,这样考虑遍历两堆规模更小的石子,就是它的下一步状态,求得它们的sg值,进行mex操作,即可得到这堆石子的sg值。

C++代码如下,

#include <iostream>
#include <unordered_set>
#include <cstring>

using namespace std;

const int N = 110;

int n;
int f[N]; //sg值

int sg(int x) {
    if (f[x] != -1) return f[x];
    
    //x可以走到的状态的sg值
    unordered_set<int> S;
    for (int i = 0; i < x; ++i) {
        for (int j = 0; j <= i; ++j) {
            S.insert(sg(i) ^ sg(j));
        }
    }
    
    //mex操作
    for (int i = 0; ; ++i) {
        if (!S.count(i)) {
            return f[x] = i;
        }
    }
}

int main() {
    memset(f, -1, sizeof f);
    
    cin >> n;
    int res = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        res ^= sg(x);
    }
    
    if (res) puts("Yes");
    else puts("No");
    
    return 0;
}

http://www.kler.cn/a/144736.html

相关文章:

  • echarts的横向柱状图文字省略,鼠标移入显示内容 vue3
  • 【机器学习】聚类(一):原型聚类:K-means聚类
  • labelImg
  • Docker的项目资源参考
  • 2023年亚太杯数学建模思路 - 案例:粒子群算法
  • css 常用动画效果
  • Selenium介绍及基本使用方法
  • 【ArcGIS Pro微课1000例】0037:ArcGIS Pro中模型构建器的使用---以shp批量转kml/kmz为例
  • RabbitMq使用与整合
  • linux上的通用拍照程序
  • 从0到0.01入门 Webpack| 004.精选 Webpack面试题
  • (4)BUUCTF-web-[极客大挑战 2019]EasySQL1
  • 淘宝商品详情接口,商品属性接口,商品信息查询,商品详细信息接口,h5详情,淘宝APP详情
  • ⑦【Redis GEO 】Redis常用数据类型:GEO [使用手册]
  • 基于51单片机的公交自动报站系统
  • Oracle 最终抛弃了 Sun !
  • Java枚举
  • ARM - AArch64 - 通用寄存器
  • Java数组的复制、截取(内含例题:力扣-189.轮转数组)
  • 什么是AWS CodeWhisperer?