CSP2021 游记

unputdownable · 2021-10-25 21:38:17 · 个人记录

Day 0

没题，上午去学校参加了运动会，下午复习算法，一天没了。

Day 1

13:00

抵达考场，直接跟文渊同学进去了。

14:00

吐槽时间

被老师强制叫进去了，发呆半小时。

一看屏幕，怎么浏览器还是 360，人傻了。

再看，怎么有一个 CSP-J 2021.pdf，傻了。

瞟一眼隔壁电脑，竟然有上午 network 的文件和代码，以及上午所有下发文件，实在是高啊。后来联系老师删掉了

另外，为什么我右边是 224，左边是 226，我是 215 啊。（看前面一排，似乎都是顺序的...）

而且你这电脑高度和挡板高度，属于挺胸就能看到旁边一半屏幕的那种（不过我还是一个守法的好考生！）。

此时前面一排有一位写码头的老哥，监考走来走去也看不见...

隔壁老哥一直跟监考抱怨输入法的事。

14:30

康康题，T1 怎么不是一眼题。

后来发现如果强制让飞机停在编号最小的廊桥，那么不论有几条廊桥，每架飞机停的位置不变，若这个编号不存在，就只能去远机位了。

于是写了个 priority_queue 就过了。

15:30

调出来才发现优先队列默认大根堆

调完已经 1h 过后，开始肝 T2。

开始写了一个 O(nk) DP，然后发现没有 (***()***)，暴毙了。

后来写了一个区间 DP 的记忆化搜索，调了 0.5h，发现是 O(n^4) 的。

前缀和优化，常数++，但是 O(n^3) 过了大样例。

16：30

心态有点炸。开始想 T3。

观察到后取的 n 个一定是一整个区间并且 1-n 都出现正好一次。

于是我想出了四指针，不过别人的四指针如上，我的四指针如下：

我真的脑回路清奇啊。

于是 O(n) \rightarrow O(n^2)。

后来觉得取最右一个即可，就胡上去了。

18：00

开始 T4。