随手记
-
链式前向星(临接表优化版)
-
SPFA算法(解决负权图，如果瞎优化会变成指数复杂度)
-
反向建图(这个应该是和路径输出有关，具体再分析)
-
最大连续子序列和(动态规划大法好 O(n)复杂度)，或者也可以维护前缀和最小值，
-
给出阶梯博弈(尼姆进阶版)先手必胜的条件：当且仅当所有奇数上的台阶的石子数的异或和不为0时，先手必胜。
-
尼姆博弈证明
而对于Nim游戏，局面是必败态当且仅当所有堆硬币的数量都异或起来结果为0，即：
a1^a2^...^an=0为了证明之，我们只要证明它满足上述必败态的三条性质即可。
-
第一个命题显然，最终局面只有一个，就是全0，异或仍然是0。
-
第二个命题，对于某个局面(a1,a2,…,an)，若a1^a2^…^an不为0，一定存在某个合法的移动，将ai改变成ai’后满足a1^a2^…^ai’^…^an=0。不妨设a1^a2^…^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k<ai一定成立。则我们可以将ai改变成ai’=ai^k，此时a1^a2^…^ai’^…^an=a1^a2^…^an^k = k^k =0。
-
第三个命题，对于某个局面(a1,a2,…,an)，若a1^a2^…^an=0，一定不存在某个合法的移动，将ai改变成ai’后满足a1^a2^…^ai’^…^an=0。因为异或运算满足消去率，由a1^a2^…^an=a1^a2^…^ai’^…^an可以得到ai=ai’。所以将ai改变成ai’不是一个合法的移动。证毕。
-
