「CSP 2020」退役有感
CSP 2020 联赛
退役有感。 # 比赛经历 ## A 开场看到题目就知道这道题可能会浪费我很长时间，但是这是第一题，如果简单题没有做出来，排名肯定不理想了。 主要是不知道后面题目的难度，而且这道题显然是一道不需要动脑子的题目，所以树立了无论如何都要把这道题拿满分的观念。（也许是对的，但是可能结果不尽人意）
首先这道题一定是一个模拟题，放在第一题的位置，而且题目流程相对复杂，没有考虑时间复杂度上的问题，感觉是模拟整个过程就完全可以通过，就直接上手开始写的。
一开始没有完整的思路，就是想到哪里写道哪里，没有仔细思考怎么做比较好写，浪费了很多时间。一直没有注意部分分，写起来比较迷茫。大约到了 \(1\) 小时左右注意到了部分分，发现如果 \(\operatorname{O}(n)\) 预处理 + \(\operatorname{O}(1)\) 询问。就有 \(80pts\) 这一部分大概只需要 \(5\) 分钟就可以写完，然后注释掉之前写的垃圾，\(5\) 分钟写完了 \(\operatorname{O}(n)\) 做法。还是没看后面的题目，坚持着第一题必须拿满分的信念，继续做剩下的 \(20pts\)。剩下的 \(20pts\) 询问在 的数量级在 \(10^9\) 左右。逐年眺的话大概每次需要 \(\lfloor \frac{10^9}{365} \rfloor = 2739626\) 次运算 不是很确定能不能通过。然后发现这个年份显然可以二分，然后预处理的部分已经包含了所有特殊情况，对闰年的判断条件容斥了一下感觉可以做到 \(O(1)\) check，虽然预处理了，但是细节仍然很多，处理了很久，终于在大概在开始 \(2\)h 的时间里通过了大样例。但是没有对拍，因为线性预处理不可能过，而且样例已经包含了所有的情况。主要是时间已经很不够用了，后面还有三道题，时间剩下不到 \(2\)h ，基本上已经确定要退役了。直接放弃听天人命了。
后来想了一下，题目要求 \(10^5\) 询问，询问数量级为 \(10^9\)。我这个做法好像能做到 \(10^6\) 询问，单次询问数量级 \(10^{18}\)。所以我在考场上写二分是在炫技吗……最后检查了几个特使情况，自己觉得挺稳的，中间该开 long long 的地方都已经开过了，后来发现数据里面的读入数据就已经超过 int 了。还是丢了\(10pts\)。
B
冷静了 \(10\)min ，确定了虽然已经完蛋但是还要好好打的想法。开始飞速读题，读了一遍感觉这直接做就可以了吧……以为是读错题了，然后又读了一遍，感觉确实是一个大水题啊…… 开始写代码，这时候已经很紧张了，写错很多次，感觉这种状态写出来的东西会出问题，但是顾不了那么多了。大概 \(7\)min 写完了，调试了一下样例用了 \(5\)min 左右。然后通过了最大的样例。还剩下大概 \(1\)h 多一点的时间，剩下两道最难题目，仍然很迷茫，但是感觉已经 \(200pts\) 到手了。
光顾着写没注意这题的复杂度，我的实现很简陋，复杂度只能做到 \(O(n\operatorname{log}n)\) ，但是数据范围是 \(10^6\) 感觉应该能过，就没有继续优化。
后记：评测的时候，出题人卡满了 \(O(n\operatorname{log}n)\) ，根本过不去。而且最后需要特判答案是否溢出，根本没注意那里。最后输出的数字可能是 \(2^{64}\) 。计算机中无符号64位整形最大是 \(2^{64}-1\)。所以这个情况需要计算器算好 \(2^{64}\) ，然后当成字符串输出。然后我觉得太恶心了。
C
第一眼看题的时候，感觉这道题和正睿的一道题非常相似，（其实这道题的大概\(20pts\)的部分分可以直接用正睿的那个题的方法做），但是只有 \(50\)min 了，后来又去看了看 \(D\) 题，\(D\)题有\(20%\)的分数\(n < 4\)这一部分分应该很简单。权衡了一下决定好好写 \(C\) 题。\(C\) 题的部分分特别多（\(20pts\) 暴力 + \(20pts\)正睿做法 + \(10pts\)线段树模板 = \(50pts\) ），然后赶紧开始写。后来呢，第一档分数，状态极差，完全没心情，特别紧张，写了 \(40\)min 才过了样例。最后只剩下 \(10\)min 了，监考老师都开始准备收拾东西了……我哭了……感觉这种状态下 \(10\)min 写双标记线段树有点扯。算了退役了……
最后检查了文件夹，一遍一遍测了样例和文件读写。还剩下\(5\)min想了想回去怎么好好学文化课……沮丧之极。难受的在于 还能拿到的但是没时间写的分数大概是\(50\)分左右，时间，时间，时间。唉……
后来发现其实这个 \(C\) 题挺思路很好想，这个题不能直接套用正睿的做法关键在于乘法和加法操作不能合并，如果展开操作，这个操作数量是\(O(n^2)\)级别的，既然不能展开，那正解一定是考虑每单个操作的贡献，这些在考场上第一眼就能看出来的，但是由于很多原因都没有仔细想下去。感觉如果时间充足我能想出来。
其实也不能怨出题人题目排布有问题，其实是自己没好好权衡题目难度，紧张情况下没办法保证代码质量。之后问了冯友和，虽然他 \(C\) 题最后只剩下了 \(40\)min，但是他在比赛快结束的 \(40\)min 中写完了 \(5\)min写完了暴力，\(5\)min 写完了线段树，\(5\)min写完了拓扑排序，我一个暴力最后都快不知道我写的是啥了……还是要多加练习啊。
今后注意
- 还是应该仔细的阅读全部试题，就算第一题比较恶心人，也不会像这次比赛那样做第一题用时很长就感觉自己菜到无可救药。
- 最简单的题目也要注意部分分，能够给你实现上的简便提示。
- 不要紧张，写的时候好好调整心态，思考每一种可能的最坏情况，认真解决。
- 根本原因是不熟练，如果能保证代码写完就不出错，就不会出现什么时间不够用的情况。
- 代码方面：注意
long long可以局部#define int long long,#undef int，保证不会溢出。注意最坏情况下程序可能的出错。在时间允许的情况下优化复杂度。 - 估分 \(260\) 实际 \(175\) 还是不要对自己的代码太有信心，忘开一个
long long就送退役了…… - 之后还是要多做思维难度大的题，毕竟\(C\)题没有在\(40\)min里想出来QAQ。