Posts match “ 小记 ” tag:

并查集可以加入统计量,来统计某个等价类的性质。并且,通过在合并时更新,可以保留此类性质。

差统计量 维护的是两个节点之间差的统计量。有人将此类归作种类并查集,但其本质上维护的是两个节点之间差的值,并且通过合并来逐步完善差的关系。

进一步的解释:如果若干个元素在同一个集合中(从fa[x]可以观察出来),那么这个集合中任意两个元素x,y的差值rk[y]-rk[x]是一定的。
如果询问:所给的两个元素是否在同一个集合中/求两个元素的差值/求某一统计量,其可以间接转化为两个元素的差值/...,我们就可以通过判断rk[y]-rk[x]是否与询问一致/返回rk[y]-rk[x]的值来解决。

分析如下例子:
HDU 3038 How Many Answers Are Wrong
大致思路:这题就相当于判断两个元素的差统计量是否与所给的值矛盾,很明显,若两区间端点相邻或重合,我们就可以求出这些子区间及子区间合并后的区间的元素和。我们可以将区间变为左闭右开的形式(即区间右端点+1),然后合并两端点。
直接看样例:
一开始初始化所有rk[i]为0,并在接下来的合并x,y中保持fa[y]->fa[x](固定合并方向)
1 10 100 -> 合并1,11,rk[1]=0,rk[11]=100
7 10 28 -> 合并7,11,相当于合并7,1,求相对值后rk[1]=-72,rk[7]=0,rk[11]=28
1 3 32 -> 合并1,4,相当于合并7,4,求相对值后rk[4]=-40,其余不变
4 6 41 -> 发现4,7在同一个集合中,但rk[7]-rk[4]=0-(-40)=40,矛盾
6 6 1 -> 合并6,7,rk[7]=1,更新各节点之后rk[1]=-71,rk[4]=-39,rk[6]=0,rk[7]=1,rk[11]=29

继续阅读

零、「以牙还牙,以眼还眼」

Codeforces 197A Plate Game
(经典博弈,我们选修课老师在上课时提到过此题)
分析:一开始你放一个盘子在桌子中心,然后对手怎么放,你就关于桌子中心对称地放,只要一开始你能放一个盘子在中心,那么最后你肯定能赢。
此乃「以牙还牙,以眼还眼」。

一、基础知识

一般规则:

  1. i=0为必胜/必败态(视题目而定);
  2. 某个i-(某个数)为必败态的话,i为必胜态 / 若i为必败态,则i+(某个数)为必胜态;
  3. 所有i-(某个数)为必胜态的话,i为必败态 / 若i为必胜态,则i+(某个数)可能为必败态,但是若i+(某个数)只有一个后继,则其必为必败态

技巧:
如果难以看出必胜/必败态,不妨从i=0开始画一棵必胜/必败态的转移树来辅助分析。

一些题目使用记忆化搜索就可以解决。

>> 有最大取子限制的取石子游戏:POJ 2068 Nim
>> 需要一些技巧性讨论的取石子游戏:POJ 1740 A New Stone Game
>> 欧几里得博弈:POJ 2348 Euclid's Game (好题)
>> 弗格森 (Ferguson) 游戏(大白书 P134)
>> Chomp! 游戏(大白书 P134)
>> 约束游戏(大白书 P135)
>> 日历博弈:POJ 1082 Calendar Game

巴什 (Bash) 博奕
HDU 1846 Brave Game
有 n 个石子,两个人轮流取 1~m 个石子。最后取光者得胜。
结论:当 时后手胜,否则先手胜。
分析:以牙还牙。当 时,先手取 x 个,那么后手取 m+1-x 个,最后一定是后手取完;当 时,设 ,一开始先手取 r 个,那么变成前面 的局面,最后先手取完。

>> 威佐夫 (Wythoff) 博奕与 Beatty 定理
>> 斐波那契 (Fibonacci) 博弈与 Zeckendorf 定理

二、Nim

该游戏起源于中国,经当年到美洲打工的华人流传出去。其英文名「NIM」是由广东话「拈」(取物之意)音译而来。

1902 年,L.Bouton 脑洞大开,提出了如下定理,从而彻底地解决了 Nim 问题:

异或和值为零则后手胜,否则先手胜。

而这个定理两句话就能解释明白:

  1. 当异或和值为零时,无论你怎么取,异或和值一定变为非零,对手以牙还牙,使异或和值变为零,如此循环,直至对手取完。故此时先手必败(处于必败态)。
  2. 当异或和值非零时,总能在某一堆中选取若干个石头,使得异或和值为零(可以自己找几个例子算算),则必胜态总能转移到必败态。

一些问题可以转化为 Nim 问题,常用的思路是两个两个分成一组进行思考,注意利用“以牙还牙,以眼还眼”这一技巧。

例题:
UVa 12499 I am Dumb 3
HDU 4315 Climbing the Hill

下面阶梯博弈的变形2也可以用分组的思想做。

阶梯博弈(Staircase Nim)

博弈在一列阶梯上进行,每个阶梯上没有石子或放着若干个石子。两个人进行阶梯博弈,每一步则是将阶梯(不是第一层的阶梯)上的若干个石子移到(某些指定的)低阶的阶梯去,最后没有石子可以移动的人输。

阶梯博弈可以利用游戏的限制转化成Nim解决:由于某个阶梯上的石子移动到不能移动时所需的步数要么是奇数,要么是偶数。对于偶数步,对方用哪些石子走一步你也用哪些石子走一步,从而不影响游戏结果。所以只对奇数阶的石子求Nim就行

例题:HDU 3389 Game

有一些看似与阶梯博弈无关的题,揭开它的面纱后,实际上就是阶梯博弈:

  1. 博弈在一个N个格子的方块上进行,每个方块上至多有一个石子,每次可以选择一个石子向右移动到最近的空位,不能移动石子的人输,如下图所示:

设函数F[i]表示第i个石子移动到不能移动所需要的步数。
然后我们来观察某一次移动,假设图中的2跳到了4的后面,我们可以来观察一下所有石子的F函数有什么变化:


首先对于1及其之前的石子,它们的F函数显然不变。
同样,对于移动后的2之后的石子,它们的F函数也不变。
那么变化的就是2,3,4这三个石子的F值,变化了多少?每一个减少了1
那么,如果我们把这个函数F[]看做台阶的阶数的话,乃是不是觉得有一点熟悉的感觉了~
没错!就是阶梯博弈

·2. POJ 1704 Georgia and Bob
也是一行格子和一些石子,每次可以把一个石子往左移动若干步,但是不能越过石子,谁最后不能移动谁输。
如果将没有石子的格子看做阶梯上的石子,我们会发现移动一个石子实际上是将这个石子左边的格子移到右边去,也就是把高度为i的阶梯上的石子移到下一个阶梯上去(最右边的空白为第一阶),所以还是讨论奇偶性~
(这题也可以用两个两个一组的思路来思考)

三、Grundy值(SG函数)

我们把 Nim 游戏加点限制:每次你只能取a1,a2,a3,...an个石头。
如何转化成 Nim 问题呢?
原来的 Nim 是 a->a' 的转化,现在我们改为 SG(a)->SG(a') 的转化。
Wiki 中给出的例子。

Sprague-Grundy 定理(SG 定理):游戏和的Grundy值等于各游戏Grundy值的异或和。
很多博弈游戏都含有游戏和这一要素,故可用Grundy值很方便的解决。

剪纸博弈
POJ 2311 Cutting Game(代码见下)

继续阅读

int solve(int n)
{
    int sqrtn = sqrt(n + 0.5), cnt, ans = 1;
    for (int i = 2; i <= sqrtn; ++i) if (n % i == 0)
        {
            for (n /= i, cnt = 1; n % i == 0; n /= i) ++cnt;
            if ((i & 3) == 1) ans *= cnt << 1 | 1;
        }
    if (n > 1 && (n & 3) == 1) ans += ans << 1;
    return (ans - 1) >> 1;
}

使用 Pollard's rho 算法可以加速到,代码就不贴了。。

参考 A046080 中的 Mathematica 代码:

cnt[n_] := If[n == 1, 0, With[{expList = Select[FactorInteger[n], Mod[#[[1]], 4] == 1 &][[All, 2]]}, ((Times @@ (2 * expList + 1)) - 1) / 2]];

证明待填。。