校际交流模拟总结（updating）

标签：rt sz updating 校际 cdot dep 枚举 模拟 dp

前言

由于上次补总结补了一整天多，决定每天及时写总结。

校际交流，但是被本校的人吊打。

---

Day 1

总体情况

都是 CF 6月24日 Div1+Div2 的原题，早知道多打点 CF 了。

T1 考场降智没想出来，后面暴力基本上都打了。

60+20+50+20=150，rk3

怎么一回家就会 T1 了啊！

T1

CF1842C

一眼 DP，只会 \(O(n^3)\) ，瞎优化一下变成 \(O(n^2)\)。

其实再小优化一点就可以 \(O(n)\) 了，但是优化的时候有个 sb 错误，没调出来，只能交暴力。

算是比较简单的优化吧，转移的时候记录每种颜色最大值，去掉枚举最大值的 \(O(n)\)。

Div 2 C 都不会了，废

CODE

---

T2

CF1842D

---

T3

CF1842F

50pts

枚举所选点数 \(cnt\)，然后树上背包板子，\(dp[x][j]\) 表示 \(x\) 子树内选 \(j\) 个点，子树内所有边对答案的贡献。

\[dp[x][j]=\max_{y \in son_x}(dp[x][j-k]+dp[y][k]+abs(cnt-k-k)) \]

然而我太弱了，树上背包调了一个多小时。

100pts

事实上这是 CF 的题，或许不会考这么裸的模板。所以正解是贪心。

绝对值很麻烦，所以用一些神奇的操作把绝对值去掉了。

可以找到树的黑点的重心，即某个点，它的子树内黑点个数的最大值最小，易证重心任一子树内黑点个数不过半，绝对值就去掉了。

然后以重心为根，求出每个点的深度 \(dep[i]\) ( \(dep[rt]=0\) ).

设 \(sz[i]\) 表示以 \(i\) 为根子树中黑点的个数，答案为

\[\sum_{i \neq rt} k-2 \cdot sz_i = k\cdot (n-1)- 2 \cdot \sum_{i \neq rt} sz_i \]

对于每个点会对除了根之外所有的祖先的 \(sz\) 产生 1 的贡献，所以化为

\[k\cdot (n-1)- 2 \cdot \sum_{i \neq rt,col_i=black} dep_i \]

要求贡献最大，所以要最小化 \(dep[i]\) 的和。

所以贪心地选深度最小的点。

关于重心，直接枚举就行了，如果枚举到非重心，可能导致 \(k - 2 \cdot sz_i\) 变负，只会让答案偏小，取 \(\max\) 后不影响结果。

感觉很巧妙。

时间复杂度 \(O(n^2)\)。

CODE

标签：rt,sz,updating,校际,cdot,dep,枚举,模拟,dp
From： https://www.cnblogs.com/wonderfish/p/17601873.html