bzoj 4518: [Sdoi2016]征途 DP 斜率优化

原式可以化简成  m * sum(xi^2)(i = 1 – > m) – sum(xi)(i = 1 -> m)

如果你很好奇为什么可以化成这个形式,请注意一个事实。x的平均值*m是等于所有的和。

我们发现我们无非就是求最小的sum(xi^2)(i = 1 -> m)[……]

Read more

bzoj 4443: [Scoi2015]小凸玩矩阵 二分+二分图匹配

题解:

求第k大,我们转化成求第n-k + 1小。然后我们二分一个值。对于原始矩阵如果mp[i][j]  <= x,那么我们就在行列的二分图里把i行和j列连上。然后跑一边二分图匹配,如果不小于n-k+1,那么认为结果可以更小。

我开始一直不太确定算法正确性,你能满足n-k+1个小的[……]

Read more

bzoj 4196: [Noi2015]软件包管理器 树链剖分

裸的树剖写到近200行,线段树还写错了,quq。感觉自己成老年选手了。

平时都写得bfs的树剖,然后这种写法貌似不支持子树dfs序列在线段树上连续这个特点,quq。还换了板子。。。。

按dfs构建top,和线段树序列,可以发现一颗子树在序列上是连续的。显然序列的开始是这个子树的根,然后再[……]

Read more