比赛：LGR236 Div.2

chenwenmo · 2025-08-10 19:11:35 · 题解

LGR236 Div.2

T1. 传奇模数

简单题。

Code

T2. 未送出的花

假设有 x，对于盛开度 < x 的点的盛开度设为 -1，对于 \ge x 的点的盛开度设为 1，定义一个点的权值为它到根路径上的点盛开度之和，

那么若一个点的权值 \ge 0，则代表该点的美丽值 \ge x，

也就是说我们要在树上填 n-x+1 个 1，x-1 个 -1，使得权值 \ge 0 的点数量尽量多，假设这个数量最大为 y，那么 [1,y] 的答案都 \ge x，

考虑如何求这个最大数量。发现如果存在儿子是 1，父亲是 -1，那么把儿子和父亲的 1,-1 交换是一定不劣的。因此得出结论：填 1 的点一定构成包含树根的连通块。

考虑用树形背包求这个东西。如果直接设 f(u,i) 表示以 u 为根的子树中，填 i 个 1 的最大答案，没办法转移。

那么就要考虑利用上面得到的结论。即，如果一个点填 1，那么它到根路径上的所有点都填 1。那么对于每个点，只需要计算它选了之后，会比它父亲多出几个点即可。把它父亲以及祖先的贡献留到上面计算，就不用担心少算贡献了。

至于如何计算每个点比父亲多出的贡献，也是好计算的。赛时多写了一个 DP，f(u,i) 表示 u 子树内距离 u 为 i 的点的数量。实际上不用这么复杂，可以直接 dfs 一遍预处理。

那么背包状态就是，g(u,i) 表示根到 fa_u 路径上点全部填 1，u 子树内选了 i 个点填 1 多出的最大贡献。

Code

T3. 逻辑推理

T4. 污水博弈

设某个区间的污水高度为 x，选到这个区间的概率为 P，序列一共分成 i 段，能出现该区间的划分方案数为 Q，那么它对期望的贡献为：