题解：P10872 [COTS/CETS 2022] 移位 Maliand

Rainbow_qwq · 2024-08-17 10:13:24 · 题解

两个串之间 1 匹配的次数总和为 k\times l，并且共有 n 次匹配。

于是答案的下界为 k\times l 个球放进 n 个盒子，最小化最大的盒子中的 1 个数，也就是 \lceil \dfrac{k\times l}{n} \rceil。

设 ans = \lceil \dfrac{k\times l}{n} \rceil，我们可以构造来达到这个上界：

• 对于第一个串，将前 k 个位置变成 1。
• 对于第二个串，设这个串的前缀和数组为 sum_i。设 sum_i = \min(\lfloor\dfrac{(i+1)\times ans}{k} \rfloor,l)，然后差分即可。