CSP-S 2021 游记

这次 CSP 比赛之前比较平静的说，没什么 考试加油 一类的消息/kk。实际上这次考试挺重要的，这大概是我获得 ISIJ 参赛名额的最理想机会，虽然按理说九年级还有一年，但是九年级我的状态不一定会很好，毕竟有巨大的 whk 压力，我还没有能够得心应手 whk 的实力。

早上睡了个究极大懒觉，然后在家里看看书，中午到 hsy 坐车去考试。

这次考试准备的比较仓促，没带啥吃的喝的，好在中午吃的挺好。

在车上又小睡了一会，至少保证在考场上不会犯困。

高中生考场都在八楼，我因为是初中生考场就在一楼，所以也见不到太多省内较强的 OIer。

到了考场果断选用 noi linux，考场工作人员帮忙把考题共享到了虚拟机内，感觉这波操作非常强。

noi linux 可以用 vscode 写代码，但是不知道出于什么想法 noi linux 原生 vsc 内置的 c++ 插件根本不是完整版，然后就没有代码补全和调试功能，只能当个裸的编辑器用。考试全程都用的 cerr 调试，一定程度上影响了效率，但至少对现在的新版 noi linux 更熟悉了。

廊桥分配

看到题首先容易想到的是用一个 priority_queue 维护飞机飞走的时间，然后在廊桥数量给定的情况下就可以在 $O(n\log n)$ 的时间复杂度内求出有多少飞机可以使用廊桥，然后猜了个凸性，这样做复杂度 $O(n\log^2n)$。

后来自己把凸性给叉掉了。最开始我想的是在一个 priority_queue 的基础上记录每架飞机到达机场时机场共有多少飞机，这玩意记作 $tot_i$，那么当廊桥数量为 $p$ 时只需要对满足 $tot_i\le p$ 的飞机进行计数就行。

测了一发样例发现这玩意假了，原因是机场现在停着的飞机不一定占用了廊桥，纸上手玩了一下样例发现可以对机场的机位进行编号，$1\sim p$ 为廊桥，$p$ 未知，每架飞机贪心的往编号较小的机位上停（这样有可能听到廊桥），正确性显然，机场的空机位再开一个 priority_queue 维护即可，复杂度 $O(n\log n)$。

考场上在这题上浪费了一个多小时的时间，代码写错了一些细节，没有调试功能的情况下对着 错误流 + 大样例 硬调还是比较自闭，好在最后还是把这题改对了，以后其实应该尽量在写代码时细心一点，避免繁琐的调试过程。

期望 100

括号序列

区间dp显然，但是考场上不是很会处理这道题，情况非常复杂，不会很好的处理 **(...)* 这一类不合法情况。

这题挂了，dp底子不够，思路还是不够清晰。

期望 0

回文

构造好题。

构造题需要套路和灵感。

KAMIYA

很可惜的是我在构造上还是缺乏经验，这道题遇到后并没有太好的想法。

基于枚举目标状态打了一个暴力，这样做是 $O(nn!)$ 的，考完后发现这样做很蠢，完全可以枚举操作序列，代码难度急剧减小，复杂度为 $O(n2^{2^n})$，不知道哪种写法剪枝效率高一些，直觉上来讲似乎第二种写法严格优于第一种。

据说这题 xjt 剪枝 0.7s 卡过了大样例，爬了。

期望 28

交通规划

这玩意感觉出的挺神仙的，稍微分析一下不难发现 S 连白点，T 连黑点，做一下最小割就行，这样可以拿到大量部分分。

但是考场上留给我的时间不多，我这题思路走太慢了，而且 dinic 怕是考场难得打出来。

这题最终弃了。

期望 0

---

合计期望 128，如果我高中这玩意就是退役分了。

$Updated$ Hydro 估分 100+5+28+0

总体来看很不理想，dp 和 构造 都是属于积累不够，题做的太少，另外有些知识点不够熟悉，考场上打不出来的话那这玩意跟不会也没多少区别了。

后期继续努力吧，心态需要调整，不要让自己受到身边某些环境的负面影响，积极备战 noip，查漏补缺。

学校 whk 也尽量不要让自己掉的太远。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。