Day -1

因为 CSP 第二轮非零分应该就可以晋级，所以没有什么太大的考试压力。

学军紫金港校区。

晚上 18:30 从海亮出发到酒店，整顿一下就休息了。

Day 1

上午

总结一个经验就是在酒店的自助早饭中摄入大量高热量食品（如培根）可以让一整天都不会饿。我每次考试前都会在酒店里吃一大堆培根。

没什么有意思的，调整一下心态记了遍注意事项上午就过去了。

中午

由于早饭培根吃得太多了所以中午没啥食欲，象征性吃了几口就吃撑了。

听说上午的题目挺简单的，希望下午的也可以简单一些吧。

非常非常感谢 Maplisky 和 cyl06 千里迢迢从杭师大考点跑来找我。

下午

原本以为有 45min 试机环节的，到了考场发现监考老师不让碰机器，干坐了半个小时。

在考场门口面到了 Rosmarinus，非常感谢 Ros 在开考前挤出时间跑过来找我。

考试开始，先看了一遍四道题，对每道题都思考了一下大概的解题方向。发现除了一个 T2 是个比较裸的区间 DP 题以外其他几道题好像都没有什么想法。

因为这个时候感觉题目总体偏难，所以没有花时间考虑 T3 T4，先直接看 T1。发现 $n$ 到了 $10^5$，考虑快速将 $i$ 个廊桥的答案递推到 $i+1$ 个廊桥的答案。不难发现一定存在一种 $i+1$ 个廊桥的方案使得在 $i$ 个廊桥时使用廊桥的飞机正好使用其中的 $i$ 个廊桥。因此我们只需要考虑多出来的这个廊桥能够接纳哪些飞机即可。直接 set<pair<int,int>> 模拟就做完了，复杂度 $O(n \log n)$。写完一遍过了大样例，此时是开考 0.5h。

然后开始做 T2，最简单地，考虑 $f[l][r]$ 表示 $[l,~r]$ 为超级括号序列的方案数，按照题面上给出的所有规则模拟转移即可。其中对于 ASA 规则，考虑枚举一个 $x \in [l,~r]$，令 $l \sim x$ 部分为第一个 A，接下来考虑所有满足条件的 $y \in [x+1,~r]$，令 $x + 1 \sim y - 1$ 部分为 S，$y \sim r$ 部分为第二个 A。维护所有满足条件的 $y$ 只需要用一个队列存放当前 $x$ 对应的所有满足条件的点即可。写了一遍后发现没有过第二个样例，数据较小用手推检验 DP 发现忘记考虑去重情况（()()()），使用常用的 trick，$f[l][r]$ 保存 $[l,~r]$ 不可从中间某个位置裂开的合法方案数，$g[l][r]$ 保存 $[l,~r]$ 允许从中间某个位置裂开的合法方案数。对于可能算重的情况 AAA 和 ASASASA，枚举 $x,~y$ 时使用 $f[l][x] \times g[y][r]$ 计算答案即可。有一些细节错误，静态差错较快地找出了他们。写完时是开考 1.5h。

然后看 T3，由于是回文串，在我们知道正数第 $i$ 步选出的数时也就知道倒数第 $i$ 步选出的数了。考虑同时考虑 $1 \sim n$ 和 $2 \times n \sim n + 1$，容易想出一个 $n^4$ DP 方法：在第 $i$ 轮中我们同时考虑 $1 \sim i$ 和 $2 \times n \sim 2 \times n - i + 1$ 部分，第一部分应当组成原序列的前缀和后缀，第二部分应当组成剩余部分的一个连续段。这里就获得两个区间的信息了，用四维状态存储即可。但是 $n^4$ 的复杂度过高，仔细想一下之后发现对于一个状态，其合法转移数量相当少，只在 $0 \sim 2$ 范围内。但是似乎并没有什么很好的优化方向。手推一下样例之后发现对于一个状态似乎在只考虑其字典序较小的转移下是可以得出正确结果的。继而从大样例中抽出几个较小的点手推了一下发现找不出问题。也构造不出来可以卡掉该方案的数据。由于代码并不复杂，花了 10min 写了一下，发现过了大样例，此时是开考 2.5h。

由于感觉 T3 的做法挺正确的，所以就先开始考虑 T4 了。但是主要的思考方向都在 2-SAT 和类似的结构上，因为 $n \times m$ 过大所以并没有考虑网络流（网络流只会写板子）。最后第一档暴力分也没有想出来怎么做。

期间抽出时间考虑了一下 T3 做法的正确性，容易发现对于一个状态而言，其不管下一步转移是 L 还是 R，对于之后的每一步转移而言都不会让情况变得更劣。在当前状态允许下一步转移为 L 或 R 的情况下，这一步选 R 并在未来选 L 如果合法，则其一定能转变为这一步选 L 并在未来选 R。因此不可能出现在当前能够选择 L 或 R 的状态下选 L 会导致无解而选 R 有解的情况。因此 $O(n)$ 贪心是正确的。

最后 T4 没有写出来暴力分，期望得分 $100+100+100+0=300$。

考场代码：

1. T1: Code
2. T2: Code
3. T3: Code

---

各路民间数据测出来也都是 $100+100+100+0=300$，应该是没什么问题了。

根据今年 CSP-S 第一轮和第二轮的考试知识点来看，一些在往年被我们放入省选知识点的，而在考纲中偷偷放入提高级的知识点均有被考到，出现了比往年严重的发现“考的东西没学过”的情况。

也许应该翻翻考纲多学点难知识点了。