【2021】 CSP - S 题解
这是一篇迟来的题解，承载着一份未到的喜悦。
伴随着新年将至的钟声，揭开的是旧年里的酸酸甜甜、挫折成长。
在这一年里，
或是幸运，我能够接触到信息学、有了一番不同的梦想；或是不幸，我在自鸣得意时跌入谷底，灾难重重。
T1 廊桥分配 - 困难
算法一
(平衡树) $O(nlog(n))$
这是一道非常有趣的题目，反正当时一眼看去就是个三分，然后样例全过，$fst$ 了不少。
因为国内航班飞机和国际航班飞机 不能停靠在 同一个区。
这就导致了状态 可能性变数过大，从而增加了枚举的难度，
如果是按照朴素方法枚举，复杂度会达到 $O(n^2logn)$，太大了，那该怎么办呢？
由于这道题不满足 凸函数 性质，非严格单调。
所以不能用三分来优化时间复杂度。
在这种情况下，一般的，能想到如果 不能直接找到 要怎么分配，可不可以先预处理，再一一判断。
显然的，如果 分别预处理 两种飞机的停靠，是满足 单调性质 的，那么，就可以做一些其它的考量。
想要快速处理将飞机停靠在 不同数量的廊桥上 所容纳的飞机，就不要去重复处理同一件事。
这一点，可以用 前缀和 解决。
那我们就需要一个能够在 $log n$ 的时间内查找飞机 离开时间 的算法。
这样的算法往往有两种选择 优先队列 或 平衡树。
但是，这不仅仅是要查找 最晚离开时间，还要具有删除功能。
这需要用到 懒惰删除法，这里是直接用 set 解决。
#include <bits/stdc++.h>
#define x first
#define y second
#define For(i, j, k) for (int i = j; i <= k; i ++ )
using namespace std;
const int N = 100010, INF = N;
typedef pair<int, int> PII;
int ans;
int n, m1, m2;
PII a[N];
PII b[N];
set<PII> A, B;
set<PII>::iterator id;
int num1[N], num2[N];
int add(set<PII> &S)
{
int res = 0, now = 0;
For(i,0,INF)
{
id = S.lower_bound({now, now}); // 寻找进入机场的飞机在上一架飞机离开后最早的一个, 返回迭代器
if (id == S.end()) break; // 退出
res ++, now = (*id).y;
S.erase(id);
}
return res;
}
int main()
{
scanf("%d %d %d", &n, &m1, &m2);
For(i, 1, m1) scanf("%d %d", &a[i].x, &a[i].y);
For(i, 1, m2) scanf("%d %d", &b[i].x, &b[i].y);
For(i, 1, m1) A.insert(a[i]);
For(i, 1, m2) B.insert(b[i]);
For(i, 1, n) num1[i] = num1[i - 1] + add(A);
For(i, 1, n) num2[i] = num2[i - 1] + add(B);
For(i, 0, n) ans = max(ans, num1[i] + num2[n - i]);
printf("%d", ans);
return 0;
}
T2 括号序列 - 困难
这应该是我遇到的最难的一道和括号有关的题了。
算法1
(暴力搜索) $O(n3^n)$
遇事不决，先打暴力。
枚举每一个 ? 的三种可能情况，最后判断是否满足要求。
即，相邻的 * 不能超过 $k$ 个，不能出现 (*A*) 、A* 或 *A，后两种只有开头或结尾可能出现。
期望得分：15 分
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define q(t) q.top()
using namespace std;
const int N = 510, mod = 1e9 + 7;
int n, k, ans;
int num[N], t;
int f[N];
char a[N];
int check()
{
stack<int> q;
for (int i = 0, c = 0; i < n; i ++ )
{
if (a[i] == '*')
{
f[i] ++;
if (++ c > k) return 1;
}
else c = 0;
f[i + 1] = f[i];
}
if (a[0] == '*' || a[n - 1] == '*') return 2;
for (int i = 0; i < n; i ++ )
{
if (a[i] == '(') q.push(i);
if (a[i] == ')')
{
if (q.empty()) return 2;
if (a[q(t) + 1] == '*' && a[i - 1] == '*')
{
if (f[i - 1] - f[q(t)] != i - 1 - q(t))
return 2;
}
q.pop();
}
}
return q.size() ? 2 : 0;
}
void dfs(int u)
{
if (u >= t) {
if (!check()) ans ++;
return;
}
a[num[u]] = '(';
dfs(u + 1);
a[num[u]] = ')';
dfs(u + 1);
a[num[u]] = '*';
dfs(u + 1);
}
int main()
{
scanf("%d %d\n%s", &n, &k, a);
for (int i = 0; i < n; i ++ )
if (a[i] == '?')
{
num[t ++ ] = i;
}
if (check() != 1) dfs(0);
printf("%d", ans % mod);
}
算法二
(区间 Dp) $O(n^3)$
题目背景
一个长度为 n 且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。
分析
对于蒟蒻的博主而言，这道题的难度显然是犯规了的，但是，如果你能合理运用题目的条件，倒也能出奇制胜。
既然这道题写不出来，那就先看一下它的 弱化版。
通常对于一个求方案数的题目，只有两种算法可以解决，$DFS$ 和 $Dp$。
这道题数据量很大，那就只有可能是选 $Dp$ 了，那到底可以用哪种 $Dp$ 呢？
状压不行，数据量太大了，背包、树形、数位 似乎也不行。
不过，好像 状态机 跟这个有点关联，毕竟都有 多个状态 嘛，
这时，请注意一下 括号序列 的性质，多个 合法序列 正确组成的序列也是一个 合法序列。
到这里，答案已经呼之欲出了，没错 状态机思想 + 区间Dp。
所遇困境（以下分析都和弱化版无关）
但是不同的形态可能会有不同的转移，如：$(S)$ 这种只能从 $S$ 转移过来等等。所以只开两维的 $f$ 数组必然是不够的。
更何况 ? 似乎也没有办法处理？（事实上，只能先将它看成 万能牌 ，不再单独考虑。）
思考一下，既然这道题的状态太多了，那为何不能多开一维，用 状态机 的方式，将不同连边的状态 转换。
那我们还剩两个任务，设计状态、状态转移。
设计状态
我们可以发现，对于一个超级括号序列，一定可以表示成以下 七种形式：
$()$ 、$(S)$ 、$(AS)$ 、$(SA)$ 、$(A)$ 、$AB$ 、$ASB$。
而这 七种形式 又可以分成两类：
包在括号内的：$()$ 、$(S)$ 、$(AS)$ 、$(SA)$ 、$(A)$
首尾有两个括号序列的：$AB$ 、$ASB$
我们先尝试多开两位，用 $f[i][j][0]$ 和 $f[i][j][1]$ 分别表示上面这两类情况。
根据题意，$(S)$ 、$(AS)$ 、$(SA)$ 、$(A)$ 都是超级序列，所以我们要用 $S$ 、 $AS$ 、$SA$ 、$A$ 来对第一种情况的超级序列进行转移。
其中 $A$ 满足第一类的要求，但是 $S$ 、$AS$ 、$SA$ 显然都不符合，
因为它们代表三种不同的情况，所以需要再设计三种不同的状态来表示。
所有状态如下：
-
$f_{i,j,0}$ : 形态如
(...)的括号序列（即左右直接被括号包裹且最左边括号与最右边的括号相互匹配）。 -
$f_{i,j,1}$ : 形态如
(...)***(...)*(...)的括号序列（即左边以括号序列开头，右边以括号序列结尾）。 -
$f_{i,j,2}$ : 形态如
***...*的括号序列（即全部是*，记得判断一下两端距离是否不大于 $k$）。 -
$f_{i,j,3}$ : 形态如
(...)**(...)***的括号序列（即左边以括号序列开头，右边以*结尾）。 -
$f_{i,j,4}$ : 形态如
***(...)**(...)的括号序列（即左边以*开头，右边以括号序列结尾）。
状态转移
请见代码（感觉会清晰一点）
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 510, mod = 1e9 + 7;
int n, k;
int f[N][N][5];
char s[N];
bool check(int l, int r)
{
return (s[l] == '(' || s[l] == '?') && (s[r] == ')' || s[r] == '?');
}
signed main()
{
scanf("%lld %lld %s", &n, &k, s + 1); // s 下标从 1 开始
for (int i = 1; i <= n; i ++ ) f[i][i - 1][2] = 1;
for (int len = 1; len <= n; len ++ )
for (int l = 1, r; (r = l + len - 1) <= n; l ++ )
{
f[l][r][2] = f[l][r - 1][2] & (s[r] == '*' || s[r] == '?') & (len <= k);
// 需满足仅由*构成且不超过k个, 因为*都是一样的, 所以值只存在1和0两种可能
if (len == 1) continue; // 当len等于1时, 除f[l][r][2]以外的都只能为0
f[l][r][0] = check(l, r) * (f[l + 1][r - 1][0] + f[l + 1][r - 1][1] + f[l + 1][r - 1][2] + f[l + 1][r - 1][3] + f[l + 1][r - 1][4]) % mod;
// 如果s[l]和s[r]可以组成一个括号的话
for (int k = l; k < r; k ++ ) // 分成[l, k]和[k + 1, r]
{
// AS -> ASB / A + S
f[l][r][3] = (f[l][r][3] + (f[l][k][0] + f[l][k][1]) * f[k + 1][r][2]) % mod;
// f[l][k][0] 和 f[l][k][1] 之间，只有一个是有效的。
// 由乘法原理可知, AS 方案数 = A 方案数 * S 方案数, 总方案数需要累计
// SA -> S + ASB / A
f[l][r][4] = (f[l][r][4] + (f[k + 1][r][0] + f[k + 1][r][1]) * f[l][k][2]) % mod;
// f[k + 1][r][0] 和 f[k + 1][r][1] 之间，只有一个是有效的。
// 由乘法原理可知, SA 方案数 = A 方案数 * S 方案数, 总方案数需要累计
// AB/ASB -> ASB / A / AS + A
f[l][r][1] = (f[l][r][1] + (f[l][k][0] + f[l][k][1] + f[l][k][3]) * f[k + 1][r][0]) % mod;
// 由乘法原理可知, AB 方案数 = A 方案数 * B 方案数, 总方案数需要累计
// 由乘法原理可知, ASB 方案数 = AS 方案数 * B 方案数, 总方案数需要累计
}
}
printf("%lld", (f[1][n][0] + f[1][n][1]) % mod); // 任选一个
}
T3 回文 - 困难
算法一
(贪心) $O(n)$
本题的数据偏大，只能用 $O(n)$ 或 $O(nlogn)$ 的算法。
同时，本题要求最小字典序，这提醒了我们往贪心这一方面想。
因为答案要的是 回文串，可见对于任意一个字符，若它 第一个 取出，则另一个值相等的字符要 最后取。
根据要 最后取 的字符做 分割线，将这一串数字被分成了两部分($A$ 和 $B$)，靠左的只能往左取、靠右的往右。
最后就是顺序问题了，因为最终要形成 回文串，这启发我们定义两个指针，从两端往中间搜。
贪心
若 $A$ 队头 等于 $A$ 队尾，因为 $A$ 队队尾后没有 $A$ 队元素，不会产生影响，所以 可以取出。
若 $B$ 队头 等于 $B$ 队尾，因为 $B$ 队队尾后没有 $B$ 队元素，不会产生影响，所以 可以取出。
若 $A$ 队头 等于 $A$ 队中的元素，因为 $A$ 队中此元素为 局部最晚弹出，其后元素只能往右弹，但右边有分割线，无法也最好不这么弹，所以 不能取出。
若 $B$ 队头 等于 $B$ 队中的元素，因为 $B$ 队中此元素为 局部最晚弹出，其后元素只能往左弹，但左边有分割线，无法弹出，所以 不能取出。
若 $A$ 队头 等于 $B$ 队尾，因为 $B$ 队队尾后没有 $B$ 队元素，不会产生影响，所以 可以取出。
若 $B$ 队头 等于 $A$ 队尾，因为 $A$ 队队尾后没有 $A$ 队元素，不会产生影响，所以 可以取出。
若 $A$ 队头 等于 $B$ 队中的元素，因为 $B$ 队中此元素为 局部最晚弹出，其后元素只能往左弹，但左边有分割线，无法弹出，所以 不能取出。
若 $B$ 队头 等于 $A$ 队中的元素，因为 $A$ 队中此元素为 局部最晚弹出，其后元素只能往右弹，但右边有分割线，无法也最好不这么弹，所以 不能取出。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int T, n;
int a[N], b[N];
int Al, Ar, Bl, Br;
char ans[N];
bool F1, F2;
deque<int> A, B;
void print()
{
for (int i = 1; i <= 2 * n; i ++ ) printf("%c", ans[i]);
puts("");
}
int find(int x)
{
for (int i = 2; i <= 2 * n; i ++ )
if (a[i] == x)
{
return i;
}
}
void build(bool op, int S, int E)
{
A.clear(), B.clear();
if(!op) Al = 1, Ar = E, Bl = E + 1, Br = 2 * n;
if (op) Al = 1, Ar = S, Bl = S + 1, Br = 2 * n;
for (int i = Al; i <= Ar; i ++ ) A.push_back(a[i]);
for (int i = Bl; i <= Br; i ++ ) B.push_back(a[i]);
}
bool work()
{
int L = 1, R = n * 2;
while (A.size() || B.size())
{
// 两个元素都在 A 栈里, 其中一个在队首, 出栈操作为 'L'
// 另一个元素会是此栈中最晚出栈的, 因为A栈原队尾是全局最晚出栈的
// 所以最好也只能选 'L'
if (A.size() >= 2 && A.front() == A.back())
{
A.pop_front(), A.pop_back();
ans[L] = 'L', ans[R] = 'L';
L ++, R --;
}
else if (A.size() && B.size() && A.front() == B.front())
{
A.pop_front(), B.pop_front();
ans[L] = 'L', ans[R] = 'R';
L ++, R --;
}
// 两个元素都在 B 栈里, 其中一个在 B 栈队尾, 出栈操作为 'R'
// 另一个元素会是当前栈中最晚出栈的, 因为A栈原队尾是全局最晚出栈的
// 所以只能选 'R'
else if (B.size() >= 2 && B.front() == B.back())
{
B.pop_front(), B.pop_back();
ans[L] = 'R', ans[R] = 'R';
L ++, R --;
}
else if (A.size() && B.size() && A.back() == B.back())
{
A.pop_back(), B.pop_back();
ans[L] = 'R', ans[R] = 'L';
L ++, R --;
}
else return false;
}
print();
return true;
}
int main()
{
scanf("%d", &T);
while (T -- )
{
scanf("%d", &n);
for (int i = 1; i <= 2 * n; i ++ ) scanf("%d", &a[i]);
F1 = false, F2 = false;
int Ls = 1;
int Le = find(a[Ls]);
strcpy(ans, "");
build(0, Ls, Le);
if (work()) continue;
int Re = 2 * n;
int Rs = find(a[Re]);
strcpy(ans, "");
build(1, Rs, Re);
if (work()) continue;
puts("-1");
}
return 0;
}
T4 交通规划 - 困难
前言
考场上想到了 $45$ 分暴力的写法，但码力太蒻了，最后没有调出来。
题面简述
给定一个网络和 $T$ 次询问，每次询问给出 $k$ 个附加点的相邻点，
附加点都在 网格边缘以外，并和边缘的一个节点相连，给出其 边权 和附加点的 颜色。
求线段上 端点异色的边 的边权之和。
k <= 2 的解法
(对偶最短路) $O(n)$
对于 $k < 2$，只有一个附加点，故连通块颜色相同，则答案为 $0$
对于 $k = 2$ 若两附加点颜色一致，连通块颜色相同，则答案为 $0$.
否则，这个图上会有 一黑一白两连通块。
下图对应本题的样例（借一张图）
红线经过的边权为 $3 + 4 + 5 = 12$。
现在，我们的问题转化成了：在这张图上找一条线，使得这条线把这张图分为两块，并且 线上的边权之和 最小
这是一张 偶图，即把 格子看作 点，然后把 格子之间隔着的边 变为 连接两个格子的点的边
由图可见，起点 和 终点 分别位于两个 附加点 连成的长方形的 两侧，
这是因为一条 分割线 一定经过 两个附加点的不同侧，否则无法把它们两个分开，所以两个点必须在不同侧。
最后，用 $Dijkstra$ 算法求 起点 到 终点 的最短路即可
期望得分：45 分
算法二
(对偶最短路 + 区间 Dp) $O(\sum (k_i)\cdot mn\log(mn)+\sum (k_i^3))$
以下内容有亿点点复杂，水平不足者请就此打住，您已经拥有 $345$ 的高分了。
迈出勇敢的一步 k = 3
让我们改一下样例（没错，又是蹭图
可见，在 $(1, 1)$ 位置的点 往左延伸 出一个附加点。
因为点被染上的颜色只有 黑白两种，所以必然可以找到两个同色点，
那么我们可以把这两个点当成 同一个点 进行处理：
这样，我们就知道了 起点 和 终点 的位置！
虚线连接的是除了 起点和终点 以外的所有 同侧边上的点。
问题解决。
问题扩展 k > 2
通过上面的 $k = 3$ 的情况，我们发现我们可以将所有 相邻的同色附加点 合并，将它们 看为一个点
如果有好多点，又该如何处理呢？
上图中，黑色的是原图，红色的是我们转化后的 对偶图。
我们现在要做的，就是把图上的 异色 附加点 两两配对 为 起点和终点，让所有点都有自己的 伴点。
最后，将 可以两两配对的异色点 的 最短路径上的 所有边的权值之和相加即可。
那么，我们该如何配对这些点呢？
如果是直接直接枚举 所有配对方案，那么时间复杂度会飙升到 $O(k!)$，无法接受！
我们需要找到一些性质，来降低枚举的方案数量，也就是 可行性剪枝。
思考一下，异色的附加点 两两配对 后 最短距离和最小 需要满足什么样的性质？
有 $A, B, C, D$ 四个可配对的点，顺时针摆放后 若按 $(A, C)、(B, D)$ 顺序配对，会造成如下情况：
因为它们是交叉着配对的，其最短路必定在一个位置相交，棕色的点就是其相交处。
如此，我们会惊讶的发现，要是将 $(1, 2)、(3, 4)$ 进行配对呢？
如图可见，最终答案显然要优于上一种。
由此，我们总结出了一个规律：配对的点 组成的最短路 不能交叉!
哎，这个规律好熟悉呀，不就是括号序列嘛！
举个例子：若 $A$ 为合法的括号序列，则 $AA、(A)$ 都合法。
那我们要枚举的 配对方案 和 括号序列的方案 一一对应。
于是，我们求出求出 任意两个 起点、终点之间的最短路。
最后用区间 $Dp$ 求出 配对方案中 最小权值之和。
因为这个序列构成一个环形，所以，我们需要 断链加一倍 来实现。
至此，我们实现了所有的操作：
一、 建出 转化后的图
二、 求出 任意两个 起点、终点之间的最短路
三、 用 括号序列 的区间 $DP$ 操作求出 最小值
# $Orz$
大神，第四题没有代码？
TQL！！！！大神贴贴
$good$