Public Round #13 题解

旋转序列

来源：

• Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection) Day 1, Problem B
• https://qoj.ac/contest/956/problem/4326

两个串之间 \(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)\)，然后差分即可。

交换豆子

来源：

• Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) Day 2, Problem B
• https://qoj.ac/contest/1686/problem/8731

假设 C 是 1，P 是 0。

枚举第一行最后有多少个 \(1\)，由于 \(1\) 的总个数不变，因此第一/第二行的 \(1\) 的个数是确定的。

假设 \(y\) 坐标为 \([1,2]\)，\(x\) 坐标为 \([1,n]\)，此时我们想要最小化 移动步数 + 最后所有 \(1\) 的 \(x\) 坐标之和，答案就是这个值减去 \(c_1(c_1+1)/2+c_2(c_2+1)/2\)。

上下的移动步数是确定的，只需要最小化向右的移动步数（这些移动步数会增加 \(x\) 坐标，每移动一步会有 \(2\) 的代价，因为要增大 \(x\) 坐标且多移动一次）。

接下来观察一些性质：

• 把一个 \(1\) 从上往下调一定不优。
• 我们可以考虑先做若干次向右移动，直到某个时刻上下调整可以使得上下的个数满足要求，然后再上下调整。

什么情况下可以满足要求？若一列有 \(2\) 个 \(1\)，则这列必须在第二行有一个 \(1\)，也就是有 \(2\) 个 \(1\) 的列不能超过 \(c_2\) 个。

对于一个前缀的若干列，设有 \(sum_i\) 个 \(1\) 和 \(i\) 列，则有 \(\max(0,sum_i-i-c_2)\) 个 \(1\) 必须向右调，需要花费的代价就是 \(\sum 2\times \max(0,sum_i-i-c_2)\)。

对于每种 \((c_1,c_2)\) 维护一个 \(ans_{c_2}\)，交换同一列两个时 \(sum_i\) 不改变；交换不同列时只有 \(1\) 个 \(sum_i\) 会改变至多 \(1\)，只需要在 \(ans\) 上区间加。

用线段树维护 \(ans\) 数组，时间复杂度 \(O(n+q\log n)\)。

序列计数

来源：

• World Tour Finals 2022 Day1, Problem E
• https://atcoder.jp/contests/wtf22-day1/tasks/wtf22_day1_e

考虑转化成一个格路计数问题：

• 有一个 \(n\times m\) 的网格，每次可以往上或往右走，要从 \((0,0)\) 走到 \((n,m)\)。
• 每次从 \((i,j)\to (i+1,j)\) 就确定了 \(a_{i+1}=j\)，称 \((i,j)\to (i+1,j)\) 为横线。
• 对于求 \(\{a_i-i\}\)，可以转化成：画出 \(y=x+k(-(n-1)\le k \le m)\) 的所有斜线，对于每条斜线，若有 \(c\) 个横线在它的上方经过，则将 \(ans_{n-k+1}\dots ans_n\) 加上 \(1\)。

考虑对于每条斜线算贡献，我们想要对于每个 \(c\) 算出，有多少个方案恰有 \(c\) 个横线在它的上方经过。

先特判掉所有没有触碰这条斜线的情况，这部分贡献可以 \(O(n)\) 算出。

枚举这条斜线上的两个位置，钦定这是走的路径第一次、最后一次触碰斜线的位置。

我们有结论：

• 在一个 \(n\times n\) 的网格中从 \((0,0)\) 走到 \((n,n)\)，设所有 \((i,j)\to (i+1,j)\) 在对角线上方经过的次数为 \(c\) 的方案数是 \(ans_c\)，则所有 \(ans_c\) 相等，均为 \(\frac{\binom{2n}{n}}{n+1}\)。

于是钦定第一次、最后一次的触碰位置后，可贡献的 \(c\) 是一个区间，且对于区间中的每个 \(c\) 贡献相等。于是只需要在差分数组上修改。

直接枚举算贡献的复杂度是 \(O(n^3)\) 的，考虑如何优化。

把 \(y=x+k\) 的直线分成 \(k\in [0,m-n]\) 和 \(k\in [-(n-1),-1]\) 两部分。\([m-n+1,m]\) 和 \([-(n-1),-1]\) 是对称的。

考虑 \(k\in [-(n-1),-1]\) 的部分。

假设我们确定了触碰始终点之间的长度 \(len\)，则在差分数组上的修改位置是确定的。

枚举 \(len\)，那这段触碰始终点之间的方案是固定的 \(\frac{\binom{2len}{len}}{len+1}\)，前后两段的形式都是 \((0,0)\to (a,b)\) 且不触碰 \(y=x+(b+1-a)\) 的折线个数（假设把后面一段对称一下）。

把这两段折线拼起来，就变成了一段折线，形式也是 \((0,0)\to (a,b)\) 不触碰 \(y=x+(b+1-a)\)，且 \(a,b\) 只和 \(len\) 有关。这样前后的方案数就变成了两个组合数相减的形式。

再枚举所有的 \(k\) 加起来，发现加减的项抵消了，可以 \(O(1)\) 计算同一个 \(len\) 的方案数。于是这部分能做到 \(O(n)\)。

考虑 \(k\in [0,m-n]\) 的部分。

由于我们是在差分数组上修改，我们可以只关心：对于所有触碰起点/终点，其方案数之和。起点和终点是相似的，下面只考虑起点。

由于起终点之间的方案数就是 \(\frac{\binom{2len}{len}}{len+1}\) 的形式，我们钦定这部分全部在斜线上面走。那折线就变成了 \((0,0)\) 到起点且只在起点触碰斜线 乘上 起点到 \((n,n)\) 并且不穿过斜线。

这样也是两个 \((0,0)\to (a,b)\) 不触碰 \(y=x+(b+1-a)\) 的形式，可以把两段折线拼起来，贡献是两个组合数相减。

再枚举所有的 \(k\) 加起来，发现是要求若干个如下的形式：

观察一下，发现上面加起来是常数，下面加起来也是常数。把这个看作要求 \(\sum_{i=l}^{r} \binom{i}{k}\binom{n-i}{m-k}\)。

先差分成求 \(\sum_{i=0}^{r} \binom{i}{k}\binom{n-i}{m-k}\)。若移动起点 \(p\to p+1\)，则 \(n,m\) 不会修改，\(r,k\) 有 \(O(1)\) 的变化量，则这个式子可以 \(O(1)\) 维护：

• 增大 \(r\) 显然只需要加上一项。
• 增大 \(k\) 的话，考虑这个式子的组合意义是“在 \(n\) 个白球中染黑 \(m\) 个，且第 \(k\) 个黑球的位置 \(\le r\)”。若 \(k\to k+1\)，则限制变成“第 \(k+1\) 个黑球的位置 \(\le r\)”，需要减去第 \(k+1\) 个黑球位置 \(> r\) 的情况。

于是这部分也能做到 \(O(n)\)。