YOU'VE MADE A BRAVE DECISION, WELCOME.

流离之人追逐幻影。

SDOI2012 Round1 Day1

抱怨无济于事

T1 Longge的问题

BZOJ2705
小学生公式题
$$\sum_{i=1}^n (i,n)=\sum_{d>0}d\times \phi(\frac{n}{d})$$
然后就没了= =

T2 棋盘覆盖

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的时候加点剪枝就能卡过去了
不知这是否标算?

T3 走迷宫

BZOJ2707
容易发现,如果是个DAG,就能一遍Dp出解
如果是个比较小的一般有向图,也可以用高斯消元求解:
设$f_i$表示走到点$i$的期望步数
$$f_i=\sum_j(f_j+1)\times P_{j,i}$$

但是这题这个图很大,接受不了高斯消元。可是发现题目有个奇怪的限制:强连通分量大小不超过100
那么我们按照拓扑序,对于每个强连通分量高斯消元,然后后面的强连通分量向前面的强连通分量更新一下答案就可以了

Extra 任务安排

BZOJ2726
不知道那次比赛的题,也不知道为何sdoi2012在bzoj上就这么四题
傻逼斜率优化,注意时间会是负数,那么每次决策更新就不是取队头了,而是到单调栈里面二分一下
也可以CDQ吧,我已经忘记斜率优化用CDQ怎么写了