Codeforces 2258 B2 题解（临时文档）

Codeforces

---

题目大意

给定 $n$ 根胡萝卜，长度分别为 $a_1, a_2, \dots, a_n$（$1 \le a_i \le m$）。
有一台切割机，每次操作可以同时选择任意多根胡萝卜（已切出的也可以再选），并对每根被选的胡萝卜执行：若其长度 $l \le x$ 则不变，否则切成 $x$ 和 $l-x$ 两段（$x$ 为正整数，每次操作可不同）。

对于每个 $k = 1, 2, \dots, m$，问恰好使用 $k$ 次操作后，最多能选出多少根长度完全相同的胡萝卜（所有选出的长度必须一致）。
每个 $k$ 独立求解，互不影响。

---

核心观察

1. 固定目标长度 $x$ 时的最优切割策略

若我们希望最终得到尽量多长度为 $x$ 的胡萝卜，那么对于每一根原始胡萝卜，最优的切割顺序是从大到小切：

$$x \cdot 2^{k-1},\; x \cdot 2^{k-2},\; \dots,\; x \cdot 1$$

即第一刀先切出 $x \cdot 2^{k-1}$ 的块（如果原长度足够），第二刀切 $x \cdot 2^{k-2}$，依此类推。这样能保证在 $k$ 刀内获得尽可能多的 $x$ 小块。

---

2. 单根胡萝卜对固定 $(k, x)$ 的贡献公式

设当前操作次数为 $k$，目标长度为 $x$。令：

$$\text{lim} = 2^k$$

对于某一根长度为 $a$ 的胡萝卜：

• 若 $a = \text{lim} \cdot x$，则恰好可以切出 $\text{lim}$ 根长度为 $x$ 的胡萝卜，贡献为 $\text{lim}$。
• 否则，贡献为：

$$\min\left(\left\lfloor \frac{a}{x} \right\rfloor,\; \text{lim} - 1 \right)$$

解释：
- $\lfloor a/x \rfloor$ 是长度 $a$ 理论上最多能包含的 $x$ 的个数。
- 但由于只有 $k$ 次切割，最多只能切出 $\text{lim} - 1$ 个完整的 $x$ 小块（因为要得到 $\text{lim}$ 个整块需要恰好的整除条件，否则缺一刀）。
- 两者取小即为实际贡献。

---

3. 最优 $x$ 的取值范围

当 $k$ 固定时，若目标长度 $x$ 太大，使得 $\text{lim} \cdot x > m$，则没有任何胡萝卜能触发“特殊贡献”，且所有 $\lfloor a_i / x \rfloor$ 都会很小甚至为 0，答案必然劣于取更小的 $x$。
因此最优解只需要考虑：

$$1 \le x \le \frac{m}{\text{lim}}$$

若 $\frac{m}{\text{lim}} < 1$，则唯一有用的 $x$ 是 $x = 1$，且此时答案就是所有胡萝卜长度之和（因为全部切成 1）。

---

快速计算方法（困难版的关键优化）

如果直接枚举每个 $k$ 和每个 $x$，再对 $n$ 根胡萝卜求和，复杂度为 $O(nm)$，不可接受。
我们需要利用长度值域 $m$ 和前缀和来加速。

预处理

• 开数组 cnt[1..m]，其中 cnt[v] 表示长度为 $v$ 的胡萝卜的数量。
• 计算前缀和：

$$\text{pref}[i] = \sum_{v=1}^{i} \text{cnt}[v]$$

则任意区间 $[L, R]$ 内的胡萝卜总数可在 $O(1)$ 得到：

$$\text{count}(L, R) = \text{pref}[R] - \text{pref}[L-1]$$

---

固定 $(k, x)$ 时，使用分段求和

对于固定的 $x$，将所有胡萝卜按 $\lfloor a_i / x \rfloor$ 的值分组。
令 $d = \lfloor a_i / x \rfloor$，则 $d$ 相同的胡萝卜长度落在区间：

$$[d \cdot x,\; (d+1) \cdot x - 1]$$

这些胡萝卜的数量可以直接用前缀和求出：

$$\text{cntGroup}[d] = \text{pref}[\min(m,\; (d+1)x - 1)] - \text{pref}[d \cdot x - 1]$$

这一组对总答案的贡献为：

$$\text{cntGroup}[d] \times \min(d,\; \text{lim} - 1)$$

我们将 $d$ 从 $0$ 到 $\lfloor m / x \rfloor$ 全部累加，就得到了常规部分的总贡献。

---

处理特殊情况

当存在长度为 $\text{lim} \cdot x$ 的胡萝卜时，这些胡萝卜在常规部分被算作 $d = \text{lim}$，贡献为 $\text{lim} - 1$，少算了 $1$。
因此需要额外加上：

$$\text{cnt}[\text{lim} \cdot x]$$

（仅当 $\text{lim} \cdot x \le m$ 时存在）

---

总复杂度分析

对于固定的 $x$，内层循环次数为 $\frac{m}{x}$。
有效的 $x$ 范围是 $1 \le x \le \frac{m}{\text{lim}}$，且 $\text{lim} = 2^k$。

对所有 $k$ 求和：

$$\sum_{k=1}^{\log_2 m} \sum_{x=1}^{m/2^k} \frac{m}{x} = m \cdot \sum_{k=1}^{\log m} O\left( \log \frac{m}{2^k} \right) = O(m \log^2 m)$$

当 $m \le 2\cdot 10^5$ 时，$\log^2 m \approx 324$，实际运行效率完全可行，题解中记为 $O(m \log m)$（将对数平方视作小常数）。

预处理 $cnt$ 和 $pref$ 需要 $O(m)$，总复杂度满足题目限制。

---

正确性证明概要

1. 切割顺序最优性：
   每次切出当前最大可获得的 $2^j \cdot x$ 块，保证在 $k$ 次内最大化 $x$ 小块数量，这是贪心最优（可通过归纳证明）。

2. 贡献公式的正确性：
   对任意长度 $a$，它至多包含 $\lfloor a/x \rfloor$ 个 $x$，且 $k$ 次切割最多产生 $2^k - 1$ 个完整小块（除非正好整除产生 $2^k$ 个）。公式精确刻画了这两种情况。

3. 枚举范围的正确性：
   若 $x > m / 2^k$，则 $\text{lim} \cdot x > m$，没有任何胡萝卜能贡献 $2^k$，且所有 $\lfloor a_i/x \rfloor = 0$ 或很小，答案不会超过取 $x=1$ 的情况，因此可忽略。

4. 分段求和正确性：
   将所有胡萝卜按 $\lfloor a/x \rfloor$ 分组，同组贡献相同，利用前缀和统计数量，结果等价于逐项累加。

---

注意事项

• 当 $k$ 较大（$2^k > m$）时，后续答案均等于所有胡萝卜长度之和（因为全部切成 1 后，总根数就是总长度），可以快速跳出循环。
• 所有测试用例的 $n$ 和 $m$ 总和均不超过 $2\cdot 10^5$，预处理和循环总次数在可接受范围内。
• 本解法对于 hard version 的 $k$ 从 1 到 $m$ 独立求解完全适用。