• 欢迎光临~

0801 模拟赛

开发技术 开发技术 2022-08-01 次浏览

真是太难过了,想了一早上 T1,但还是处在会和不会的边缘,尽早退役尽早退役。


T1

给定一个根为 (1)(n) 个节点的树,每个节点初始无色。一次操作可以选定一个点 (i),将 (i) 子树内的所有点覆盖为任意颜色。求将所有叶子变为指定颜色的最少操作次数。

(n leq 2times 10^6)


虽然我现在还不会,但我梳理一下思路,说不定就会了呢。

首先染色一定上至下,否则不优。所以可以考虑 (dp_{i,j}) 表示若 (i) 的子树内已经全部被染成 (j),使其达成条件的最小步数。

然后 (u) 的转移是形如,所有儿子第二维对位相加,然后找出 (mn=min_j{dp_{u,j}}),将所有 (dp_{u,j})(mn+1) 取较小值。看起来是可以线段树合并的,但这属实很不优美。

(mn+1) 取完最小值之后,(dp_u) 的差就小于等于 (1) 了,再向上合并时我的决策一定是取,在儿子中作为 (mn) 次数最多的那一个。所以我只需要知道这个颜色作为 (mn) 的总次数即可。

所以说不能干想,及时梳理思路还是很有必要的,我现在好像就会了。相当于我维护 (f_u) 表示作为 (u) 点的 (mn) 的所有颜色的集合,然后向上合并时当然是找出儿子的 (f) 的可重集的并中出现次数最多的那些作为 (f_u)。那么我需要维护一个 (cnt_i) 表示 (i) 颜色作为儿子的 (mn) 出现了多少次,判断 (i) 是否在 (f_u) 内就只需要记录 (max{cnt_i}) 即可。每个节点开哈希表记录 (cnt),然后启发式合并就好起来了。

程序员灯塔
转载请注明原文链接:0801 模拟赛
喜欢 (0)