专题题解 - CSP-S 2021
CSP-S 2021
今年的题质量还是可以的，难度方面比去年简单一些。
A. 廊桥分配
难度：$\bigstar$
题目大意：
有 $n$ 个廊桥，$m_1$ 班国内航班的飞机，$m_2$ 班国际航班的飞机，每架飞机有到达时间 $a_i$ 和离开时间 $b_i$。
你可以将 $n$ 座廊桥分别分配给国内航班和国际航班之一，当一架飞机到来时：
- 如果它所属区域（国内/国际）还有空余廊桥，就会停在一个空余的廊桥上；
- 如果它所属区域没有空余廊桥，就无法停在廊桥上。
你需要求出在所有可能的分配方案中，最多有多少架飞机能停在廊桥上。
$1\leq n,m_1+m_2\leq 10^5$
题目解法：
首先考虑证明一个事实：若可用廊桥数为 $k$ 时某架飞机可以停在廊桥，那么当廊桥数 $>k$ 时该飞机也可以停在廊桥。
事实上，现在考虑有无限座廊桥，编号为 $1,2,\ldots$，每当有飞机来时都让它停在编号最小的空闲的廊桥上，设飞机 $i$ 停在了 $f_i$ 廊桥上，那么飞机 $i$ 可以停靠在廊桥上当且仅当实际廊桥数量 $\ge f_i$。
所以我们可以通过使用优先队列模拟无限座廊桥的情况求出 $f_i$，然后通过一个前缀和就可以算出廊桥数为 $k$ 时能停靠的飞机数量，然后枚举所有 $n+1$ 种分配方案取 $\max$ 即可，时间复杂度为 $O(n\log n)$。
B. 括号序列
难度：$\bigstar$
题目大意：
定义“超级括号序列”是由 $\texttt{(,),*}$ 三种字符组成的字符串，只有符合以下条件的超级括号序列是“符合规范“的：
- $\texttt{()}$ 和 $\texttt{(}S\texttt{)}$ 都是符合规范的；
- 如果 $A,B$ 都是符合规范的，那么 $AB$ 或 $ASB$ 都是符合规范的；
- 如果 $A$ 是符合规范的，那么 $\texttt{(}A\texttt{)},\texttt{(}SA\texttt{)},\texttt{(}AS\texttt{)}$ 都是符合规范的。
其中 $S$ 表示任意由不超过 $k$ 个 $\texttt{*}$ 组成的字符串。
给定长度为 $n$ 的包含 $\texttt{(,),*,?}$ 的字符串，求有多少种将 $\texttt{?}$ 替换成任意字符的方式，使得得到的字符串是符合规范的超级括号序列。
$1\leq n\leq 500$
题目解法：
直接区间 DP，令 $f(i,j), g(i,j), h(i,j), p(i,j), q(i,j)$ 分别表示区间 $[i,j]$ 中替换 $\texttt{?}$ 得到形如 $\texttt{(}A’\texttt{)},A,SA,AS,S$ 的方案数，其中 $\texttt{(}A’\texttt{)}$ 表示最外层是一对匹配括号的符合规范超级括号序列，$A,S$ 定义同题面，转移略。
时间复杂度为 $O(n^3)$。
C. 回文
难度：$\bigstar\bigstar$（如果按照大众做法应该是 $\bigstar$，不过这的难度是对我自己而言的）
题目大意：
给定长度为 $2n$ 的包含 $1,\ldots,n$ 各两次的序列 $a_1,\ldots,a_{2n}$，每次操作是从 $a$ 的头部（记为 $\text{L}$）或尾部（记为 $\text{R}$）取出一个元素，放入另一个序列 $b$ 的尾部，请构造一个可能的操作序列使得 $b$ 是回文的，或报告无解，如果有多种可能的序列，输出字典序最小的。
$1\leq n\leq 5\times 10^5$
题目解法：
枚举第一次操作后就确定了最后一个选出来的数，整个序列就被分成两段。
简单做法：每次贪心，看能不能用某一侧的头和某一侧的尾匹配，并优先选择 $\text{L}$。
我考场做法：
发现每个数有两种可能的位置：两次出现属于同一段，或者不属于同一段。
分析可以发现属于同一段的那些数，如果把它对应的区间定义为两次出现之间的部分，那么这些区间必定是一个套一个的。
此时如果有一个不属于同一段的数在这一段中的位置属于某两个区间端点之间的位置，就可以确定出它在最终序列里排在这两个区间对应的数之间。
按照这样的关系建图，利用拓扑排序选点。
时间复杂度为 $O(n)$。
D. 交通规划
难度：$\bigstar\bigstar$
题目大意：
有一个由 $n$ 横 $m$ 纵直线构成的 $n\times m$ 个交点的网格图，网格内部的每条边有边权。
现在在网格边界向外延申的 $2\times (n+m)$ 条射线中，有 $k$ 条上出现了一个有颜色（黑或白）的点，并且给出了这个点到离他最近的网格点之间的边权，现在你需要将整个网格黑白染色，使得相邻不同色点之间的边权和最小，输出这个最小值。
题目解法：
首先考虑 $k=2$ 的情形，这是经典的平面图最小割问题，可以转化为对偶图上的最短路，具体地，如果两个新点一黑一白，那么可以如下建图：
（红色叉表示白色点，黑色叉表示黑色点）我们要求的就是从绿色点到紫色点的最短路，网格中和两个叉上的边权就是题目的输入。
考虑用更多黑白点会怎么样，我们一样可以按照颜色将外周的点分成绿紫两色连续段交替的形式，例如：
也就是把顺时针方向从红转到黑的这一段看成绿色，从黑转到红的这一段看成紫色。
那么答案等于什么呢？实际上就是将绿色连续段和紫色连续段一一匹配，最短路之和的最小值，可以发现将这些最短路上的边都删掉后可以保证红黑点之间都不连通。
注意到如果有交叉的匹配，那么交换一下可以使得最短路之和更小，所以最优方案中将连续段的匹配画成线后是不相交的，那么也就可以看成是括号匹配（只有嵌套和分离，没有相交），进行一个区间 DP 就可以计算了。
注意整个图是一个环，所以需要破环为链，复制两倍。
时间复杂度为 $O(k^3+knm\log nm)$。