CSP2020 总结

被 T1 搞得心态爆炸导致 T3 彻底降智，最后一小时浑浑噩噩一分都没捞着，大失败！

$T1. 儒略日$

打了一个半小时左右，真的是。。。本场崩的罪魁祸首，关键是年份还算错了一处（取模），只拿到了暴力分。。。。

啊！！！！气死我了！！！！

T1 的使命就是来耗时间的，考察选手代码能力。即选择较优的写法，以缩短时间。。。比如说二分和小范围的预处理就很好。狂码 200 行的选手如我，不崩谁崩？

$Code$

$T2. 动物园$

呵，最后 5 min 发现数据范围 $0 \leq k \leq 64$… 再见，这美丽的世界。

于是比去年更烦了一重：要判 = 64 和 65 的，65 就是先减后加。

$Code$

$T3. 函数调用$

被 T1 烦到了，思路完全乱掉，归根结底还是心理素质太差了！

这题只是简单的加法乘法原理题，只要注意到贡献都是以加为根本，以乘为辅，大概就能想出来。最终答案的原先面目都是一些加操作啊。

于是考虑维护乘操作对加操作的影响，记一个后缀乘积就好了，拓扑看似难写实则好写。。。

$Code$

$T4. 贪吃蛇$

这题看似简单 实则不愧对其第四题的地位。。。思维严密，挺有意思的。

重要性质（与 16 年的蚯蚓十分相似）：

1
进食的蛇丢进另一个队列里，发现当前丢的一定是进食过的蛇里最弱的

猜想：如果当前 $max$ 吃了 $min$，不会变成 $min$，就一定会吃

1
证明：之后吃了的 max 会比当前吃完的 max 更小。

所以分为两个阶段：

  1. 当前 $max$ 吃了 $min$，不会变成 $min$，就一直吃
  2. 当前 $max$ 吃了 $min$，会变成 $min$，会一直进行下去直到某条蛇吃了不会变成 $min$ 或总数 $= 2$，这时最后吃的那条会反悔，倒数第二条吃的一定会吃，倒数第三条会反悔。。。发现和递归层数的奇偶性有关。感觉十分nb。
    $set$ 维护 $max$ & $min$，$O(Tnlogn)$，$70$ 分。

考虑优化，那必须 $O(n)$ 了

考虑双端队列

划一下题目中容易遗漏的条件：保证每组数据（包括所有修改完成后的）的 $a_i$ 以不降顺序排列。

——不用 $sort$ 了！

$q1$ 维护没吃过和没被吃过的，$q2$ 维护吃过的。显然都是有序的。

就是在暴力的基础上改一改

对于我这种没有🧠的选手来说，先写暴力才有可能优化成正解。。。而且暴力也更稳，考场上要尽力的打高分啊！

$Code$(暴力)

$Code$(正解)

$总结$

不要哀求，学会争取。感觉思维还是太慢了，细节又推不干净，接下来要训练思维的敏捷性，也要注重模拟赛的训练。

考场情况多，稳住。僵住的状态可以去窗口深呼吸，回来继续拼抢。