11.12 写题

AGC002

已经单独开题解写了就不放在这里了(

CF1179C

看题就会了贪心。。最后那个线段树卡了好久。。不会找最后一个大于 00 的位置是不是没救了啊。。

考虑贪心,我们把 ai,bia_i,b_i 放到数轴上,然后从后往前扫。扫到一个 bib_i 就给维护的值 -1 ,扫到 aia_i+1 ,也就是做一个类似括号匹配的东西。我们要找到的就是第一个位置,满足这个位置的值大于 00

所以我们直接开一棵值域上的线段树。把 bib_i 的修改看成删除一个 bib_i 再加入一个新的,也就是前缀的 +1,1+1,-1 操作。然后对每个区间维护最大值,每次在线段树上如果右儿子大于 00 就尽量往右走即可。复杂度 O(qlogv)O(q\log v)

CF1179D

手玩一下样例可以发现,本质上就是找一条路径,满足路径上每个点在非路径子树的 siz×(nsiz)siz\times (n-siz) 的和尽量大。

首先有一个类似直径跑两遍的高论做法。

证明就直接粘你谷题解的了,画一下会发现非常有道理。关键点在于一条路径本身的权值和根的位置的选取没有关系。

V_3E3CD_0U4B2HAIDFL___U.png

一种更加靠谱的换根做法。考虑 dp[u][0],dp[u][1]dp[u][0],dp[u][1] 分别表示 11 为根 uu 向下的路径的最小去除路径方向的 sizsiz 平方的和。不难发现最优的解一定是选择两个叶子,所以说如果根不是叶子,那么最优解在这棵树上一定是两个儿子拼起来得到的。所以平方和的最小值就是就是最小的

dp[u][0]+dp[u][1]+(nsiz1si2)2dp[u][0] + dp[u][1] + (n-siz_1-si_2)^2

然后就做完了。两个做法都有代码。

为啥会有人写斜优呢?

\