NOIP2022模拟赛二 By YJC 10.20
NOIP2022模拟赛二 By YJC 10.20
yzxoi
2022-10-20 (Updated: 2022-10-20)
A P1330 封锁阳光大学
每个连通块单独考虑，分别黑白染色，取黑白中数量较小即可。
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，均挂在深度最小的节点上，之后树上差分统计即可。
若碰到与当前颜色相同的点，之后该子树将失效，贡献更新。
注意根节点父亲颜色应设为“全彩”，特殊考虑即可。
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-10-20
，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录