NOIP2022模拟赛二 By YJC 10.20

2022-10-31 10:29:50 浏览数 (1)

NOIP2022模拟赛二 By YJC 10.20

yzxoi

2022-10-20 (Updated: 2022-10-20)

oi

暴力, 树上差分, 树形 DP, 贪心

A P1330 封锁阳光大学

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

90701973

B CF436E Cardboard Box

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

  • 2a_ileq 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 个两个，再将其中一个两个转为一个。

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

177110807

C AcWing 359. 创世纪

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

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

f_{u,0} = sum_{vin subtree_u} max{f_{v,0},f_{v,1}}
f_{u,1} =(sum_{vin subtree_u} max{f_{v,0},f_{v,1}}) - (min_{vin subtree_u}max {0,f[v][1]-f[v][0]} ) 1

考虑非树边 xrightarrow y，有两种情况：

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

两者取最大即可。

18236699

D P2664 树上游戏

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

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

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

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

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

dp

0 人点赞