[除草]bzoj 2410: Nim游戏

最近一直没干正事。现在的生活已经不能用颓废两个字形容了……只能用"浪"这个字来形容了。
//这篇博文是第二次重写的,第一篇因为太浪忘记保存结果浪没了。
先来吐槽这题标题……nim游戏的sg函数跟这玩意的sg函数差太远了啊……
题意:

一排n个格子,两人轮流用k种颜色给一个未染色的格子染色,要求每次染色后都不能有两个相邻的格子被染上了相同的颜色,你需要做的是判断一个已有部分格子被染色的初始局面是先手必胜还是后手必胜。

显然是一个组合游戏……
如果k>2,那么任何时刻都能染色,每次一方只能染一块格子的颜色,所以看一下空格子的总数的奇偶性就可以了。
然后剩下的情况只有k=1,k=2两种。
看起来k=1比较好搞
所以先来讨论一下k=1的情况。
很容易发现……染好色的格子将其它没染色的格子分成若干个块。
比如样例给的图片:


一开始有一个为4的空白块,然后变成了两个空白块,大小为2,1。
显然不同块之间的游戏是独立的,所以算出每个块的游戏的sg值,然后异或起来就好了。
定义sg[i],表示初始一个长度为i的空白块,没有任何染色格子的状态的sg数值。
然后我们可以发现对于一个被两个染色块夹住的空白块,如果它的长度为n,那么它能染色的格子数为n-2,因为左端和右端不能染色。
所以图里面一开始的sg值为sg[3],第二个状态的sg值为sg[0] xor sg[0]

然后很容易发现sg[i]的递推式……


接下来就到了群众喜闻乐见的找规律环节了。
打表发现,从1开始……前几项是:
1,1,2,0,3,1,1,0,3,3,2,2,4,0,.....
当时看到这个表的时候我就掀桌了……tm完全看不出规律啊!
主席建议我用sam或者后缀数组之类的东西来找一下规律……找一下那些子串出现次数比较多之类的……我觉得这个做法脑洞太大,就没有实施(事实证明如果我真的这么做了,那么肯定就能找到某些规律了……)

然后问了一下杜教,杜教:34循环节?
一眼秒简直可怕……
总之查了一下oeis之类的发现这破玩意是以34为循环节的……
但是有反例,第2个循环节可能会出现sg[i]!=sg[i-34]的情况……
但到后期,就是准确的了。
这个性质应该可以用流氓归纳法归纳出来。但是我很关心这个性质怎么才能很快地在考试时发现……因为这个性质在小范围有反例,在大范围反而没有,很容易让人在找小范围的规律时把它排除掉。。。
(而且34这个循环节好不自然……
oeis说这个sg值是“Sprague-Grundy values for Dawson's Chess”
我也没怎么找这个资料……也不知道有没有人正经证明这个34循环节……下次看看有没有证明吧。

然后k=1的情况就这样解决了……
接下来看k=2的情况……
先暂时不讨论全部空白的特殊情况...
空白块总共有三种:
1.有一端与一个染色块相邻,另一端为整个序列的首或尾。
2.两端都与染色块相邻,两端颜色不同。
3.两端都与染色块相邻,两端颜色相同。

因为情况2和情况3比较相似……
所以我们先来考虑这两个情况。

很容易发现f[i][0]在i>0的时候都是0,f[i][1]在i>0的时候都是1。归纳可证。
然后考虑一下第一种情况,定义g[i]为有一个长度为i的情况1的空白块的sg值,容易验证g[i]=i。

这题就被这样浪过去了。

Comments

comments powered by Disqus