流离之人追逐幻影。
BZOJ2705
小学生公式题
$$\sum_{i=1}^n (i,n)=\sum_{d>0}d\times \phi(\frac{n}{d})$$
然后就没了= =
BZOJ2706
三合一超值版
第一问黑白染色最大流
第二问分治得到公式$Ans=frac{NM-1}{3}$
第三问DLX模板，用精确覆盖模型：
01矩阵中，每一行用一个三元组$(i,j,k)$表示棋盘中$(i,j)$这个格子放$k$号方块的左上角，每一列用一个二元组$(x,y)$表示“$(x,y)$这个格子只能被放一次”这个限制
那么矩阵中每个位置被一个二元组$((i,j,k),(x,y))$描述，它的值是1当且仅当第$k$种方块的左上角放置在棋盘的$(i,j)$这个格子时，棋盘的$(x,y)$这个格子会被覆盖
这样子一来的话，由于每列只会选一个1，所以每个格子只会被覆盖一次
DLX的时候加点剪枝就能卡过去了
不知这是否标算？
BZOJ2707
容易发现，如果是个DAG，就能一遍Dp出解
如果是个比较小的一般有向图，也可以用高斯消元求解：
设$f_i$表示走到点$i$的期望步数
$$f_i=\sum_j(f_j+1)\times P_{j,i}$$
但是这题这个图很大，接受不了高斯消元。可是发现题目有个奇怪的限制：强连通分量大小不超过100
那么我们按照拓扑序，对于每个强连通分量高斯消元，然后后面的强连通分量向前面的强连通分量更新一下答案就可以了
BZOJ2726
不知道那次比赛的题，也不知道为何sdoi2012在bzoj上就这么四题
傻逼斜率优化，注意时间会是负数，那么每次决策更新就不是取队头了，而是到单调栈里面二分一下
也可以CDQ吧，我已经忘记斜率优化用CDQ怎么写了