8.27 模拟赛（2019 CSP-S 真题）

省流：预计 \(40+0+15+0\)，实际 \(35+4+15+0\)。

比赛复盘

开局浏览题。A 没太看懂（廊桥是什么？机场里有这玩意？）；B 题很好读懂，但没思路；C 括号序列感觉可做；D 一眼不会。除 C 外都感觉没太有戏。

顺序开题。看懂 A 后，分析了一段时间后忘记了题面中“先到先得”的原则，导致推到一些歪的贪心浪费了一段时间。想到了求解 \(f(i),g(i)\) 然后答案是 \(\max f(i) + g(n-i)\)，但是不会快速求 \(f(i), g(i)\)。

B。想了很长时间的特殊性质也没想出来。结果发现我连 \(\sum n \le 50\) 最低档的 \(35\) 分也不会。先把 B 丢了。

C 输麻了。先尝试了 \(f(l, r)\) 的区间 DP，以为按照题意中的超级括号序列的定义模拟就是一个 \(\mathcal O(n^4)\) 的算法。写加调用了 1h+。结果是样例 1 过了，样例 2 输出 \(28\)（正确 \(19\)），调不出来了。这时反应过来会算重。于是尝试在状态里加第三维，但此时大脑已经混乱了最终也没想出来。

写 C 的时候看了看 D。看到数据范围后果断放弃回去继续写 C。

此时 \(11\) 点了（比赛还剩 \(1\) 小时），A 正解没冲出来，B 特殊性质没想出来，C 恶心到要吐了，D 神秘。但重点是现在一分没得？？？？？

发现 A 的 \(40\) 分可以写。BCD？？

B 的特殊性质只有 \(15\)，按理分这么少的特殊性质应该不难啊？又尝试猜了若干结论没猜出来。彻底放弃 B。

C 的 \(n \le 15\) 是最暴力 dfs。但发现 check 不会写。此时相当刚才写的一坨东西虽然会算重但不会算少，用这个 check 就行。复制过来改了改就把小样例过了。期望拿 \(15\) 分。

不是 CSP-S 才 \(40 + 15\) 这能忍？因为 D 实在太神秘所以在最后 \(10\) 分钟尝试写 B 的 \(\sum n \le 50\)。虽然测试点 \(1 \sim 7\) 应该不会全对但至少没开 Subtask 应该能得到一点分。于是写写写。但最终还是没过第一个样例。

赛后看榜 B 题大家都会 40 分。我什么时候这么菜了 /fn/fn/fn。哦读错题了那没事了。

比赛过程中好的做法和不足

1. 做的比较好的地方：无。

2. 不足（时间分配、代码能力、思维能力等）：

   1. 一题正解都没冲出来。
   2. B 读错题；
   3. 比赛前 3 个小时毫无进展，一分没得；

试题分析

• T1：堆，贪心。
• T2：模拟，构造。
• T3：区间 DP，模拟。
• T4：不道。

补题情况

A. P7913 [CSP-S 2021] 廊桥分配

如果我们能求 \(f(i)\) 表示当国内区有 \(i\) 个廊桥时，停靠飞机数量的最大值，\(g(i)\) 同理，那么答案为 \(\max f(i) + g(n-i)\)。

考虑快速求解 \(f\)。\(g\) 同理不再赘述。

因为先到先得，所有我们将区间按左端点排序。每次遍历到一个区间时，找到这个区间内编号最小的没有被占用的廊桥，分配给 \(i\)。你可以理解成有若干个集合 \(S_i\)，表示时刻 \(i\) 还没有使用过的廊桥组成的集合。每次求 \(\operatorname{mex}(S_l\cup\dots\cup S_r)\)。这里 \(\operatorname{mex}\) 指最小的没有出现过的正整数（没有 \(0\)）。

令 \(h(i)\) 表示 \(i\) 被分配的廊桥编号。那么 \(f(k)\) 为 \(h\) 中 \(\le k\) 的值的数量。可以理解成将所有 \(> k\) 的位置放到远机位。

在数轴上将 \(h\) 中的数标记后，前缀和就是 \(f\)。考虑快速求解 \(h\)。

从小到大枚举 \(i\)，表示我们要决策将第 \(i\) 架飞机放到那个廊桥。维护两个集合。\(S_0\) 维护与 \(i\) 相交的所有区间，\(S_1\) 维护仍空闲的廊桥。那么 \(\min S_1\) 即为所求。

我们思考如何从 \(i - 1\) 修改至 \(i\)。

注意此时有 \(l_{j} < l_i\)（\(j \in S_0\)）。所以如果 \([l_j,r_j]\) 与 \([l_i,r_i]\) 有交集当且仅当 \(r_j > l_i\)。所以我们将 \(S_1\) 中的数按照 \(r\) 从大到小排序，然后循环删数直到上述条件不满足即可。

当 \(S_0\) 中插入一个数 \(i\) 时，\(S_1\) 中应删去一个数 \(h(i)\)。同理 \(S_0\) 中删去一个数 \(i\) 时，\(S_1\) 中应插入一个数 \(h(i)\)。所以我们可以在上述维护 \(S_0\) 的过程中顺带维护 \(S_1\)。

\(S_0, S_1\) 用优先队列维护即可。这是因为我们每次查和删的都是最小的数。

https://www.luogu.com.cn/record/174956626

B. P7915 [CSP-S 2021] 回文

考虑枚举第一步操作是 \(\texttt L\) 是 \(\texttt R\)。以下只说明 \(\texttt L\)，\(\texttt R\) 同理不难赘述。

第一步是 \(\texttt L\) 也就是说 \(b_1 = a_1\)。如果 \(a\) 中另一个 \(a_1\) 出现在 \(x\) 位置的话，因为回文，所以 \(b_n = a_x\)，即 \(x\) 应该是最后一个被操作的数。

也就是说第一步操作 \(1\)，然后操作 \([2,x-1],[x+1,2n]\)，最后操作 \(x\)。

因为我们只能从开头或结尾取，所以我们可以考虑两个栈 \(A, B\)。\(A\) 从栈顶到栈底依次是 \(2\dots x-1\)，\(B\) 从栈顶到栈底依次是 \(2n\dots x+1\)。每次操作的数是任意一个栈的栈顶元素，然后并将其 pop。而从 \(A\) 取相当于 \(\texttt L\)，从 \(B\) 取相当与 \(\texttt R\)。

所以第一次操作一定是 \(2,2n\) 中的一个，最后一次操作一定是 \(x-1,x+1\) 中的一个（即第一次操作的是某个栈顶，最后一次操作的是某个栈底）。因为回文，所以如果这两个栈顶都不等于这两个栈底，则无解。否则我们优先考虑 \(\texttt L\)，因为字典序最小。

模拟即可。

https://www.luogu.com.cn/record/174974158

C. P7914 [CSP-S 2021] 括号序列

令 \(A\) 表示超级括号序列，\(S\) 是一个长度 \(\in [1, k]\) 的全 \(\texttt *\) 序列。根据题意，合法的括号序列一定形如：

• \(()\)

• \(A\)

• \((S)\)

• \((A)\)

• \((SA)\)

• \((AS)\)

• \(AB\)

• \(ASB\)

我们可以总结成下面的情况（这里 \(A\) 的左右端点是匹配的括号）：

• \(()\)

• \(A\)

• \((S)\)

• \(AASASASAASA\dots A\)（很乱，\(A\) 中间夹着 \(S\)，但是开头结尾都是 \(A\)）

• \((SAAASAS\dots A)\)（也很乱，但是括号内 \(S\) 开头 \(A\) 结尾）

• \((A\dots ASASAAS)\)（也很乱，但是括号内 \(S\) 结尾 \(A\) 开头）

这样计数方便些。我们定义 \(4\) 种序列（不一定合法）就能表示出上面的所有括号：

• 第 \(0\) 种：全部为 \(\texttt *\) 且长度 \(\le k\)；
• 第 \(1\) 种：左右端点匹配的超级括号序列；
• 第 \(2\) 种：形如 \(SASASAAS\dots A\) 的括号序列，其中的 \(A\) 都是第 \(1\) 种括号；
• 第 \(3\) 种：形如 \(A \dots AASASAAS\) 的括号序列，其中的 \(A\) 都是第 \(1\) 种括号；

发现第 \(2/3\) 种也很难表达，我们设计第 \(4\) 种：

• 第 \(4\) 种：形如 \(AASASAS\dots AASA\) 的超级括号序列，其中的 \(A\) 都是第 \(1\) 种括号；

那么第 \(2\) 种形如 \(SB\)，第 \(3\) 种形如 \(BS\)，其中 \(S\) 是第 \(4\) 种括号序列。

此时设计区间 DP \(f(l, r, 0/1/2/3/4)\) 表示有多少种将问号确定的方案使得 \([l, r]\) 是第 \(0/1/2/3/4\) 种序列。那么答案为 \(f(1,n,0)+f(1,n,4)\)。转移看代码。

https://www.luogu.com.cn/record/174982460

D. P7916 [CSP-S 2021] 交通规划

不会。