A. Rectangle Cutting

随便模拟一下

code

B. Equalize

我们设众数为 $x$，那么数量就是数组 $a$ 与 $x - n, x - n + 1, \cdots , x - 1$ 的重叠部分，于是用双指针即可。

code

C. Physical Education Lesson

枚举一下该点在上坡还是下坡，找到对应的零点，那么符合的 $k$ 满足

• $2k - 2 \mid n + x - 2$ 或 $2k - 2 \mid n - x$
• $x \leq k$

根号复杂度枚举一下 $n + x - 2$ 和 $n - x$ 的因子即可。

code

D. Lonely Mountain Dungeons

注意到 $\sum c_i \leq 2 \cdot 10^5$，设 $f_i$ 表示有 $i$ 个小组时军队的最大兵力。

对于一个种族来说，设其有 $a$ 个生物，且有 $y$ 个小组，容易发现每个队伍中该种物种数量尽量平均时，总兵力最大。

设 $k = \lfloor \frac{a}{y} \rfloor, k’ = a \bmod y$，

我们反过来求在同一队伍中的对数，那么总兵力为 $\left( \frac{a(a - 1)}{2} - \frac{k(k - 1)}{2} \cdot a - k’ \cdot k \right) b - x(y - 1)$。

其中 $\frac{a(a - 1)}{2}$ 这一项是固定的，所以提前累计，先忽略，那么当 $y > a$ 时 $a$ 对 $y$ 没有贡献。

对于每一个 $a$，枚举 $y \in [1, a]$，答案累计在 $f_y$ 上，时间复杂度 $O(\sum c_i)$。

注意多组数据不要用 memset，手动清空。

code

E. Modular Sequence

我们发现对于 $a_i(1\leq i\leq n)$，一定满足 $a_i \equiv x \pmod y$。

赋值 $s := \frac{s - (x \mod y) * n}{y}, x := \lfloor \frac{x}{y} \rfloor$ （$s - (x\bmod y) * n$ 不是 $y$ 的倍数或小于 $0$ 则判无解）。

于是题目变为 $a_1 = x$，$a_i := a_{i-1} + 1$ 或 $a_i = 0$。

先设 $a_1 = 0$，那么朴素的 $dp$ 是 $O(nS)$ 的。

设 $f_i$ 表示序列总和为 $i$ 时序列的最短长度，用 $dp$ 可以在 $O(S\sqrt{S})$ 的复杂度求出 $f$。

如果 $f_s \leq n$ 则有解，因为最后可以一直赋值 $0$。

然后考虑 $a_1 = x$ 的情况，枚举该连续上升段的终点即可。

那如何输出序列呢？计算 $f$ 的时候记一下路径就行。

总时间复杂度 $O(S \sqrt{S})$。

code