JOI Open 2020
lgswdn_SA
·
·
个人记录
C
设 f_u 表示选择的发电站恰好被包含在了 u 子树内的最大值；g_u 表示承诺 u 子树外一定会有别的发电站时子树最大值。
于是我们对于没有发电机的点，有 f_u=g_u=\sum g_v；对于有发电站的点有 f_u=1+\sum g_v,g_u=\max(1,-1+\sum g_v)。
A
继'随便做'之后，又有了'暴力做'。
对于判断是否可行，维护每条对角线的 $f$ 之和，如果当前修改的节点的对角线的 $f$ 之和 $=1$（即自己）那么肯定就不行。
# B
感觉自己的思维被碾压了。
对于任意匹配 $b_i-w_i$，若存在 $i,j$ 满足 $b_i<b_j<w_j<w_i$（小于号指在环上的按照顺时针的偏序关系），那么我们交换一下，让 $b_i-w_j$，$b_j,w_i$ 进行匹配答案一定更优。于是，我们合理外推一下，不断调整后得到的匹配一定长成 $b_i-w_{i+p}$ 的样子（加法表示沿顺时针走 $p$ 步）。于是乎，$b_i-w_{i+p}$ 会与所有 $b_i<b_j<w_{i+p}$ 的组相交，设匹配的长度为 $l$，那么一个匹配的贡献即为 $n-|l-n|$，我们只需要最小化 $\sum |l-n|$ 即可。