CF924 简要题解

SegTree · 2024-02-11 20:24:10 · 个人记录

场切 ABCDE，故这里没有 F 的

A

简单分讨

B

把 a 排序后双指针即可

C

分讨这个 a_n 落在前面一段还是后面一段。

分别得到 2k-2 是 n-x 和 x+n-2 的因数，直接枚举即可。

D

枚举队伍的数量，对于每种生物分配方案可贪心，时间复杂度 \mathcal{O}(n^2)。注意到 \sum c\le 2\times 10^5，所以不同的 c 只有 \sqrt{2\times 10^5} 种，直接枚举这些 c 再乘以等于该值的个数即可，\mathcal{O}(n\sqrt{n})。

E

注意到序列里每一项模 y 都等于 x 模 y。

显然无解的 case：

• nx \bmod y\ne s \bmod y
• x+(n-1)\times(x\bmod y)>s

然后我们令 a_1=x，a_{2,\cdot n}=x\bmod y

考虑剩下还需要的增量，每次增量只能增加 y，为方便除以 y。

你可以改变一段长度为 m+1 的区间，使它们分别产生 0,1,\cdots m 的增量，可视为一个完全背包，物品的体积为 m\times (m+1)/2，贡献为 m+1，最小化贡献，物品只有根号级别，可直接预处理。

然后枚举 x 开始的那一段的位置 i，判断剩余所需增量的贡献是否 \le n-i，填上后剩下全填 x\bmod y 即可。