【题解】口胡计划 SDOI2014

BZOJ 3529 [SDOI2014]数表

莫比乌斯反演

BZOJ 3530 [SDOI2014]数数

$AC$ 自动机优化数位 $DP$

BZOJ 3531 [SDOI2014]旅行

考虑到修改并不是很多,并且宗教的总数在 $n$ 级别
直接树链剖分,对于每种宗教维护一个动态开点线段树

BZOJ 3532 [SDOI2014]LIS

考虑搞个最小割加上退流(从小到大)
时间复杂度 $O(n*maxflow(n,n^2))$

没有满流的边必然不在最小割上

BZOJ 3533 [SDOI2014]向量集

如何求 $\max\{ua+vb\}$

$$ ans=ua+vb\\ \frac{ans}{b}=\frac{a}{b}u+v\\ $$

最小/大化 $\frac{a}{b}u+v$ ,取决于 $b$ 的正负

考虑维护一个凸包,一个决策 $(u,v)$ 在图上对应一个点 $(-u,v)$ ,过该点斜率为 $\frac{a}{b}$ 的直线的截距为 $\frac{a}{b}u+v$

那么维护一个上/下凸包,每次查询在凸包上二分即可

BZOJ 3534 [SDOI2014]重建

学习一发矩阵树定理/变元矩阵树定理

题解

Comments

添加新评论