「CSP 2020」退役有感

📄 PDF 📝 Source

CSP 2020 联赛

退役有感。 # 比赛经历 ## A 开场看到题目就知道这道题可能会浪费我很长时间,但是这是第一题,如果简单题没有做出来,排名肯定不理想了。 主要是不知道后面题目的难度,而且这道题显然是一道不需要动脑子的题目,所以树立了无论如何都要把这道题拿满分的观念。(也许是对的,但是可能结果不尽人意)

首先这道题一定是一个模拟题,放在第一题的位置,而且题目流程相对复杂,没有考虑时间复杂度上的问题,感觉是模拟整个过程就完全可以通过,就直接上手开始写的。

一开始没有完整的思路,就是想到哪里写道哪里,没有仔细思考怎么做比较好写,浪费了很多时间。一直没有注意部分分,写起来比较迷茫。大约到了 11 小时左右注意到了部分分,发现如果 O(n)\operatorname{O}(n) 预处理 + O(1)\operatorname{O}(1) 询问。就有 80pts80pts 这一部分大概只需要 55 分钟就可以写完,然后注释掉之前写的垃圾,55 分钟写完了 O(n)\operatorname{O}(n) 做法。还是没看后面的题目,坚持着第一题必须拿满分的信念,继续做剩下的 20pts20pts。剩下的 20pts20pts 询问在 的数量级在 10910^9 左右。逐年眺的话大概每次需要 109365=2739626\lfloor \frac{10^9}{365} \rfloor = 2739626 次运算 不是很确定能不能通过。然后发现这个年份显然可以二分,然后预处理的部分已经包含了所有特殊情况,对闰年的判断条件容斥了一下感觉可以做到 O(1)O(1) check,虽然预处理了,但是细节仍然很多,处理了很久,终于在大概在开始 22h 的时间里通过了大样例。但是没有对拍,因为线性预处理不可能过,而且样例已经包含了所有的情况。主要是时间已经很不够用了,后面还有三道题,时间剩下不到 22h ,基本上已经确定要退役了。直接放弃听天人命了。

后来想了一下,题目要求 10510^5 询问,询问数量级为 10910^9。我这个做法好像能做到 10610^6 询问,单次询问数量级 101810^{18}。所以我在考场上写二分是在炫技吗……最后检查了几个特使情况,自己觉得挺稳的,中间该开 long long 的地方都已经开过了,后来发现数据里面的读入数据就已经超过 int 了。还是丢了10pts10pts

B

冷静了 1010min ,确定了虽然已经完蛋但是还要好好打的想法。开始飞速读题,读了一遍感觉这直接做就可以了吧……以为是读错题了,然后又读了一遍,感觉确实是一个大水题啊…… 开始写代码,这时候已经很紧张了,写错很多次,感觉这种状态写出来的东西会出问题,但是顾不了那么多了。大概 77min 写完了,调试了一下样例用了 55min 左右。然后通过了最大的样例。还剩下大概 11h 多一点的时间,剩下两道最难题目,仍然很迷茫,但是感觉已经 200pts200pts 到手了。

光顾着写没注意这题的复杂度,我的实现很简陋,复杂度只能做到 O(nlogn)O(n\operatorname{log}n) ,但是数据范围是 10610^6 感觉应该能过,就没有继续优化。

后记:评测的时候,出题人卡满了 O(nlogn)O(n\operatorname{log}n) ,根本过不去。而且最后需要特判答案是否溢出,根本没注意那里。最后输出的数字可能是 2642^{64} 。计算机中无符号64位整形最大是 26412^{64}-1。所以这个情况需要计算器算好 2642^{64} ,然后当成字符串输出。然后我觉得太恶心了。

C

第一眼看题的时候,感觉这道题和正睿的一道题非常相似,(其实这道题的大概20pts20pts的部分分可以直接用正睿的那个题的方法做),但是只有 5050min 了,后来又去看了看 DD 题,DD题有2020%的分数n<4n < 4这一部分分应该很简单。权衡了一下决定好好写 CC 题。CC 题的部分分特别多(20pts20pts 暴力 + 20pts20pts正睿做法 + 10pts10pts线段树模板 = 50pts50pts ),然后赶紧开始写。后来呢,第一档分数,状态极差,完全没心情,特别紧张,写了 4040min 才过了样例。最后只剩下 1010min 了,监考老师都开始准备收拾东西了……我哭了……感觉这种状态下 1010min 写双标记线段树有点扯。算了退役了……

最后检查了文件夹,一遍一遍测了样例和文件读写。还剩下55min想了想回去怎么好好学文化课……沮丧之极。难受的在于 还能拿到的但是没时间写的分数大概是5050分左右,时间,时间,时间。唉……

后来发现其实这个 CC 题挺思路很好想,这个题不能直接套用正睿的做法关键在于乘法和加法操作不能合并,如果展开操作,这个操作数量是O(n2)O(n^2)级别的,既然不能展开,那正解一定是考虑每单个操作的贡献,这些在考场上第一眼就能看出来的,但是由于很多原因都没有仔细想下去。感觉如果时间充足我能想出来。

其实也不能怨出题人题目排布有问题,其实是自己没好好权衡题目难度,紧张情况下没办法保证代码质量。之后问了冯友和,虽然他 CC 题最后只剩下了 4040min,但是他在比赛快结束的 4040min 中写完了 55min写完了暴力,55min 写完了线段树,55min写完了拓扑排序,我一个暴力最后都快不知道我写的是啥了……还是要多加练习啊。

今后注意

  • 还是应该仔细的阅读全部试题,就算第一题比较恶心人,也不会像这次比赛那样做第一题用时很长就感觉自己菜到无可救药。
  • 最简单的题目也要注意部分分,能够给你实现上的简便提示。
  • 不要紧张,写的时候好好调整心态,思考每一种可能的最坏情况,认真解决。
  • 根本原因是不熟练,如果能保证代码写完就不出错,就不会出现什么时间不够用的情况。
  • 代码方面:注意long long可以局部#define int long long,#undef int,保证不会溢出。注意最坏情况下程序可能的出错。在时间允许的情况下优化复杂度。
  • 估分 260260 实际 175175 还是不要对自己的代码太有信心,忘开一个 long long 就送退役了……
  • 之后还是要多做思维难度大的题,毕竟CC题没有在4040min里想出来QAQ。