资讯 / 正文
2021年CSP-S第二轮(提高级)真题及答案
第一题 廊桥分配(airport)
【题目描述】
飞机抵达机场后可以停靠廊桥,也可以停靠远机位。机场分为国内区和国际区,国内航班只能停国内区的廊桥,国际航班只能停国际区的廊桥。L 市新建的机场共有 n 个廊桥,使用遵循"先到先得":飞机抵达后,若对应区域还有空闲廊桥就停靠(约定分配编号最小的空闲廊桥),否则停靠远机位(远机位数量充足)。机场只有一条跑道,不存在两架飞机同时抵达。现给定一段时间内所有飞机的抵达、离开时刻,请把 n 个廊桥分配给国内区和国际区,使停靠廊桥的飞机数量最多,输出这个最大值。
【输入格式】第一行三个正整数 n, m1, m2,表示廊桥数、国内航班数、国际航班数。接下来 m1 行每行两个正整数,表示一架国内航班的抵达、离开时刻;随后 m2 行同样描述国际航班。
【输出格式】一个正整数,表示能停靠廊桥的飞机数量的最大值。
【样例输入 1】
3 5 4
1 5
3 8
6 10
9 14
13 18
2 11
4 15
7 17
12 16
【样例输出 1】
7
【样例输入 2】
2 4 6
20 30
40 50
21 22
41 42
1 19
2 18
3 4
5 6
7 8
9 10
【样例输出 2】
4
【数据范围】20%:n≤100,m1+m2≤100;40%:n≤5000,m1+m2≤5000;100%:1≤n≤105,1≤m1+m2≤105,所有时刻为不超过 108 的互不相同的正整数,且抵达时刻小于离开时刻。
【样例解释 1】国内区分 2 座廊桥、国际区分 1 座时,共有 7 架飞机停靠廊桥。样例 2 中把全部 2 座廊桥都给国内区最优,4 架国内航班全部停靠。注意"先到先得"是固定规则:若国际区只有 1 座廊桥,会被 (1,19) 长期占用,(3,4)(5,6)(7,8)(9,10) 四架短航班反而一架都停不进去。
【思路提示】本题的关键观察是:在"先到先得 + 取编号最小空闲廊桥"的固定规则下,每架飞机停在几号廊桥只与廊桥数量有关,与具体怎么划分无关。于是先假设廊桥无限,对两组航班各跑一遍模拟(离开时刻小根堆 + 空闲编号小根堆),记录每座廊桥停靠的航班数 cnt[id];此时"只给 k 座廊桥"的停靠数恰好等于 cnt 的前 k 项和——因为编号大的廊桥被用到,当且仅当前面编号小的廊桥全部占满,限制只能用前 k 座与只分配 k 座完全等价。这样两组航班各做一次前缀和,就同时得到了 f(i)=国内 i 座、g(j)=国际 j 座的所有答案,最后枚举 i=0..n 取 max{f(i)+g(n-i)}。总复杂度 O((m1+m2)log(m1+m2)+n),轻松通过 105 规模。
【参考代码(满分)】
#include <bits/stdc++.h>
using namespace std;
// 对一组航班做"无限廊桥"贪心模拟
// 返回 pre[k]: 只使用前 k 座廊桥时能停靠的航班数
vector<long long> calc(vector<pair<int,int> > v) {
int m = (int)v.size();
sort(v.begin(), v.end()); // 按抵达时刻排序
vector<long long> cnt(m + 2, 0); // cnt[id]: 编号 id 的廊桥共停了几架
priority_queue<pair<int,int>, vector<pair<int,int> >,
greater<pair<int,int> > > occ; // (离开时刻, 廊桥编号) 小根堆
priority_queue<int, vector<int>, greater<int> > freeq; // 空闲廊桥编号小根堆
int nid = 1;
for (int i = 0; i < m; i++) {
int a = v[i].first, b = v[i].second;
while (!occ.empty() && occ.top().first < a) { // 已离开的廊桥回收
freeq.push(occ.top().second); occ.pop();
}
if (freeq.empty()) freeq.push(nid++); // 假设廊桥无限, 不够就新开一座
int id = freeq.top(); freeq.pop(); // 先到先得, 取最小编号空闲廊桥
occ.push(make_pair(b, id));
cnt[id]++;
}
vector<long long> pre(m + 1, 0); // 前缀和: pre[k] = cnt[1..k] 之和
for (int k = 1; k <= m; k++) pre[k] = pre[k - 1] + cnt[k];
return pre;
}
int main() {
int n, m1, m2;
scanf("%d%d%d", &n, &m1, &m2);
vector<pair<int,int> > v1(m1), v2(m2);
for (int i = 0; i < m1; i++) scanf("%d%d", &v1[i].first, &v1[i].second);
for (int i = 0; i < m2; i++) scanf("%d%d", &v2[i].first, &v2[i].second);
vector<long long> f1 = calc(v1), f2 = calc(v2);
long long ans = 0;
for (int i = 0; i <= n; i++) { // 国内 i 座, 国际 n-i 座
int j = n - i;
long long x = (i < (int)f1.size()) ? f1[i] : f1.back();
long long y = (j < (int)f2.size()) ? f2[j] : f2.back();
ans = max(ans, x + y);
}
printf("%lld\n", ans);
return 0;
}
第二题 括号序列(bracket)
【题目描述】
定义"超级括号序列"为仅由 (、)、* 组成的字符串。给定常数 k,合法的超级括号序列定义如下:
1. () 和 (S) 合法,其中 S 是不超过 k 个字符 * 组成的非空串(下两条规则中的 S 含义相同);2. 若 A、B 都是合法的超级括号序列,则 AB 和 ASB 也合法;3. 若 A 是合法的超级括号序列,则 (A)、(SA)、(AS) 也合法;4. 所有合法序列都由以上 3 条规则得到。
特别地,空串不是合法的超级括号序列。例如 k=3 时,((**()*(*))*)(***) 合法,而 *()、(*()*)、((**))*)、(****(*)) 不合法。现在给出一个长度为 n、由 (、)、*、? 组成的串,其中 ? 表示未确定。求把所有 ? 填成三种字符后,得到的串是合法超级括号序列的方案数(即不同的填法个数),对 109+7 取模。
【输入格式】第一行两个正整数 n, k;第二行一个长度为 n 的字符串 S,仅含 (、)、*、?。
【输出格式】一个非负整数,表示方案数对 109+7 取模的结果。
【样例输入 1】
7 3
(*??*??
【样例输出 1】
5
【样例解释 1】5 种合法填法:(**)*()、(**(*))、(*(**))、(*)**()、(*)(**)。
【样例输入 2】
10 2
???(*??(?)
【样例输出 2】
19
【数据范围】对 100% 的数据,1≤k≤n≤500。测试点 1~3:n≤15;4~8:n≤40;9~13:n≤100;14~15:n≤500 且串中只含 ?;16~20:n≤500。
【思路提示】经典区间 DP,难点全在计数不重不漏。若直接设"区间是否合法"并枚举拼接点,像 ()()() 这样的串会被 ()+()() 与 ()()+() 算两次。正确做法是给区间按"开头/结尾是括号还是星号"细分状态:设 f[l][r][0..5] 分别表示纯星号段(≤k)、(S) 型、括号开头星号结尾、括号开头括号结尾、星号开头括号结尾、星号开头星号结尾(中间含括号)。核心转移:状态 3(答案状态)由 (状态2或3)×状态1 推出——即"一段以括号结尾的前缀"接上一个新括号单元;状态 2 由 状态3×状态0 推出(尾部补星号段);状态 4、5 关于星号开头对称。括号内部只允许 状态0/2/3/4——因为规则只允许 (A)、(SA)、(AS),不允许 (SAS);而 (S) 型包含于状态 3,避免重复。转移中"尾部星号段"永远用状态 0 整体承担,保证星号段 ≤k 且每种填法只被统计一次。复杂度 O(6n3),n≤500 轻松通过。
【参考代码(满分)】
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int n, k;
char s[505];
// 0: 纯'*'段(长度<=k) 1: (S)型
// 2: 括号开头、'*'结尾 3: 括号开头、括号结尾(答案状态)
// 4: '*'开头、括号结尾 5: '*'..括号..'*' (包含状态0)
long long f[505][505][6];
bool match(int l, int r) { // s[l..r] 两端能否配一对括号
return (s[l] == '(' || s[l] == '?') && (s[r] == ')' || s[r] == '?');
}
bool starable(int l, int r) { // s[l..r] 能否全填成 '*' 且长度<=k
if (r - l + 1 > k) return false;
for (int i = l; i <= r; i++)
if (s[i] != '*' && s[i] != '?') return false;
return true;
}
int main() {
scanf("%d%d%s", &n, &k, s + 1);
for (int i = 2; i <= n + 1; i++) f[i][i - 1][0] = 1; // 空区间当"空星号段"
for (int len = 1; len <= n; len++)
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
long long v[6] = {0, 0, 0, 0, 0, 0};
if (starable(l, r)) v[0] = 1;
if (len >= 2 && match(l, r)) { // (S): 内部为空/纯星号/合法/一侧带星
long long *g = f[l + 1][r - 1];
v[1] = (g[0] + g[2] + g[3] + g[4]) % MOD;
}
v[5] = v[0];
for (int i = l; i < r; i++) // 5 = 4 + 尾部星号段
v[5] = (v[5] + f[l][i][4] * f[i + 1][r][0]) % MOD;
for (int i = l; i < r; i++) // 4 = (4或5) + 括号单元
v[4] = (v[4] + (f[l][i][4] + f[l][i][5]) * f[i + 1][r][1]) % MOD;
for (int i = l; i < r; i++) // 2 = 括号序列 + 尾部星号段
v[2] = (v[2] + f[l][i][3] * f[i + 1][r][0]) % MOD;
v[3] = v[1]; // 3 包含 (S) 型
for (int i = l; i < r; i++) // 3 = (2或3) + 括号单元
v[3] = (v[3] + (f[l][i][2] + f[l][i][3]) * f[i + 1][r][1]) % MOD;
for (int t = 0; t < 6; t++) f[l][r][t] = v[t];
}
printf("%lld\n", f[1][n][3]);
return 0;
}
第三题 回文(palin)
【题目描述】
给定正整数 n 和整数序列 a1, a2, …, a2n,其中 1..n 每个数恰好出现两次。现在要进行 2n 次操作,目标是构造一个同样长度的序列 b1,…,b2n,初始 b 为空。每次操作二选一:
1. 取出 a 的第一个元素,接到 b 的末尾;2. 取出 a 的最后一个元素,接到 b 的末尾。
目标是使 b 成为回文序列。请判断是否可行;若可行,输出操作方案中字典序最小的一个:输出长度 2n 的字符串,第 i 个字符为 L(操作 1)或 R(操作 2)。无解输出 -1。多组数据。
【输入格式】第一行一个整数 T,表示数据组数。每组数据第一行一个正整数 n;第二行 2n 个空格隔开的整数 a1,…,a2n。
【输出格式】每组数据输出一行:无解输出 -1,否则输出字典序最小的操作串。
【样例输入】
2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3
【样例输出】
LRRLLRRRRL
-1
【样例解释】第一组得到的 b = [4,5,3,1,2,2,1,3,5,4],是回文;方案 LRRLLRRRRR 也可行但字典序更大。第二组无论怎么操作都无法得到回文。
【数据范围】1≤T≤100,1≤n,∑n≤5×105,每个数恰好出现两次。保证答案存在时操作串唯一确定。
【思路提示】回文是从外向内逐层配对的:b[1]=b[2n],b[2]=b[2n-1]……于是第一步取了某个数 x,它的另一个副本必须最后被取。枚举第一步取 L 还是 R(优先 L):设副本位置为 s2,它把剩余元素分成左右两段,各相当于一个双端队列(左段怎么取都是 L,右段怎么取都是 R)。之后每一层需要在"当前可取的四个端点"(左段两端、右段两端)中找到两个相等的数,合法配对只有四种:LL(左段两端相等)、LR(左段外端=右段内端)、RL(左段内端=右段外端)、RR(右段两端相等);"两个外端"或"两个内端"的组合都会破坏结构。为了字典序最小,每层按 LL → LR → RL → RR 的顺序贪心尝试,第一步 L 失败再试 R,都不行输出 -1。两个易错点:①某段只剩一个元素时不能和自己配对,同段配对条件必须用严格小于;②最后一步只剩副本一个元素,取 L 或 R 都合法,字典序取 L。整个算法 O(n)。
【参考代码(满分)】
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int T, n, a[MAXN], p1[MAXN], p2[MAXN]; // p1/p2: 每个值的两个出现位置
char ans[2 * MAXN];
bool tryFirst(bool firstL) { // 枚举第一步取 L / R
int s1 = firstL ? 1 : 2 * n; // 第一步取的位置
int val = a[s1];
int s2 = (p1[val] == s1) ? p2[val] : p1[val]; // 它的副本, 最后一步取
int l1, r1, l2, r2; // 副本把剩余元素分成两段双端队列
if (firstL) { l1 = 2; r1 = s2 - 1; l2 = s2 + 1; r2 = 2 * n; }
else { l1 = 1; r1 = s2 - 1; l2 = s2 + 1; r2 = 2 * n - 1; }
ans[1] = firstL ? 'L' : 'R';
ans[2 * n] = 'L'; // 最后一步只剩一个元素, 取 L 字典序最小
for (int step = 2; step <= n; step++) {
int bk = 2 * n + 1 - step;
if (l1 < r1 && a[l1] == a[r1]) { // 条件1: 左段两端相等 LL
ans[step] = 'L'; ans[bk] = 'L'; l1++; r1--; continue;
}
if (l1 <= r1 && l2 <= r2 && a[l1] == a[l2]) { // 条件2: 左外=右内 LR
ans[step] = 'L'; ans[bk] = 'R'; l1++; l2++; continue;
}
if (l1 <= r1 && l2 <= r2 && a[r1] == a[r2]) { // 条件3: 左内=右外 RL
ans[step] = 'R'; ans[bk] = 'L'; r1--; r2--; continue;
}
if (l2 < r2 && a[l2] == a[r2]) { // 条件4: 右段两端相等 RR
ans[step] = 'R'; ans[bk] = 'R'; l2++; r2--; continue;
}
return false; // 四种条件都不满足, 无解
}
return true;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= 2 * n; i++) {
scanf("%d", &a[i]);
if (p1[a[i]] == 0) p1[a[i]] = i; else p2[a[i]] = i;
}
if (tryFirst(true) || tryFirst(false)) {
ans[2 * n + 1] = 0;
printf("%s\n", ans + 1);
} else {
printf("-1\n");
}
for (int i = 1; i <= 2 * n; i++) p1[a[i]] = p2[a[i]] = 0;
}
return 0;
}
第四题 交通规划(traffic)
【题目描述】
平面上有 n 条水平直线和 m 条竖直直线,相交成 n 行 m 列的网格,第 r 行第 c 列的交点称为格点 (r,c)。相邻两格点之间的水平/竖直线段称为边,每条边有非负整数边权。另有若干条从网格边界向外发出的射线:从上边界的最左端开始到最右端、再到下边界最右端到最左端、左边界的最下端到最上端,依次编号为 1..2(n+m)。共有 T 组询问。每组询问给出 k 个附加点,它们分别位于 k 条互不相同的射线上;每个附加点与其最近的格点之间的连线也称为一条边,有非负整数边权。给出每个附加点的颜色(0 白 / 1 黑),要求给网格内每个格点染黑或白,使得所有两端异色的边的边权之和最小,输出这个最小值。
【输入格式】第一行三个正整数 n, m, T。接下来 n-1 行每行 m 个非负整数,第 i 行第 j 个 x1 表示 (i,j) 与 (i+1,j) 之间边的权值;接下来 n 行每行 m-1 个非负整数,x2 表示 (i,j) 与 (i,j+1) 之间边的权值。随后 T 组询问:每组第一行正整数 k;接下来 k 行每行三个非负整数 x3, p, t,表示该附加点连边的权值、所在射线编号与颜色。
【输出格式】输出 T 行,第 i 行表示第 i 组询问的最小边权和。
【样例输入】
2 3 1
9 4 7
3 8
10 5
2
19 3 1
17 9 0
【样例输出】
12
【样例解释】一组最优方案:(1,3)、(1,2)、(2,3) 染黑;(1,1)、(2,1)、(2,2) 染白。异色边为 (1,1)-(1,2) 权 3、(1,2)-(2,2) 权 4、(2,2)-(2,3) 权 5,总和 12;两条附加点连边两端同色,不产生代价。
【数据范围】2≤n,m≤500,1≤T≤50,1≤k≤min{2(n+m),50},同一询问中射线编号互不相同,∑k≤50,0≤x≤106。另有部分分满足 k≤2。
【思路提示】本场压轴题,本质是平面图最小割转对偶图最短路。先想 k≤2:把 n 条横线、m 条竖线看成完整直线,平面被分成 (n+1)×(m+1) 个区域,每个区域是对偶图的一个结点;原图每条边(网格边、附加点连边)在对偶图中产生一条连接两侧区域、权值相同的边,附加点所在射线把外圈 2(n+m) 个无穷大区域串成一环。此时答案就是两个外圈区域之间的最短路。k>2 时:沿外圈扫描附加点,相邻异色附加点之间的外圈区域切成一块,块恰好交替地分成两类;最优方案一定是把两类块不交叉地两两配对,每对的代价 = 两块之间的对偶图最短路(曲线可以证明不交叉时不劣),最后用类似三角剖分的环形区间 DP 合并:f[i][j] = min{ g[i][k] + f[i+1][k-1] + f[k+1][j] }(k 与 i 奇偶性不同)。每个块跑一次 Dijkstra 求块间两两距离,总复杂度 O(∑k·nm·log(nm)+∑k³)。两个实现细节:①同色相邻附加点之间的外圈区域也要建点连边,因为最短路可能贴着边界从那里绕过;②没有附加点的射线相当于权值为 0 的对偶边,可以自由穿过。
【参考代码(满分)】
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 260005;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
struct Edge { int v, w, next; } e[N * 10];
int h[N], hbak[N], eid;
void addEdge(int u, int v, int w) { e[eid] = (Edge){v, w, h[u]}; h[u] = eid++; }
int n, m, Q;
int a[2005], c[2005]; // a[p]: 射线 p 上附加点的边权; c[p]: 颜色
vector<int> zoo; // 外圈无穷大区域按顺时针排一圈(存两遍)
int b[N], tot; // b[u]: 外圈区域 u 属于哪一块(0=不属于)
vector<int> pig[105]; // 每一块包含的外圈区域
LL d[N], g[105][105], f[105][105];
bool vis[N];
struct Node { int u; LL d; bool operator<(const Node &r) const { return d > r.d; } };
void dijk(int s) { // 从第 s 块的所有区域同时出发
for (int i = 0; i < N; i++) d[i] = INF, vis[i] = false;
priority_queue<Node> q;
for (int x : pig[s]) { d[x] = 0; q.push((Node){x, 0}); }
int cnt = 0;
while (!q.empty() && cnt < tot) {
int u = q.top().u; q.pop();
if (vis[u]) continue;
vis[u] = true;
if (b[u] > 0 && g[s][b[u]] == -1) g[s][b[u]] = d[u], cnt++;
for (int i = h[u]; ~i; i = e[i].next) {
int v = e[i].v, w = e[i].w;
if (d[v] > d[u] + w) { d[v] = d[u] + w; q.push((Node){v, d[v]}); }
}
}
}
int id(int x, int y) { return x * (m + 1) + y; }
int id2(int p) { // 射线编号 -> 顺时针下一块外圈区域
if (p <= m) return id(0, p);
else if (p <= m + n) { p -= m; return id(p, m); }
else if (p <= m + n + m) { p -= m + n; p = m - p + 1; return id(n, p - 1); }
else { p -= m + n + m; p = n - p + 1; return id(p - 1, 0); }
}
int main() {
memset(h, -1, sizeof h);
scanf("%d%d%d", &n, &m, &Q);
for (int i = 1; i < n; i++) // 竖直边: 把相邻两个区域连起来(对偶边)
for (int j = 1; j <= m; j++) {
int u = id(i, j - 1), v = id(i, j), w;
scanf("%d", &w);
addEdge(u, v, w); addEdge(v, u, w);
}
for (int i = 1; i <= n; i++) // 水平边
for (int j = 1; j < m; j++) {
int u = id(i - 1, j), v = id(i, j), w;
scanf("%d", &w);
addEdge(u, v, w); addEdge(v, u, w);
}
for (int t = 0; t < 2; t++) { // 外圈区域顺时针环, 存两遍方便环形截取
for (int i = 0; i <= m; i++) zoo.push_back(id(0, i));
for (int i = 1; i <= n - 1; i++) zoo.push_back(id(i, m));
for (int i = m; i >= 0; i--) zoo.push_back(id(n, i));
for (int i = n - 1; i >= 1; i--) zoo.push_back(id(i, 0));
}
memcpy(hbak, h, sizeof h);
while (Q--) {
memcpy(h, hbak, sizeof h); // 还原成不含射线边的对偶图
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
memset(c, -1, sizeof c);
memset(g, -1, sizeof g);
for (int i = 1; i <= tot; i++) pig[i].clear();
tot = 0;
int k, flag = 0;
scanf("%d", &k);
for (int i = 0; i < k; i++) {
int x, p, t;
scanf("%d%d%d", &x, &p, &t);
a[p] = x; c[p] = t;
flag |= 1 << t;
}
if (flag != 3) { puts("0"); continue; } // 附加点全部同色, 代价 0
for (int i = 1; i <= m; i++) // 上边射线 (左->右)
{ int u = id(0, i - 1), v = id(0, i); addEdge(u, v, a[i]); addEdge(v, u, a[i]); }
for (int i = 1; i <= n; i++) // 右边射线 (上->下)
{ int u = id(i - 1, m), v = id(i, m); addEdge(u, v, a[i + m]); addEdge(v, u, a[i + m]); }
for (int i = 1; i <= m; i++) // 下边射线 (右->左)
{ int u = id(n, m - i + 1), v = id(n, m - i); addEdge(u, v, a[i + m + n]); addEdge(v, u, a[i + m + n]); }
for (int i = 1; i <= n; i++) // 左边射线 (下->上)
{ int u = id(n - i + 1, 0), v = id(n - i, 0); addEdge(u, v, a[i + m + n + m]); addEdge(v, u, a[i + m + n + m]); }
for (int i = 1; i <= 2 * n + 2 * m; i++) { // 相邻附加点异色处切出一块
if (c[i] == -1) continue;
for (int j = i + 1;; j++) { // 找顺时针下一个有附加点的射线
if (j > 2 * n + 2 * m) j = 1;
if (c[j] == -1) continue;
if (c[j] != c[i]) {
tot++;
int x = id2(i), y = id2(j);
bool st = false;
for (int u : zoo) { // 两射线之间的外圈区域记入该块
if (u == x) st = true;
if (st) {
if (u == y) break;
b[u] = tot;
pig[tot].push_back(u);
}
}
}
break;
}
}
for (int i = 1; i <= tot; i++) dijk(i); // 块两两之间的对偶图最短路
memset(f, 0x3f, sizeof f);
for (int len = 2; len <= tot; len += 2) // 不交叉配对的环形区间 DP
for (int i = 1, j = i + len - 1; j <= tot; i++, j++)
for (int k2 = i + 1; k2 <= j; k2 += 2) {
LL L = (k2 - 1 >= i + 1) ? f[i + 1][k2 - 1] : 0;
LL R = (k2 + 1 <= j) ? f[k2 + 1][j] : 0;
f[i][j] = min(f[i][j], g[i][k2] + L + R);
}
printf("%lld\n", f[1][tot]);
}
return 0;
}
全卷小结
🎯 本卷关键词:贪心 + 前缀和(T1,"无限廊桥模拟一次,前缀和回答所有询问"的经典转化)、区间 DP + 状态细分去重(T2,CSP-S 史上著名计数题,状态设计的严谨性直接决定成败)、由外向内逐层贪心(T3,回文结构 + 字典序贪心,O(n) 但边界极多)、平面图对偶 + 不交叉配对 DP(T4,把最小割做成对偶图最短路再套环形区间 DP)。四题梯度分明:T1 是送分的思维好题,T2/T3 是中档偏难的实现题,T4 则需要平面图转对偶图的知识储备,属于省选级别。
📢 下期预告:2022年CSP-J第一轮(入门级)真题及答案,欢迎持续关注,每天一套真题带答案,稳步冲击 CSP/NOIP!
题目版权归 CCF 所有,本文仅作学习交流之用;答案经多个独立来源交叉核对,若与官方公布不一致,以官方为准。
💪 建议先掐时间独立把四题写一遍再对照代码复盘:T1 体会"固定规则下与方案无关"的转化思想,T2 重点亲手推一遍 6 个状态的转移并想想为什么不会算重,T3 用样例 1 把 LL/LR/RL/RR 四种配对逐一过一遍,T4 先掌握 k=2 的对偶图最短路再逐步理解多终端情形。加油,我们明天见!