CSP-S2 2021 场外

说在前面

由于我初赛太逊了，导致我今年没去S2。不过我在复赛过后还是看了卷子，以下内容大概都是在独立思考下想出来的。

T1

感觉这个题比排水系统/julian良心。
不难发现飞机肯定是优先排在前面，那么也就是说我们先求出来有无限多廊桥的情况，然后作前缀和即可，国内和国际单独做，最后枚举0~n作为国内廊桥个数取max。
那么无限多廊桥的情况怎么弄呢？一开始属实把我整不会了。后来想想，主要是解决几个东西：
1.找到最前面的空廊桥（查询）
2.进入空廊桥（单点加）
3.起飞（单点减）
不难发现直接一波线段树二分完事，不过目测码量有点大。

rush成功了，一遍过，3.14KB，不过普遍比其他做法慢3倍。哈哈。

T2

看到题目感觉挺震撼，什么东西啊。
后来仔细分析，注意到了(n le 500)，确认是一个区间dp了应该。
一开始设(f[i,j])为总个数，但是发现对于()()()...()之类的东西会重很多，样例2过不去。
然后考虑(f[i,j])记录((...))类，然后(g[i,j])记录AB,ASB之类。
转移自推，这里讲一个东西，就是ASB的(mathcal{O}(n^3))优化

[egin{aligned} Delta{g_{i,j}} &= sum_{i + 1 < k < j} sum_{k le l < j,l - k + 1 le K} (f_{i,k - 1} + g_{i,k - 1}) cdot isS_{k,l} cdot f_{l + 1,j} \ &= sum_{i + 1 le k < j} (f_{i,k - 1} + g_{i,k - 1}) cdot left( sum_{k le l < j,l - k + 1 le K} isS_{k,l} cdot f_{l + 1,j} ight) \ & (发现k le l < j,l - k + 1 le K可以转换成k le l le min{j - 1,k + K - 1})\ &= sum_{i + 1 le k < j}(f_{i,k - 1} + g_{i,k - 1}) cdot left(sum_{k le l le min{j - 1, k + K - 1}} isS_{k,l}cdot f_{l + 1,j} ight)\ & 注意到isS_{k,l}具有单调性，其值为1的一段满足条件的l的值是一段连续的区间[k,l_0]。\ & 考虑预处理出每个k的l_0(mathcal{O}(n^2))。\ &= sum_{i + 1 le k < j}(f_{i,k - 1} + g_{i,k - 1}) cdot left(sum_{k le l le min{l_0,j - 1}} f_{l + 1,j} ight)\ &(变得好看一点)\ &= sum_{i + 1 le k < j} (f_{i,k - 1} + g_{i,k - 1}) cdot left(sum_{k + 1 le l le min {l_0, j - 1} + 1} f_{l,j} ight)\ & 考虑到f（在当前使用到的）应该已经计算完全。所以后面那个东西开个前缀和即可。 end{aligned} ]

rush完了，3K+，震撼，不过有不少注释，删掉应该会小很多。

T3

还没想，看上去像一个比较思路清奇的题。
update：写完了，写了3.8K/xia
先来个简短题意：
给一个正整数(n(1 le n le 5 imes 10^5))和长度为(2n)的序列(a)，(a)中(1sim n)每个数恰好出现2次。每次可以从(a)的开头(L)和结尾(R)取出一个数放到序列(b)的结尾。求能让(b)成为回文序列的操作序列，如果没有输出-1，如果有多种输出操作序列字典序最小的。

看上去第一眼不太会，那就先玩样例：

5
4 1 2 4 5 3 1 2 3 5

不难发现，我们把一个数放到(b)中时，它所对的那个相等的数的出现顺序也确定了。
设我们选了的数用<>表示，已经被确定的用()表示。

5
<4> 1 2 (4) 5 3 1 2 3 5
L

我们发现(4)必须是最后一个被点到，那么倒数第二个只能是2或5。发现5可以通过R点出来，而2不行，那就点5.

5
<4> 1 2 (4) (5) 3 1 2 3 <5>
LR

(5)必须是倒数第二个被点到，那么倒数第三个被点到的只能是2或3。发现3可以通过R点出来，而2不行，那就点3.

5
<4> 1 2 (4) (5) (3) 1 2 <3> <5>
LRR
5
<4> <1> 2 (4) (5) (3) (1) 2 <3> <5>
LRRL

此时我们发现既可以L又可以R，那为了字典序最小，肯定L优先。

5
<4> <1> <2> (4) (5) (3) (1) (2) <3> <5>
LRRLL

我们发现()区间是连续的，当它的长度到达n时，可以停止了。然后在将()序列处理一下即可。
第一步R的话同理的。

T4

不会，不做评价！