题目
矩阵翻转问题
给定一个01矩阵n*m ， \(n , m \leq 1000\) 。 两人轮流操作： 每次选择一个数值为1的点： 使得每次选择的点(包含)到右下角的矩阵01状态翻转。 无法操作则输。 问先手必胜还是后手必胜？
题目来源: 2017Summertraining V8 讲课 博弈论
树翻转问题
上一道题进阶版：hdu5963(2016 CCPC 合肥)
一棵树，每个边有一个边权1,0。每次选一个边权为1的边， 将从这个边开始到根的路径的所有边的边权翻转。 不能操作则输。 问先手胜还是后手胜？
K倍动态减法游戏
两个人轮流取石子，第一次取可以取任意个(0除外)，但是不能取完，以后每次都只能取不超过上一次取的k倍(0除外)。
问先手必胜，还是后手必胜？
毒药问题
1000个瓶子中有一瓶毒药（编号000 ~ 999 ），一只老鼠吃到毒药一周后会死，瓶子里有无穷多的药水，老鼠可以吃任意瓶药水。 1. 如果只有10只老鼠，如何在一周内检测出老鼠所吃的毒药的编号是由哪几位数字组成？（如毒药为 413号的话，答案是1 3 4 、 3 1 4 、 4 1 3 等都对） 2. 如果只有10只老鼠，如何在一周内检测出所吃的毒药是哪一瓶？ 3. 如果要在两周内检测出哪一瓶是毒药，最少需要几只老鼠？
Codeforces Taxes
题目链接：Codeforces Round #382 (Div. 2)-735D TAXES
题意：年收入是N，那么需要缴税额是N除自身外的最大因子。为了偷税可以把N拆成K个数，但是拆成的数不能为1，因为这样会被税务局发现。找出最小税额。
好像是CCPC 2017 哈尔滨题
输入一个n，已知该数列是由 1 - n 共n个数组成的。 要求构造一个数列，数列满足 \[a\_{n} \\bmod | a\_{n} - a\_{n-2} | =0\] 给出任意一个满足要求的数列。
-----
解答
矩阵反转问题
我们观察到无论如何进行游戏，每次必将使局面减少1个1(换句话说，将1个1恒久地变为0了，不可能再变回来了)
因此局面是朝着右下角不断缩小的。
最后必然缩小到最后一个格。
那么，如果右下角一开始是0，先手无论如何操作，都会将右下角变成1，后手只要将右下角一个变成0。那么这样操作下去，给先手的人一定是一个右下角是0的局面。所以先手必输。
反之，先手必胜。
(这道题很适合讲完博弈论的必胜必败态后出一下2333)
树翻转问题
考虑假如只有一条链，那么先手如果将第一个边的1变成0，后手无论怎么操作，都只能把这个1变回去，或者不可操作输了。
因此，如果第一个边是1，那么先手必胜。
如果是树的话，只需要知道和这棵树的根节点连接的边权为1的边的个数是奇数还是偶数就可以了。
(这里已经有点SG函数、异或之类的意思了)
k倍动态减法游戏。
我目前对这里的理解还有一些问题，未完待续，仅供参考。 1. 当k等于1时，我们将石子数拆成二进制数，会发现先手如果每次只取1个的话，会把最后一位由1变成0，或者由0变成1。因此，只要最后一位是1的话，先手必胜。否则后手必胜。(因为局面必定会缩小到最后只有一位) 2. 1. 当k等于2时，同样将石子拆成二进制数，如果第一次取了1个，会发现第二次取只能取1个（即将最后一位0 1变换）或者取2个（即将倒数第二位0 1变换） ， 然后由任何一个正整数都可以由两个斐波那契数相加得到，求解.(我对这里不太理解，未完待续)
用必胜态必败态DP转移得到。不过这里细节比较多，比如
dp[n][n]在第一手的时候因为不能拿完，但是在第二手又可以拿完，这里需要注意一下变化。 这道题V8当时主要讲的是如何把\(O(n^{3})\) (朴素)* 优化到\(O(n^{2})\) (减少维数) 再优化到\(O(n)\) (单调栈) 。 第一次听讲的时候惊艳了。当到k倍的问题的时候，请参考NOI2009冬令营论文——《从“k倍动态减法游戏”出发探究一类组合游戏问题》
毒药问题
这其实是我一开始错误的想法改编后成的问题。对于这样的话，只要让所有数字带0的药水，给第0个老鼠吃，所有数字带1的药水给第1个老鼠吃即可由哪几只老鼠死亡来判断所含数字。- 将1000瓶药水的编号二进制拆分，正好是10位以内，即可把10只老鼠分别对应一个二进制位。由此准确确定毒药的二进制位，转成十进制即可。
- 将1000瓶药水三进制拆分，这样第一天可确定毒药每一位数字是否为0，第二天可确定是否为1，然后排除法确定哪些是2。 1000转成三进制是7位，所以需要7只老鼠。
Codeforces Taxes
哥德巴赫猜想。
需要注意的是，人们熟知的哥德巴赫猜想，是\(1+1=2\)，但是那是建立在1被作为素数的情况下。 因此，现代的哥德巴赫猜想有些不同。 >原初猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。欧拉在回信中也提出另一等价版本，即任一大于2的偶数都可写成两个质数之和。 >今日常见的猜想陈述为欧拉的版本，即任一大于2的偶数都可写成两个素数之和，亦称为“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”。 >从关于偶数的哥德巴赫猜想，可推出：任一大于7的奇数都可写成三个质数之和的猜想。后者称为“弱哥德巴赫猜想”或“关于奇数的哥德巴赫猜想”。若关于偶数的哥德巴赫猜想是对的，则关于奇数的哥德巴赫猜想也会是对的。弱哥德巴赫猜想尚未完全解决，但1937年时前苏联数学家维诺格拉多夫已经证明充分大的奇质数都能写成三个质数的和，也称为“哥德巴赫-维诺格拉朵夫定理”或“三素数定理”。
因此，我们只需要对 大于7的奇数，判断他是否是由一个质数+2这个质数得来的，如果是，则答案为2，否则为3. 对大于2的偶数，答案为2.
好像是CCPC 2017 哈尔滨的题
本来我想的是任意偶数差两个都可以满足要求，但是奇数和质数就不太满足，然后考虑了一下，质数要满足，必定是$ a_{n} 与 a_{n-2} $ 相差1。因为任何数 mod 1 都是0 。 所以考虑构造数字的方法就是 类似于蛇形填数，第 1、3、5、7、.... n-1 依次填1234567，然后n-2、6、4、...2 以此填写8 9 10 11... 即可