N01P2024 总结

赛时

开赛先五分钟迅速配置好电脑,开始读题。感觉第一题就很神秘,第二题更加神秘,第三题还是神秘,第四题反而看起来挺清新。

秉持着快速过掉前两题的想法,直接开始做第一题。刚开始好一会儿没有思路,过了可能十几分钟,突然发现了每一个连通块可以任意交换,然后就可以贪心了。写完之后有些小问题,调完刚好一个小时。

接着做第二题,很快想到可以容斥,但是式子好像推了挺久的,推了一会儿式子,开写。十点多写完了,但是死活过不了大样例。自己出了一些数据,都发现不了问题。上了个厕所,回来又调了一会才发现有一个式子乘漏了,到十一点才过掉大样例,浪费了很多时间。

有点怕挂分,就写了个指数级暴力对拍,还写挂了,又浪费了 20 分钟。

最后剩一个半小时,我想看看能不能像 CSP 一样弄出第三题,怕大家都过了题我没过,就完了。

感觉挺复杂,推了挺久,推了个结论,写完发现假了,此时只剩三十多分钟了。我断然放弃继续做,暴力不知道该怎么写,就把特殊性质写了,但是菊花图的情况一直过不了大样例,不知道哪里有问题。这时还剩 20 分钟,我又放弃写这 15 分的性质,转而写第四题的暴力。

写第四题暴力的时候其实挺慌,其实也不难写,仅是求一个树上 LCA,再加一个 ST 表罢了。就是怕细节出问题,调不出来。写的时候没有多想,就写了个 O(1)O(1) LCA,写完惊喜地发现可以顺便过特殊性质 B。

只剩两分钟,重新打开第三题的文件,发现我以为图中有 nn 条边,实际上有 n1n-1 条边。赶紧改一改就过了。

期望得分 100+100+16+32=248,好像大家都比我高,不知道能不能拿一等,但是估计一些比赛是去不了了,省选也得吃亏了。

反思

我觉得我第一题切的应该是比较快的,第二题却做得比较慢。究其原因,我对难度的估计还是比较刻板的,放第一题这个位置,我可能就能很快做,第二题我就会有点畏难,有点退缩。平时比赛也是这样,做题也是这样。当知道一题比较难的时候,我往往会失去思考的能力,导致我很多时候其实没有尽全力。

其次是对拍,大样例应该够强了,对拍的数据其实说实话不是很强,数据范围很小。有的时候其实对拍不一定是效率最高的。

前两题做得慢其实不是理由。PrinceX 前两题做得比我还久,但是他在一个半小时内得到了 88 分,我比他多十几分钟,然而只得到了 44 分。当时我放弃了想第三题的暴力,而是想正解,其实暴力都不是很清楚怎么写,说明题目流程也不清楚,又怎么可能想出来呢?

第三题的策略失误使得我损失了第三题 k=1k=1 的部分和第四题的性质 A,成功成为垫底选手了。

后记

出分了,只有 240 分,第三题特殊性质 B 有 19、20、21 三个点,判断的时候只判了 19,导致少了 8 分。

感觉一等有点悬。

后后记

出分数线了,220,如果在重庆我就没有一等了。

Weight Balanced Leafy Tree
连通性相关