"看着昔日的小伙伴,现在和我犹如天壤之别"

"难道你就没有什么惋惜想挽回的吗?"

"......死亡?"

巴什博奕

每轮我们可以报出1~n的一个数

第一个报到m的人胜利,问给出n,m谁必胜

m%(n+1)==0后手必胜

否则先手必胜

我们一定有一个策略是对手报 $x$ ,我就报 $n-x$

如此重复下去,直到报完我一定胜利

如果 $%(n+1)!=0$ ,先手第一步可以报余数

于是后手变为了必败态

每人给出一个从1到100之间的数字。把所有人的数字求算术平均值。谁选的数字最接近这个算术平均值的2/3，谁就赢得整场游戏。

1是答案,因为所有人在绝顶聪明的情况下最后都会选择1

平均选的平均数是50,但是大家为了自己肯定不会让你有50,于是可能爆出100

接着如果考虑到这一步 $[1,66]$ 的范围内就会被选

接着是 $[1,45],[1,30]$ 直到最后 $[1,1]$

但是并不是所有人都如此聪明,所以说选1反而不会胜出

P5675 [GZOI2017]取石子游戏

选出一些异或为0的

显然这样先手必败,钦点她选哪个都一样

选出一些异或不为0的

那么我们钦定她第一步选完后不能选出一个异或值为0(后手必败)的状态

也就是说分给他的石子堆数要小于异或值最高位

因为这样他一定没法一步变成异或值为0的后手必败态,然后就输了

所以我们dp即可 $f_{i,j,k}$ 表示前i个人异或值为j,而且最高位小于异或值的有k个的方案数

转移对于一个状态直接计算后继即可

最后统计方案,不难发现每个状态都是本质不同的,于是我们直接计数即可.....

题解的方法:枚举一下A选了哪堆,剩下直接dp出方案数即可

也可以

SG定理证明

Nim游戏正确性的证明

我们不难发现,博弈论(五子棋)就是在在于削弱先手优势

如果先手只能做出一步适得其反的操作,先手就输了

因为所有石子堆异或起来不为0,设那个值k的最高位为j

所以先手可以选择一个最高位有j的石子堆,让他取走 $a_i^k$ ,此时一定能取...因为至少最高位j在呢

于是异或值变成了0,此时后手随便搞一步,先手可以重复上述过程

直到全局为0,后手搞不了那一步了

SG定理来了

用老子的语言描述,一个总游戏的SG值相当于各个互补干扰的子游戏的SG值异或之和

SG值定义为一个局面能到达所有后继局面异或值的mex,如果SG为0,表示先手必败

额,这个网上的证明都在口胡,甚至直接套nim板子,因此我也口胡一个自己的证法

对于一个总游戏SG值为0的状态

假设现在还有游戏能操作

递归到SG值不为0的状态,能操作次数减少

所有子游戏都终结

先手必败

对于一个总游戏值不为0的状态

现在必然还有游戏能操作,设当前状态最高位那个为j,值为k

还是找到一个最高位j为1的子游戏

因为他的sg值定义为后继mex,所以说一定能转移到一个局面的sg值为 $a_i^k$ ,因为不难发现 $a_i^k<a_i$ ,所以一定存在一个后继局面满足

此时SG值为0,递归到SG值不为0状态

那么我们通过反复归纳,最后一定能得出case1的2情况,又因为先操作的是先手,所以case1永远是留给后手的qwq

P2148 [SDOI2009]E&D

会所有子任务,正解可能要打个表

N=2

我们会发现,两个数存在一个是偶数先手必胜,否则先手必败

先手遵循如下原则操作:

选取其中一个偶数n,划分为1,n-1

后手只能:

选择一个奇数,划分成一个奇数+一个偶数,不难发现那之后先手还是能操作

从而先手逐渐将后手逼上绝境

$S_i<=1000$

相邻两个操作后还是相邻两个,也就划分为了子游戏

$f_{i,j}$ 表示第一堆为i,第二堆为j的sg值

sg定理

std:

本游戏一个子局面的 $sg(i,j)=(i-1)|(j-1)$

打表方法:根据一个的( $sg_i$ )sg值来找规律,发现是 $n-1$

于是两个就容易找出了

P4101 [HEOI2014]人人尽说江南好

简单题

每次我们合并两堆.相当于给某一堆+1因为后手一定可以让你新合并的某堆和某堆合并从而相当于合并入了两个1

那么我们一共能合并的次数也就能算出来了

是奇数先手必胜


#include<bits/stdc++.h>
#define int long long
using namespace std;
int T, a, b;
signed main() {
	scanf("%lld", &T);
	while(T-- > 0) {
		scanf("%lld%lld", &a, &b);
		int ans = a / b * (b - 1);
		ans += (a % b ? (a % b - 1) : a % b);
		printf("%lld\n", (ans & 1) ^ 1);
	}
	return 0;
}

P2964 [USACO09NOV]A Coin Game S

比较简单, $f_{i,j}$ 表示考虑前i个硬币,然后这一个人走的步数为j,先手操作,先手减去后手的最大收益是什么

因为是零和博弈,所以可以设计出这样的状态,转移枚举上一个人用了几步

然后我们可能要更大的空间,不太允许,不妨再用个小技巧就是一个状态向未来转移,但是我们只转移最小可到达的,然后接着一个j向 $j+1$ 转移就能压下空间了

当然题解有一个一个数转移可是可以的

P4576 [CQOI2013]棋盘游戏

naive题

$f_{i,j,k,l,m,n}$ 表示第一个棋子在(i,j),第二个在(k,l),目前走了k步,是谁掌棋的最小到结束的回合数

那么后手会取max,先手会取min

这个k不会超过3n,所以可能要思考下为啥

P3480 [POI2009]KAM-Pebbles

差分

之后发现一次操作对于数组的影响相当于把一个非0的位置数减少一部分加到他后面那个位置

哎?阶梯nim板子

阶梯nim的做法是所有奇数位置拿出来做nim

阶梯nim证明:

偶数位置操作完为加到了奇数位置,不妨令0为偶数,定义的局面为奇数位置nim值

但凡是偶数位置,我们操作之后另一方一定可以再做出同样的操作使得定义的局面不发生改变,但是总能够操作的次数减少了

和可爱的超现实数一样,只要能减少规模递归定义也可以的啦

超现实数

这是一个很牛逼的数域,因为他是最大的有序域!

下面只说说他和博弈论的联系,因为既然是最大的有序域,博弈论里面所有状态也不例外

$x={x^L|x^R}$

其中 $x^L$ 和 $x^R$ 都是一个集合?

我们定义x的值为 $x^L$ 中最大的和 $x^R$ 中最小的那个的和的一半

同时定义边界 $0={|}$

那么我们把所有左玩家操作一次的得到的局面放在x的左边,右玩家操作一次后的局面放在右边,递归左右就能有x的值了

这个有什么用呢?所有子游戏局面的值求和,大于零则左玩家必胜,小于零则右玩家必胜

相当厉害,举个例子,一排黑白棋,左玩家只能操作0,右玩家只能操作1,操作是把这个棋和右边的都删掉,然后最后不能操作的输

1010

(显然后手必胜)

$x={101,1|10,{|}}$

而

$1={|{|}}=-1$

$10={1|{|}}=-1/2$

$101={1|10,{|}}=-3/4$

$x=-5/8$

也是后手必胜qwq

Anti-SG

桌子上有 N 堆石子，游戏者轮流取石子。
每次只能从一堆中取出任意数目的石子，但不能不取。
取走最后一个石子者败。

于是我们考虑这个问题的解决方案---SJ定理

先手必胜当且仅当:

任意堆的石子数都为1,而且总局面sg值为0
存在堆的石子数大于1,而且总局面sg值不为0

sg值就是nim游戏的sg值

好像就是nim游戏的一个特例,我们先分析1情况

此时显然是有偶数个堆石子,而且轮流选后手一定拿到最后呢

2情况

首先后手对于大于1的情况可以和先手对称选取(经典nim),然后变成情况1,而你会发现,最后可能会变成情况1

但是这之前一定是只有一堆石子大于了1,那么先手一定可以操作他吧局面变成只剩下奇数个1,就赢了

把这个直接拍过来,就是sj定理(Sprague Grundy——Jia Zhihao 定理??)

对于任意一个 Anti-SG 游戏， 如果我们规定当局面中所有的单一游
戏的 SG 值为 0 时， 游戏结束，则先手必胜当且仅当： （1）游戏的 SG 函
数不为 0 且游戏中某个单一游戏的 SG 函数大于 1；（2）游戏的 SG 函数
为 0 且游戏中没有单一游戏的 SG 函数大于 1。

如何证明其正确性?其实和nim游戏的证明大多数都是重叠的

其中有一个附加条件"我们规定....."才使得结论正确,然后给了个超长证明,我咕咕咕了

夏晓光(loveJY)的博客

昴的博弈论1