CSP-S 2021 爆零记

发布于 2021-10-27  60 次阅读


考试之前

酒店还不错,睡眠很充足,唯一可惜的大概是自己中午没怎么睡着。

考场之上

开考时候没事干,喝了很多水(为后面肚子痛埋下伏笔)。考试机房里键盘敲起来很大声(也有可能是我太用力了),然后偷敲模板被监考老师提醒。

然后开考,用了大概 $20 \min$ 看了一遍题面,大概感觉是 T1 没有什么特殊算法,T2 是一个明显的 DP,T3 构造题,T4 不太可做。

所以自己大概目标是 T1 先写掉,T2 和 T3 一定要做一题出来,T4 打打暴力。

然后是每逢大考肚子疼。但是感觉不是很疼(?),觉得开考就去不大好,然后就没有上厕所准备写完 T1 去。

然后就出了大问题。首先 T1 的大题思路肯定没问题,大概是求一个 $ord_i$ 表示第 $i$ 架飞机要有廊桥的最小廊桥数。这个东西求出来之后直接开个桶记录一下,然后求前后缀统计一遍就好了。

但是不知道为啥,漏看了一个 ”保证 $a_{i,1}$,$a_{i,2}$,$b_{i,1}$,$b_{i,2}$“ 互不相同的条件。

然后就想到其他算法上了,尝试过的大概有拓扑,然而仔细思考发现这东西没法用。

考虑的是把飞机按照到达时间从小到大排序,然后扫一遍统计答案。用优先队列、用 std::set 维护空闲廊桥的信息。后来写到一半,发现这玩意儿没法维护要 $push$ 进来的值到底要放在那个廊桥,然后又想了一些奇奇怪怪的解决办法然而都假了。

然后大概过了 $2h$ 肚子疼得受不了了去上了个厕所。回来冷静了一波仔细看了一下题意,发现保证互不相同,然后想到离散化,然后直接从小到大枚举时间节点,再用优先队列维护最小的空闲廊桥就可以。

然后写完+调完大概是花了 $2h$ $30\min$。T1 花了这么长时间,我大概明白这场比赛接下来节奏应该紧张一点,大概是往三题暴力+一些高档部分分的方向走。

然后去想 T2。T2 思考了一会儿(我也不知道为啥要思考一会儿)发现是个区间 DP。然后就想了个 $O(n^4)$ 的解法想着先拿点分再去优化(后来事实上想出 $O(n^4)$ 之后 $O(n^3)$ 其实优化很快)。但是根据题面中不同的字符串类型写了一车的分类讨论,最后一直误算一种 SAS 的情况以及一些奇奇怪怪的东西,没调出来。

这个时候大概还剩下 $1h$ 不到点,写了个 T2 T3 暴力,T4 大概看了一下,发现没看懂题,暴力不是很好写。

此时发现自己唯一的翻盘点在 T2,然后把代码保存好回去冲 T2 的 DP,可惜最后又有点肚子疼,越调越乱。

最后五分钟大概是麻了,放弃挣扎,再回去检查了一下四题代码。

期望得分 $100+15+28+0=143$。

考试之后

第二天拿到代码测了一下发现自己 T1 Compile Error 了,当时就挺震惊的,毕竟最后五分钟我检查了所有代码,所有代码都是可以通过编译和大样例的,一度怀疑代码收上去出错。

然而事实是我在考场上写了这样一段代码:

struct Plane{
    int l,r;
    inline operator < (Plane& rhs) const{
        return l < rhs.l;
    }
}p1[N],p2[N];

也就是,我在重载运算符的时候没有写明返回值。

这段话应该是这个样子:

struct Plane{
    int l,r;
    inline bool operator < (Plane& rhs) const{
        return l < rhs.l;
    }
}p1[N],p2[N];

我在考场上开了 -Wall-Wextra ,然而都没有发现这个错,并且编译也是可以通过的。

后来查询了一下。

这玩意儿大概是 mingw 的经典问题,漏掉返回值默认返回 int。而这玩意儿只在 Windows 下适用,Linux 下会直接 Compile Error

大概只有 $\le 50$ 分了。

总结

  • 考试中肚子疼一定要第一时间上厕所。

  • 不肚子疼,想不出题了也要上厕所。

  • 心态要好。

  • 要多锻炼 DP 这种弱项。

至于上面提到的问题,解决办法大概是不要 inline

inline 这东西能不用就不用,之前某道题中就是因为在 dfs 函数中加了 inline 导致莫名 Memory Limit Exceeded。现在又因为加了 inline 之后函数头太长,不写返回值显得不是很突兀,查不出来。

以及,在 C++20 之后,inline 将被弃用。所以能不用就不用吧。

幸亏这是 CSP-S,不是 NOIP。希望 NOIP 不要爆炸了。

警醒自己,也警醒后人吧。

Updated On 2021.10.30:
官方成绩出来了,$0+0+44+0=44$,炸得明白。

但是加上 T1 的 $100$ 分后能一等是我没想到的。

感觉血亏。


我们无法选择过去,但我们可以改变未来。