$$ \def\xor{\text{ xor }} \def\mex{\mathrm{mex}} \def\SG{\mathrm{SG}} $$
一共 $n \times m$ 个硬币，摆成 $n \times m$ 的长方形。dongdong 和 xixi 玩一个游戏，每次可以选择一个连通块，并把其中的硬币全部翻转，但是需要满足存在一个硬币属于这个连通块并且所有其他硬币都在它的左上方（可以正左方也可以正上方），并且这个硬币是从反面向上翻成正面向上。dongdong 和 xixi 轮流操作。如果某一方无法操作，那么他（她）就输了。dongdong 先进行第一步操作，假设双方都采用最优策略。问 dongdong 是否有必胜策略。
第一行一个数 $T$，表示他们一共玩 $T$ 局游戏。
$$ \def\xor{\text{ xor }} \def\mex{\mathrm{mex}} \def\SG{\mathrm{SG}} $$
小 E 与小 W 进行一项名为 E&D 游戏。
游戏的规则如下：桌子上有 $2n$ 堆石子，编号为 $1 \sim 2n$。其中，为了方便起见，我们将第 $2k-1$ 堆与第 $2k$ 堆（$1 \le k \le n$）视为同一组。第 $i$ 堆的石子个数用一个正整数 $S_i$ 表示。
一次分割操作指的是，从桌子上任取一堆石子，将其移走。然后分割它同一组的另一堆石子，从中取出若干个石子放在被移走的位置，组成新的一堆。操作完成后，所有堆的石子数必须保证大于 $0$。显然，被分割的一堆的石子数至少要为 $2$。两个人轮流进行分割操作。如果轮到某人进行操作时，所有堆的石子数均为 $1$，则此时没有石子可以操作，判此人输掉比赛。
$$ \def\xor{\text{ xor }} \def\mex{\mathrm{mex}} \def\SG{\mathrm{SG}} \def\tuple[1]{\langle (#1) \rangle} $$
一起长大的约定 那样清晰 拉过勾的我相信 说好要一起旅行 是你如今 唯一坚持的任性
——《蒲公英的约定》
清和如在玩游戏。她们有 $n$ 丛蒲公英，每丛分别有 $s_i$ 朵。这些蒲公英有一个神奇的性质：有一个给定的常数 $\sigma \in (0,1)$，$x$ 朵蒲公英会分出 $\lfloor \sigma x \rfloor$ 朵为一组，剩下 $x-\lfloor \sigma x \rfloor$ 朵继续分组，直到分出的组没有蒲公英即 $\lfloor \sigma x \rfloor=0$ 为止。她们称这种现象为任性。现在她们的每丛蒲公英都有任性的现象。
$$ \def\xor{\text{ xor }} \def\mex{\mathrm{mex}} \def\SG{\mathrm{SG}} $$
Urej 喜欢玩各种类型的沉闷游戏。他通常会邀请其他人和他一起玩。他说，玩这些游戏可以展现他的非凡智慧。最近，Urej 对一个新游戏产生了极大兴趣，而 Erif Nezorf 成为了牺牲品。为了摆脱玩这样一个沉闷游戏的痛苦，Erif Nezorf 请求你的帮助。这个游戏使用一个由 $W \times H$ 格网组成的矩形纸张。两名玩家轮流将纸张切割成两个矩形部分。在每个回合中，玩家可以横向或纵向切割，保持每个格网完整。经过 $N$ 轮后，纸张将被切割成 $N+1$ 片，然后在后续的回合中，玩家可以选择任意一片进行切割。如果一名玩家切割出一个只有一个格网的纸片，他就赢得了游戏。如果这两个人都非常清楚，你应该写一个问题来告诉是否先手的玩家能赢得游戏。
$$ \def\xor{\text{ xor }} \def\mex{\mathrm{mex}} \def\SG{\mathrm{SG}} $$
博弈论题目的特点：
P2197 【模板】Nim 游戏 - 洛谷：在许多地方曾经流行过这样一个小游戏：摆出三堆硬币，分别包含 3 枚、5 枚、7 枚。两人轮流行动，每次可以任选一堆，从中取走任意多枚硬币，可把一堆取光，但不能不取。取走最后一枚硬币者获得胜利。
这类游戏可以推广为更加一般的形式：
Bessie 有一行 $N$（$2\le N\le 300$）块瓷砖，依次具有丑陋度 $a_1,a_2,\ldots,a_N$（$1\le a_i\le 10^6$）。其中 $K$（$0\le K\le \min(N,6)$）块瓷砖卡住了；具体地，索引为 $x_1,\ldots,x_K$（$1\le x_1<x_2<\cdots<x_K\le N$）的瓷砖。
Bessie 想要最小化瓷砖的总丑陋度，其中总丑陋度定义为每对相邻瓷砖的最大丑陋度之和；即 $\sum\limits^{N−1}{i=1}\max(a_i,a{i+1})$。她可以任意次执行以下操作：选择两块均未卡住的瓷砖，并交换它们。
求 Bessie 以最优方案执行操作可以达到的最小总丑陋度。
题目链接：P2106 Sam 数 - 洛谷。
本题是经典矩阵乘法优化 DP 题目。
小 Z 最近发现了一种非常有趣的数，他将这种数称之为 Sam 数。
Sam 数具有以下特征：相邻两位的数字之差不超过 $2$。
题目链接：P2703 [NOI2006] 千年虫 - 洛谷。
本题使用奇妙性质优化 DP。
千年虫是远古时代的生物，时隔几千万年，千年虫早已从地球上销声匿迹，人们对其知之甚少。考古生物学家最近开始对其有了兴趣，因为一批珍贵的千年虫化石被发现，这些化石保留了千年虫近乎完整的形态。
理论科学家们根据这些化石归纳出了千年虫的一般形态特征模型，并且据此判定出千年虫就是蜈蚣的祖先！但科学家 J 发现了实际与理论的一些出入，他仔细的研究了上百个千年虫化石，发现其中大部分千年虫的形态都不完全符合理论模型，这到底是什么因素造成的呢？理论科学家 K 敏锐的指出，千年虫的形态保存在化石中很有可能发生各种变化，即便最细微的变化也能导致它不符合模型。
题目链接：P2470 [SCOI2007] 压缩 - 洛谷。
给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母 R 与 M，其中 M 标记重复串的开始，R 重复从上一个 M（如果当前位置左边没有 M，则从串的开始算起）开始的解压结果（称为缓冲串）。
bcdcdcdcd 可以压缩为 bMcdRR，下面是解压缩的过程：
| 已经解压的部分 | 解压结果 | 缓冲串 |
|---|---|---|
| b | b | b |
| bM | b | . |
| bMc | bc | c |
| bMcd | bcd | cd |
| bMcdR | bcdcd | cdcd |
| bMcdRR | bcdcdcdcd | cdcdcdcd |
题目链接：P2145 [JSOI2007] 祖玛 - 洛谷。
这是一个流行在 Jsoi 的游戏，名称为祖玛。
精致细腻的背景，外加神秘的印加音乐衬托，彷佛置身在古老的国度里面，进行一个神秘的游戏——这就是著名的祖玛游戏。祖玛游戏的主角是一只石青蛙，石青蛙会吐出各种颜色的珠子，珠子造型美丽，并且有着神秘的色彩。
环绕着石青蛙的是载着珠子的轨道，各种颜色的珠子会沿着轨道往前滑动，石青蛙必需遏止珠子们滚进去轨道终点的洞里头，如何减少珠子呢？就得要靠石青蛙吐出的珠子与轨道上的珠子相结合，颜色相同者即可以消失得分！直到轨道上的珠子通通都被清干净为止。 或许你并不了解祖玛游戏。没关系。这里我们介绍一个简单版本的祖玛游戏规则。一条通道中有一些玻璃珠，每个珠子有各自的颜色，如图 1 所示。玩家可以做的是选择一种颜色的珠子（注意：颜色可以任选，这与真实游戏是不同的）射入某个位置。