The 2021 China Collegiate Programming Contest (Harbin)¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 9/495 | 9 | 10 | 12 |
A¶
upsolved by
题意¶
题解¶
C¶
upsolved by JJLeo
题意¶
\(n\) 个节点树，\(1\) 为根，每次操作可以将一个子树的叶子节点染成同一个颜色，现给定每个叶子需要变成的颜色，问最少需要操作几次。(\(1 \le n \le 10^5\))
题解¶
考虑暴力 dp，设 \(f_{i,j}\) 表示若节点 \(i\) 的所有叶子颜色为 \(j\)，最少需要操作几次满足条件。一个需要注意的是细节是，对于固定的 \(i\)，\(\displaystyle \max_j f_{i,j}\le\left(\min_j f_{i,j}\right)+1\)，这是因为可以对 \(i\) 子树操作一次将所有叶子颜色变为 \(\displaystyle \min_j f_{i,j}\) 对应的 \(j\)。设 \(S_i\) 是节点 \(i\) 儿子节点的集合，转移为： $$ f_{i,j}=\sum_{k \in S_i} \min\left[f_{k,j},\left(\min_j f_{k,j}\right)+1\right] $$ 最终答案为 \(\displaystyle \left(\min_j f_{1,j}\right)+1\)。
直接转移是 \(O\left(n^2\right)\) 的。整个过程可以抽象为，对于节点 \(i\)，先令： $$ f_{i,j}=\sum_{k\in S_i}f_{k,j} $$ 再令： $$ f_{i,j}=\min\left[f_{i,j},\left(\min_j f_{i,j}\right)+1\right] $$ 子树内没有的叶子颜色其值必然为 \(\displaystyle \left(\min_j f_{i,j}\right)+1\)，如果只保留子树内叶子颜色对应的 \(j\)，利用启发式合并 + map，复杂度降为 \(O\left(n \log ^2 n\right)\)。
具体的细节是，每个节点维护 \(g_i=\displaystyle \left(\min_j f_{i,j}\right)+1\)，同时维护一个 map，所有 \(f_{i,j}\) 为最小值的 \(j\) 其在 map 中的值为 \(-1\)。
合并 map 中的值的同时维护最小值，并用一个 vector 存储有哪些 \(j\) 为最小值，最后将 map 清空，并将 vector 中的 \(j\) 在 map 中设为 \(-1\)。但启发式合并可能使两个 map 互换，此时不能把大 map 中的值全部放到 vector 中，否则这样不符合启发式合并会 TLE。注意到这个大 map 里面的最小值为 \(-1\)，因此最后判断如果最小值仍为 \(-1\)，不清空 map 仍保留即可。
合并过程中累加每个儿子的 \(g_k\)，用其减去最小值再加 \(1\) 即得到 \(g_i\)。
D¶
upsolved by
题意¶
题解¶
F¶
upsolved by
题意¶
题解¶
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
I¶
upsolved by
题意¶
题解¶
K¶
upsolved by
题意¶
题解¶
L¶
upsolved by
题意¶
题解¶
记录¶
0h：ZYF看I签到开始写，MJX看B签到，CSK看E签到。ZYF写完发现读错题了捏，ZYF重写，ZYF发现又想错了捏。MJX写B，MJX写完，ZYF写J，ZYF写完J CSK写E，CSK写完E感觉F能暴力就写了。MJX想了想感觉也好tm对，然后CSK写了过了，15ms的奇迹。MJX猜了I结论，感觉好对ZYF开写，MJX看D。ZYF写完了MJX大概看了看差不多交了，WA了。
1h：MJX看D感觉完全nm不可做，63位爬吧，瞅了瞅ZYF的提交，发现每个位置只改了1次，ZYF改了过了。CSK给喂G题意，是个sb题，ZYF写了过了。CSK看D发现是 \(2^{63}\)，MJX nt看成了 \(10^{63}\)，寄捏。ZYF开始打暴力，打完寄了，第一次没有二进制位运算少减1。
2h：CSK发现没算前导0，寄了捏。开始想CH，C想了半天感觉只会暴力 \(O(n^2)\)，CSK感觉会乱搞点给ZYF说了说，搞了搞WA3开润。
3h：MJX感觉H和最近arc一道题一样，给了个结论ZYF开冲写了过了捏。看了看L，ZYF感觉是个比较模板的AC自动机，直接开冲。MJX和CSK继续研究逆天C。
4h：ZYF写完一发过了，C研究了一堆乱搞方法，最后甚至用上了线段树合并（赛后：直接线段树合并就行了捏，太早训练笨比了捏）。寄！
After：MJX A题n范围也看错了捏，芜湖。