何事秋。
何事秋。
全部文章
博弈论基本算法
AC自动机(4)
bfs/dfs(5)
bitset(3)
CF刷题(23)
dp一般看规律(11)
dp基本算法(12)
KMP(2)
LCA(1)
LCT(4)
Prufer(2)
SAM(3)
STL(1)
tarjan(1)
主席树/线段树(14)
二分/三分(2)
二分图(1)
位运算(1)
偏序问题(2)
分块(1)
分治/点分治/边分治(2)
单调栈(2)
单调队列(1)
博弈/sg(3)
后缀数组(1)
启发式合并(1)
哈希(4)
回文自动机(2)
图论一顿套模板(3)
图论基本算法(31)
基本算法(2)
多项式(1)
套题(1)
字典树(1)
字符串基本算法(27)
容斥(1)
平衡树/堆(2)
并查集(3)
序列自动机(1)
快速幂/矩阵快速幂(1)
思维只会A+B(5)
投稿(2)
拓扑序(1)
数位dp(1)
数学不好先打表(4)
数据结构基本算法(69)
数据结构瞎乱写(8)
数论分块(1)
数论只会gcd(20)
数论基本算法(64)
暴力(1)
最短路(3)
期望/概率(1)
期望dp/概率dp(1)
构造(3)
枚举(3)
树形dp(3)
树链剖分(5)
模拟只会猜题意(5)
生成树(1)
签到题(2)
线性dp(12)
线性基(2)
组合数学(1)
组合数学靠运气(2)
结论题(2)
网络流/费用流(5)
网络流基本算法(5)
群论(2)
背包dp(1)
莫比乌斯反演(1)
莫队(1)
虚树(1)
计数类dp(1)
计算几何(8)
计算几何基本算法(15)
贪心刚好过样例(3)
随机化算法(2)
归档
标签
去牛客网
登录
/
注册
何事秋。的博客
全部文章
/ 博弈论基本算法
(共11篇)
巴什博弈
一、巴什博弈: 巴什博弈:只有一堆n个物品,两个人轮流从这堆物品中取物, 规定每次至少取一个,最多取m个。最后取光者得胜。 i f (...
2020-09-04
0
488
斐波那契博弈
一、斐波那契博弈: 有一堆物品,两人轮流取物品,先手最少取一个,至多无上限,但是不能把物品取完,之后每次取的物品数不能超过上一次取的物品数的二倍且至少为1件,取走最后一件物品的人获胜。 先手胜当且仅当n不是斐波那契数(n为物品数)。
2020-09-04
0
384
Ferguson游戏
一、Ferguson游戏: 有两个盒子,一个装有m颗糖,一个装有n颗糖,表示为(m,n) 每次清空一个盒子,将另一个盒子里的糖转移一些过来,并保证两个盒子至少各有一颗糖 最后进行转移糖者获胜,无法转移糖者败。 m,n都为奇数,先手败 m,n至少一个为偶数,先手胜。
2020-09-04
0
562
chomp!游戏
一、chomp!游戏: 1。 有一个n * m的棋盘,棋盘的每一个格子用(x,y)表示,最左上角是(1,1) 每次可以拿走一个方格,并拿走该方格右边与下边的所有方格,谁拿到(1,1),谁败。 除了n=m=1先手败,其余先手胜。 三维的除了(1,1,1)先手败,其余的先手胜。 2。...
2020-09-04
0
1259
SG函数
一、公平组合游戏ICG: 若一个游戏满足: --------由两名玩家交替行动 --------在游戏进程的任意时刻,可以执行的合法行动与轮到哪名玩家无关 --------不能行动的玩家判负 则称该游戏为一个公平组合游戏。 二、有向图游戏: 给定一个有向无环图,图中有一个唯...
2020-09-04
0
899
P/N理论
一、P/N分析法: P点:即 必败点,某玩家位于此点,只要对方无失误,则必败。 N点:即 必胜点,某晚接位于此点,只要自己无失误,则必胜。 必败态:一定输。 必胜态:一定赢。 奇异局势:必败态局势。 非奇异局势:必胜态局势。 P/N点满足三个定理: (1) 所有终结点都...
2020-09-04
0
765
博弈例题、SG函数应用
一、取石子: 有1堆n个的石子,每次只能取{ 1, 3, 4 }个石子,先取完石子者胜利,那么各个数的SG值为多少? SG[0]=0,f[]={1,3,4}, x=1 时,可以取走1 - f{1}个石子,剩余{0}个,所以 SG[1] = mex{ SG[0] }= mex{0} = 1; x...
2020-09-04
0
544
中国石油大学ACM俱乐部开放训练赛 问题 H: qiqi and sciorz K倍博弈:
一天,qiqi和sciorz很无聊,他们又玩起来更无聊的取石子游戏,游戏规则是这样的: 有一堆n个石子,qiqi先取,每次最少取一个,第一次取的时候最多取n-1个,之后每次不能超过上一次的k倍,取得最后一个石子的为胜利,也就是说不能操作的为败. 然而sciorz早已洞穿了一切,他已经知道了谁会胜...
2020-09-04
0
496
探寻翻硬币博弈
翻硬币游戏 一般的翻硬币游戏的规则是这样的: N 枚硬币排成一排,有的正面朝上,有的反面朝上。我们从左开始对硬币按1 到N 编号。 第一,游戏者根据某些约束翻硬币,但他所翻动的硬币中,最右边那个硬币的必须是从正面翻到反面。例如,只能翻3个硬币的情况,那么第三个硬币必须是从正面翻到反面。如果局面是正...
2020-09-04
0
730
尼姆博弈
一、尼姆博弈: 有任意堆物品,每堆物品的个数是任意的,双方轮流从中取出物品, 每次只能从一堆物品中取出部分或全部物品,最少取一件,取到最后一件物品的人获胜。 把每堆物品全部异或起来,如果最终得到的值为0,则先手必败,否则先手必胜。 int flag=0; 二、anti-nim: 取...
2020-09-04
0
426
首页
上一页
1
2
下一页
末页