CSP2022被吊打游记

· · 个人记录

考点长沙市长郡中学，刚踏入这所学校就感受到了高手的气息……

CSP开考

只报了S，14:20进入考场，因为没什么经验，连虚拟机都没怎么用过，所以就先调了一会VMware。

14:30~18:30

先看T1，一开始想DP秒切，结果发现我的DP会重复计算，于是想了30分钟正解，没想出来，打了个O(n^4)暴搜草草了事。\ T2，一眼看出这是个RMQ水题，打了8个ST表，粗略看了看答案文件，没发现什么问题，因为没学过对拍，就直接默认AC切下一题了。\ T3，一眼看出YES的充要条件是每个点的出度都是1，但不知道怎么搞操作2和操作4，想了45分钟后，打了个O(qn)暴力，然后切下一题。\ T4，想加边后跑Dijkstra，结果发现这样会保龄，于是果断放弃。

赛后

一开始预估40+100+40+0=180，想着拿1=没问题，然后我自学了一下对拍又在自己的电脑上自测，结果发现T2挂了几个点，研究了近1个小时，才发现我的代码会把不存在的情况计入答案（我用0x3f3f3f3f当INF作为不存在情况的哨兵元素，我看它比10^9略大，以为不会挂，结果忽略了乘法问题，乘法可能会产生超过INF的值，从而让INF能够更新答案），所以我在乘法运算时加了个flag，判ST表是否会取到INF，若会取到INF的话，则不用来更新答案，这样写就A掉了。。。以后写哨兵元素我都写个flag判一下再更新答案吧，虽然这样常数会比较大，而且代码会比较复杂，但这样起码能保证不会因为一些莫名其妙的因素挂掉。。。\ T3我的暴力能拿60分，但是MAXN设成了50010（少了个零），还有20分就这么丢了。。。我瞬间感觉自己是个小丑。。。\ 现在我估计我只有40+?+40+0=80+?分（?取0~60），感觉1=可能无望。。。\