[JOISC2020] ビルの飾り付け 4 题解

· · 题解

我写此题解的两个原因：

  1. 题解里都没有给出连续性的证明，这里给出简证，并说一下我自己的想法；

  2. 关于加强问题的一些想法。

题意

给定长度为 2n 的序列 a,b，你需要构造一个序列，使得每一位从 a_i,b_i 中选取，满足 a,b 中都恰选 n 个，满足其单调不降。

### 标准解法 这道题事实上 dp 是第一想法：$f(i,j,0/1)$ 表示到了第 $i$ 位，$a$（$b$ 也行）序列已经选了 $j$ 个，且这一位选了 $a_i/b_i$ 是否可行。那么，根据单调不降的性质就可以从 $f(i-1)$ 转移过来。时间复杂度 $O(n^2)$。 同时，若 $n=10^5$，这道题就做完了：毕竟 dp 数组是 bool 类型的，所以用 bitset 优化转移，时间复杂度 $O(\dfrac{n^2}{\omega})$。 因为这是正式赛题，所以在考场上，这里可以先写一个这样的暴力，再列出 dp 数组找规律。如果真的这么做的话，比较容易能发现，如果固定 $i$，那么 $f=1$ 的 $j$ 全部落在一个区间 $[l,r]$ 内。 所以就不用 $j$ 这一维了——我们直接定义 $g(i,0/1)$ 为两个数 $l,r$，表示 $j$ 满足 $l\le j\le r$ 时 $f(i,j,0/1)=1$。状态数降下来了，转移又是 $O(1)$ 的，这道题就这样做完了。 ### 解法 2 ~~如果在家里口胡，不能打表怎么办？~~ 抽象成一个图论问题来看看。若 $a_{i-1}/b_{i-1}\le a_i/b_i$，则在两点之间连一条边。如果让 $a_i,b_i$ 在同一列（$a_i$ 在上 $b_i$ 在下），那么原题就是找到从最左边到达最右边的一条路，经过了上面恰 $n$ 次，下面也如此。 有一些情况时，可以直接确定 $a_i,b_i$ 究竟选哪个。比如，若 $a_i$ 比 $a_{i-1},b_{i-1}$ 都小，那么一定要选 $b_i$ 否则连不出去；同理，若 $a_i$ 比 $a_{i+1},b_{i+1}$ 都大，那么一定要选 $b_i$。在确定了一些位之后，有可能和它相邻的位也确定了：若 $a_i$ 必须选，且 $a_{i-1}>a_i$，那么只能选 $b_{i-1}$ 了。 这其实是手算的时候的步骤。这也可以用代码来实现：先看能不能在这一位就直接确定选择，若可以就向外拓展，遇到不能拓展或已经拓展完的就停止。这样每个位置最多被扩展一次，复杂度 $O(n)$ 有保证。 好了，那现在没有被确定下来的位基本上是 $a_i,b_i$ 都行了。而且我们会发现，若 $i-1,i$ 位都没确定，不妨 $a_{i-1}\le b_{i-1}$，则一定 $a_{i-1}\le a_i,b_i$，且 $b_{i-1}$ 至少 $\le $ 其中一个。分两种情况： - $b_{i-1}\le a_i,b_i$，此时 $i-1,i$ 位任意选择都可行； - $b_{i-1}\le a_i$ 但 $>b_i$。此时不能同时选择 $b_{i-1},b_i$，其余均可。 所以我们发现，原题变成了若干条如下的限制： - 有若干位已经被确定； - 对相邻不确定的位，不能同时选择两个元素。 这就证明了连续性的结论。不妨考虑 $a$ 能选多少个。我们将第二种限制分成若干段，每段 $a_l,\cdots,a_r$ 相邻两项都不能全选。这样在这个段里面可以选 $[0,(r-l+1)/2]$ 个，是连续的；若干段叠加起来，自然也是连续的。 所以我们分别判断 $a,b$ 至多选择多少个，若全都 $\ge n$ 则可行，否则不行。判断方式也更加简单了：若这一段是区间 $[l,r]$，则答案加上 $(r-l+1)/2$ 下取整。 ### 加强 本题的加强版是：求满足条件的方案数。 变成了求方案数的问题，前面的 dp 做法就无法很简单地优化了。我们考虑解法 2。对已经确定的位，当然就固定了；剩下的就是若干限制。 我们仍考虑段。对长度为 $x$ 的段，要选择 $y$ 个，满足两两不相邻，方案数是 $$C_{x-y+1}^y = \dfrac{(x-y+1)!}{y!\times (x-2y+1)!}$$ 这可以通过递推式或者插板法推出。 回到原题，除去已经确定的位，设 $a$ 一共要选 $m$ 个。若 $a$ 的段长分别为 $x_1,\cdots,x_k$，则方案数等于 $$\sum\limits_{y_1+\cdots+y_k=m} \prod\limits_{i=1}^k C_{x_i-y_i+1}^{y_i}$$ 其中 $y_1,\cdots,y_k$ 是每段选多少个。 显然就拿多项式来干这个东西。$F_{l,r}$ 表示 $x_l,\cdots,x_r$ 区间内的以 $m$ 为变量的多项式，则 $$F_{l,r}=F_{l,mid}\times F_{mid+1,r}$$ 就可以用分治和多项式乘法来解决。时间复杂度 $O(n\log^2n)$。