2024.10.15总结

本文于 github 博客持续更新

但是我 A 没去 freopen

A：

随机数据大🐍。

对于一个 \(a\)，至多有一个 \(b=a-n\bmod a<a\)，因此所有点构成一个森林。

对于两个点暴力跳祖先即可，数据随机，期望每次缩小一半，可过。

B：

首先每行保留前 \(m\) 个点，这样有效点数就减少到了 \(m^2\) 量级，每次钦定右侧某个点必选，再枚举与它匹配的左侧点，这就要求排在当前这个点前的右侧点都能被其他左侧点选择，加入队列重复这个过程即可，若队列长度大于 \(m\) 则直接跳出。

C：

考虑拆贡献，等价于对于每个点集，选一个给出 \(a_i\) 的贡献，剩下是 \(1\) 的贡献，加起来。

记 \(dp_{i,j,k}\) 表示 \(i\) 子树里，有 \(j\) 个点未被取且给出 \(1\) 的贡献，\(k\) 个未被取且给出 \(a_i\) 的贡献。

分类讨论当前子树根是否取，转移即可。

核心代码这样：

D：

*3500 改牛魔。