2021 CSP-S 复赛游记

昨天，也就是2021年10月23日，我刚刚考完了本年度的 CSP-S 第二轮。晚上六点多走出考场时，我人已经麻了。欲知发生了甚么事，请继续阅读本文。

P.S. 去年复赛游记请移步：2020 CSP-S 复赛游记

Day 0

复赛那天恰逢成人高考，原以为我校应该做不了 CSP 认证点，和初赛一样要跑很远去华二考试，结果一看准考证，认证点竟然就在自己学校？！瞬间狂喜，而且机房也在以前刷题的机房，监考老师就是自己教练。

考试前一天下午因为成人高考布置考场三点多就放学了，回到家大致梳理了一下常用模版的实现思路。由于今年9月1日起 NOI 系列活动启用全新的技术标准，采用 C++14 标准，放开了大部分原本禁用的下划线开头的函数，pbds也可以使用，因此又现学了一下一些原本禁用的函数和库。

Day 1

下午提前45分钟到达学校，看到校门口好多人于是想也没想就跟在后面排队测温，快排到我时我瞥了一眼工作人员的胸牌，一眼就看到大大的 SHMEEA 的标志。嗯？怎么是上海市教育考试院的牌子？再一看别人手里拿的准考证，然后瞬间明白了我混进了成人高考的队伍。当然也无伤大雅，进去后直奔科技楼，终于看到教练在门口负责收集考试安全承诺书。因为时间还早就先去底楼的实验室开了台电脑练习一下手感，提前十五分钟再进楼上的考场。

到点了公布解压密码，一次输对，解压、建文件夹一气呵成，毕竟都打了两年比赛了。然后开始看题，发现今年可以吸氧（开 O2 优化）诶，STL 可以放心用了。吸取去年 T1 的教训，我把4道题都看完了。然而看完我就慌了，因为我根本找不到签到题，就只好先从 T1 开始。

T1 廊桥分配 airport

尝试抽象了一下数学模型，感觉和线段覆盖有关？莫非是线段树？那我可不会打。思索了半小时没啥正经的思路，暴力做法倒是想到了，也就是将每架飞机的起飞降落都分别看成一个事件，用结构体维护事件，上来先把事件按时序用 sort() 排列，然后对于每一种分配方案再模拟时间轴，统计停靠廊桥的飞机数量，最后取其中的最大值。当然我也很清楚这样的做法时间复杂度是 $O(nlogn(m_1+m_2))$，看了下数据范围 $n$ 和 $m_1+m_2$ 都要到 $1e5$，明显会爆炸。然而已经过去半小时了，实在没什么更好的思路了，只能先暴力开搞。半小时写完样例都通过了，可见样例非常水。

T3 回文 palin

因为 T2 实在没啥想法甚至连暴力都不知道咋写，果断跳 T3。这题也没啥正经做法的思路，看到输出字典序最小的结果考虑可以 DFS，优先走搜索树的左子树即可，当然看了下数据范围肯定炸，因此想写个 DFS 再试试看能不能剪枝。写完 DFS 过了前两个样例，考虑剪枝。发现搜索到 $n+2$ 层就可以开始判断是否回文了，如果不是就直接回溯，即

if (k>n+1 && (b[k-1]!=b[2*n+2-k])) return;

然而样例3还是炸，遂放弃。

T4 交通规划 traffic

题看起来都费劲，而且不像去年，今年这道没有好做的部分分。显然不可做，就直接放弃了，回头去看 T2。

T2 括号序列 bracket

这题一上来完全没往 DP 上想，我的思路是枚举每个?可能的值，再判断整个字符串是否合法。但是问题就出在这个判断函数应该咋写，我联想到了利用栈进行括号匹配的操作，于是大胆猜想这题也应该是这么干的，只不过还要确认连续出栈的*个数小于等于 $k$，然而很不幸猜错了。当样例1死活过不了之时，我才突然发现我这个算法很容易就证伪了。然后我就开始想另一种校验字符串合法的方式，完全陷入了这种思维定势导致我浪费了大量时间。

最后只剩下半小时了我才突然意识到 DP，结果当然并没有推出转移方程。无奈放弃。试图开一下虚拟机准备跑一下 T1 T3，结果学校的破电脑根本承受不住竟然直接死机了，硬盘仿佛在呼啸，最后也没测成。

到点交卷签字走人，我觉得我凉透了，应该是没有三位数了。

2021.10.24

一早测了下洛谷民间数据，40+0+28+0，我人没了。后来发现 T3 还有一个枝忘剪了，加了行代码直接 28pts 变 40pts，我人麻了。

总结

今年可以说更加注重思维的考察，没有去年的大模拟、卡精度之类的妖魔鬼怪，但是对于我这种缺乏思考能力的选手而言确实是挺有难度的，至少我认为比去年难多了。而我这次 T2 被自己刚开始的思路局限住了，没有充足的时间去思考 DP 做法，也值得引以为鉴。

总之这场 CSP 打得稀烂，但愿还能有机会苟进 NOIP。