NOIP2022模拟赛二 By YJC 10.20

NOIP2022模拟赛二 By YJC 10.20

A P1330 封锁阳光大学

每个连通块单独考虑，分别黑白染色，取黑白中数量较小即可。

90701973

B CF436E Cardboard Box

对于每个关卡，分成两类：

• 2a_i\leq b_i：将选两个点拆成 a_i 与 b_i-a_i，有 a_i < b_i - a_i
• 2a_i > b_ib_i 排序，此时一定先选两个更优。

一类点直接拆散按从小到大排序选即可。

考虑枚举选一类点 i 个，则剩余 m-i 个点填二类点分 m-i 的奇偶性判断：

• m-i 为偶数：恰好选前 (m-i)/2 个两个即可。
• m-i 为奇数：选 (m-i-1)/2 个两个，再加上一个一个；或选 (m-i+1)/2 个两个，再将其中一个两个转为一个。

显然奇数情况记前/后缀最小/大值即可。

C AcWing 359. 创世纪

在一内向基环树森林上选若干点，使每个点必有一个儿子没选，求权值和最大。

表示当前点选/不选的最大值。

考虑非树边 x\rightarrow y，有两种情况：

• 不选 y，则 x 无限制。
• 选 y，对 x 无影响，可直接将 x\rightarrow y 断开。

两者取最大即可。

D P2664 树上游戏

对于每个点，每种颜色，其单独答案贡献可转化为 n-siz_{x,c}。

其中 siz_{x,c} 代表从点 x 出发，不经过颜色 c 的点，所构成的连通块大小。

考虑对于所有 siz，均挂在深度最小的节点上，之后树上差分统计即可。

若碰到与当前颜色相同的点，之后该子树将失效，贡献更新。

注意根节点父亲颜色应设为“全彩”，特殊考虑即可。