2023.9 练习

\(9.1\)

鸽。

\(9.2\)

模拟赛。

难度大概是 \([2300,2400]+[2900,3300]+?\)。

• \(\text{A}\)：

给定一个正整数序列 \(\{a_n\}\)，和一个初始全 \(0\) 的整数序列 \(\{b_n\}\)，每单位时间 \(\forall i\in [1,n],b_i\gets b_i+1\)。
定义对于 \(b_j\) 的一次操作为操作后该 \(b_j\) 不再执行 \(b_j\gets b_j+1\) 操作。
求一个最大的 \(k\) 满足：可以每隔 \(k\) 单位时间做若干次个 \(b_i\) 进行操作，使得最终 \(b_i\ge a_i\) 且 \(\sum\limits_{i=1}^n b_i-a_i<m\)。
\(n\le100,a_i\le10^9,m\le10^{11}\)。

显然我们对于 \(a_i\) 要求不小于 \(a_i\) 的最小的 \(b_i\)，易得 \(b_i=\lceil \frac{a_i}{k}\rceil\Rightarrow b_i-a_i=(-a_i)\bmod{k}\)。

即题目转换为求最大的 \(k\) 使得 \(\sum\limits_{i=1}^m ((-a_i)\bmod{k})<m\)。

考虑单调性，但这个柿子显然没有单调性。

考虑为什么没有单调性，\(a=bq+r\Rightarrow r=a-bq\)，由于 \(a\) 均为常数，所以 \(r\) 的值由 \(bq\) 决定，\(bq=\lfloor \frac{a}{b}\rfloor b\)。设 \(b'>b\)，则当 \(\lfloor \frac{a}{b}\rfloor=\lfloor \frac{a}{b'}\rfloor\) 时 \(b'q>bq\Rightarrow r'<r\)。也就是说，当 \(\lfloor \frac{a}{b}\rfloor\) 相同时，\(a\bmod{b}\) 具有单调性。

考虑整除分块，对于 \(a\)，其 \(\lfloor \frac{a}{b}\rfloor\) 的值至多只有 \(\sqrt{a}\) 个。

则我们对于每个 \(a_i\) 做一个整除分块，然后把所有使得 \(\lfloor \frac{a_i}{b}\rfloor\) 的 \(b\) 丢到一个 vector 里面，然后排个序去个重，对于所有的 \(k\in [t_i,t_{i+1}]\) 原式具有单调性，二分即可。

复杂度 \(\Theta(n\sqrt{V}\log V)\)。

• \(\text{B}\)：

Too Hard。

• \(\text{C}\)：

Too Hard。