感觉挺有意思的,长期更新吧。
博弈论入门
逻辑链
拆分-Nim游戏
一个局面拆成了两个局面,多个独立局面等于它的异或和,记忆化搜索维护。
取石子游戏
显然只有两堆石子时可以直接异或,否则区间$DP$计算左边或右边放多少个石子先手必败,
由于后手必胜等于先手必败,而且必败态元素取值唯一,所以可以推出来。
简单讨论一下就可以了。
Family Photos
由 $a_1 - b_2 >= a_2 - b_1$ 知 $a_1 + b_1 >= a_2 + b_2$,对于其它情况分类讨论即可。
对于小$B$,他每次都只能选正序排序后,每个二元组中较小的哪个。
当 $a_1 - b_2 < a_2 - b_1$,
由于每对照片只有取了第一张才能取第二张,所以如果 $a_1 - b_2 > 0$,小$A$还是会取第一张,
同理我们也可以分析出 $b_1 > a_2$ 时,就算会亏,小$A$也会在小$B$之后选,
反之,双方就宁可游戏结束也不选了,因为两边都不赚。
所以本题的关键在于只要有一方想玩,那就得玩下去。