《算法竞赛进阶指南》扫题 - part1
black_trees 的重来之路-part1：
这是lyd的蓝书的扫题计划。
共 323 题，预计在8个月之内扫完 80%。
我会单独新建一个文件夹，把所有我重来的代码都放进去。
在做完每个章节之后会有归档，进度可以在 Github 上查看。
0x00「基本算法」例题
CH0101 a^b
这是快速幂的板子题，让你求 \(a^b \% p\) 的值。
首先有一个非常重要的二进制拆分思想：
对于 $\forall x \in \mathbb{N}^* $ ，可以把 \(x\) 的二进制表示写成如下形式 :
\(c_1\times 2^{0} + c_2\times 2^{1} + ... + c_k\times 2^{k-1}\)。
其中 \(c_i\) 表示 \(x\) 在二进制下的第 \(i\) 位（从 \(1\) 开始）的数字是多少。
然后我们考虑把 \(b\) 这样子拆分。
实现只需要每次把 \(b\) 的最低位 \(i\) 取出来，如果为 \(1\) 那么就把 \(a^{2^{i-1}}\) 乘到答案里面，就能算出 \(a^b\)。
\(a\) 可以利用 \(a^{2^{k}}=(a^{2^{k-1}})^2\) 这个式子来递推处理。
记住答案最开始要设置成 \(1\) 对 \(p\) 取模以避免 \(p=1\) 的时候答案出错。
CH0102 64位整数乘法
考虑把 \(b\) 像上一题一样拆分，那么每次令 \(a=2a\) ，如果 \(b\) 的当前最低位是 \(1\) 那么累加答案。
POJ1995 Raising Modulo Numbers
依旧是快速幂的模板题。
只需要分别求个快速幂然后全部加起来即可。
不要忘记加的时候取模。
CH0103 最短Hamilton路径
状压 DP 的模板题。
我们设 \(f_msk\) 表示走到的点集合为 \(msk\) 的时候的最短路径。
但是发现这样子没法表示状态，所以再加一维，\(f_{msk,i}\) 表示表示走到的点集合为 \(msk\) ，且当前在 \(i\) 的时候的最短路径。
那么先枚举状态，然后枚举所有点对来转移即可。
CH0104 [NOI2014] 起床困难综合症
很精妙。
我们发现如果直接去找这个数是什么会特别麻烦。
不妨换个思路，因为位运算的特点之一就是不进位（比如异或就是二进制下的不进位加法）。
所以每一位之间不会干扰。
我们考虑枚举答案的每一个数位到底是 \(0\) 还是 \(1\)。
然后对于每个位置，我们取出每一扇门上数字在二进制下的这一位进行运算。
如果这一位选 \(0\) 只需要记录当前的攻击力最大值即可，选 \(1\) ，那么还需要累加答案。
复杂度在 \(\log\) 级别。
不过我不是很明白，为什么我的Code里面，如果枚举的这个答案的位数是 \(30,29\) 位才能过。
\(32,31,28\) 都或多或少会挂一两个点呢？
upd on 2021/11/16 ： 在 Crab_Dave 
\(2^{28} \le 10^9\) ， 比题目给的值域小了。
\(2^{32} > 2^{31} > \text{INT\_MAX}\)，虽然我代码开了 long long 但是位运算的时候没有写 1ll。
CH0201 费解的开关
发现当第一行固定之后，如果你需要更优，那么只可能有一种情况。
所以我们暴力枚举第一行的所有 \(2^5\) 种情况，然后依次往下点击，如果最后矩阵不是全零的就不记录答案。
然后就可以了。
CH0301 递归实现指数型枚举
简单的 dfs+回溯。
CH0302 递归／非递归实现组合型枚举
我们先写一个递归版的，然后模拟系统栈的递归过程即可。
CH0303 递归实现排列型枚举
简单的 dfs+回溯。
POJ 1958 Strange Towers of Hanoi
首先我们考虑原来的 \(n\) 盘 \(3\) 塔问题。
令 \(f_i\) 表示在 \(n\) 盘 \(3\) 塔下，将所有盘子由 \(A\) 移动到 \(C\) 的最少步数。
那么我们考虑递推：
\(f_i=f_{i-1}\times 2+1\)。
也就是先把上面的 \(i-1\) 个盘子移动到 \(B\) 柱，再把最大的移动到 \(C\) 柱，然后把剩下的移动到 \(C\) 。
那么增加到 \(4\) 塔之后，我们需要考虑在所有情况当中取最优，因为你移动的范围不再是被界定成 \(3\) 塔了。
所以推一下可以有：
令 \(g_i\) 表示 \(i\) 个盘子，\(4\) 塔时移动到 \(D\) 柱的最少步数。
那么: \(g_i=\min\limits_{j=1}^{i-1}{g_j\times 2+f_{i-j}}\)。