Crysfly的博客

博客

Tags
None

Public Round #13 题解

2024-06-30 13:52:50 By Crysfly
  • 搬题人
    • 旋转序列:p_b_p_b
    • 交换豆子:Crysfly
    • 序列计数:Lynkcat
  • 组题人
    • Lynkcat
  • 题解:Crysfly

旋转序列

来源:

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

交换豆子

来源:

假设 C1P0

枚举第一行最后有多少个 $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)$。

序列计数

来源:

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

  • 有一个 $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-c+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 [m-n+1,m]$ 的部分。

假设我们确定了触碰始终点之间的长度 $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_{k=0}^{m-n}\binom{2p+k}{p}\binom{n+m-k-2p}{n-p}$$

观察一下,发现上面加起来是常数,下面加起来也是常数。把这个看作要求 $\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)$。

鱼跃龙门

2024-05-28 18:00:01 By Crysfly

/yuhaodu

2024-03-29 16:56:47 By Crysfly

/yuhaodu/yuhaodu/yuhaodu/yuhaodu/yuhaodu/yuhaodu

膜拜传奇特级大师周康阳大佬

2023-05-16 18:53:06 By Crysfly

Rainbow_sjy

Rainbow_sjy

Rainbow_sjy

Rainbow_sjy

Rainbow_sjy

Rainbow_sjy

zhoukangyang

zhoukangyang

zhoukangyang

zhoukangyang

zhoukangyang

zhoukangyang

zhoukangyang

zhoukangyang

zhoukangyang

zhoukangyang

zhoukangyang

zhoukangyang

zhoukangyang

zhoukangyang

zhoukangyang

@zhoukangyang

共 4 篇博客