一晃一年过去了，又是一年 CSP，可惜我并没有什么长进，所以有没有一等奖还真不好说

• 初赛前的日子

  学校我们这一届的其他 oier 在做初赛题，我因为去年做过了就没和他们一起。

  他们讲题的时候我看了几眼，发现我基本已经忘了基础知识了，顿时感觉很慌

  于是就一直很担心自己考不好

• 初赛前一天

  想着要好好准备初赛，然后打了一天游戏

  果然我还是个懒狗

  最后晚上的时候临时补习了一直没学的 Tarjan（因为担心初赛考这个然后我完全不会），然后复习了一下板子

  结果我复习的都没考

• 初赛

  单项选择题(1~15)做得挺顺利的，因为没啥奇怪的计数或者计算机基础知识、NOIP比赛相关题。最后一个香农我只有一个大概的印象了，不过还是选出来了。

  16. 我没看出求的是最大 or 和，不过靠着 hack 选项还是选出了所有结果

  17. 是快排 $O(n)$ 求 kth

      以前知道这个东西，但因为我是懒狗，所以一直想着直接用 nth_element() 混过去，没想到初赛考了。

      不过之前看过一点快排的思想，所以大概填出了选项。那四个选择题我基本都是靠着快排期望 $n \log n$，最坏 $n^2$ 水过去的

  18. 大概看懂了是一个旋转字符串之类的东西

      前两个选择题都很容易地选出来了，最后一个选择题我忘记了是对 $[0,m]$ 或者 $[m,len]$ 旋转，以为没有一个公共位置可以旋转，所以是 $O(n ^ 2)$ 的，就选了错。但虽然我想错了，还是选对了，属实运气好。

      两个 4 分选择题全错，还是我水平不太行

  19. 经典的贪心，随便选选就做完了

  20. 万万没想到，CCF 竟然考分块相关的题目了

      不过这个也不算是严格的分块，只是对前 $\dfrac{m}{2}$ 位和后 $\dfrac{m}{2}$ 位分开维护

      我之前做过类似的题目，所以比较容易地选完了所有选项

  考完后和小粉兔的答案对了一下，$86$ 分，应该是比较稳了

• 10.17

  官方初赛成绩貌似是 $88.5$，反正过初赛了，也无所谓了

• 复赛前

  赛前一直颓废，啥也不干的过程我也不太想说了

  总是不太明确自己到底应该干什么，就算下定决心写一道题也会因为自身的懒惰而放弃

  有时我会想，也许正是需要一次彻底的失败才能唤醒我罢

• 复赛日

  上午复习了几个后来没考到的板子，然后继续颓废

  真可谓无药可救

  直接说比赛罢

• 14:20

  发布了解压试题的密码

  大致看了一下T1和T2，发现T1是很难写的模拟，T2倒相对简单

  看了眼T3，感觉像这题，恰巧我看了这场比赛，算是运气不错？

• 14：30

  直接开始写T2

  T2感觉就维护一下每个二进制位是否有数出现过，然后对着每个限制去判一下，如果 $p_i$ 这个二进制位没有数有，那么 $p_i$ 这个位就不能为 $1$ 了，其余可以自由选

  设 $x$ 为自由选的位置，答案就是 $2 ^ x - n$

  本来感觉写起来比较麻烦，但是看到 $a_i,q_i$ 互不相同，那我其实就不太理解这个 $q_i$ 有啥用

  维护二进制位是否有数出现过就直接把所有 $a_i$ or 起来就好了

• 14：45

  开始写T1

  感觉这个T1极其恶臭，有两个特殊的东西要判：公元前与公元后的区别，有一段时间是空缺的

  如果直接做要分三类推公式，十分麻烦

  所以考虑人类智慧，直接把前两类情况打表掉，就只要判第三类了

  打表就是直接一天一天往上累加，十分方便

  但只有第三类情况公式也不好推

  所以我就想了个二分答案的年份，$[l,r]$ 年每年有多少天之和还是很好算的

  二分出年份以后，我直接把那个一天一天累加的代码复制过来来确定月份和日期

  于是这样大概写到了 15:30

  测大样例发现要跑 1s 多，但我决定等会再管

• 15：30

  开始看T3

  一开始想了个用 $v_i$ 表示调用第 $i$ 个函数会整体乘多少，$s_{i,j}$ 表示调用第 $i$ 个函数会给 $a_j$ 额外加上 $s_{i,j}$，然后用线段树合并的做法

  然后我很快发现复杂度是假的，这样只能20pts

  然后就开始往这题的做法上去想

  很容易发现函数调用的关系建成图会变成一张 DAG

  既然不能求出 $s_{i,j}$，而且这个题只有一次查询，是不是可以把修改堆到最后一起搞?

  事实证明这样是可以的

  首先可以发现一个事情，就是这个函数调用我们其实可以把它变成割裂的两个部分，一部分是序列集体乘，一部分是单点加

  对于每个函数求出给序列整体乘的值是很好算的，但是这个顺序性的调用会使得整体乘干扰到单点加

  我们先暂时忽略整体乘这个操作，只关心单点加

  于是我们可以考虑把这个图变成带权图

  调用 $u$ 可以看做（实际上在题目上也表示为），调用 $u$ 的每个连向的函数 $v$

  而调用 $u$ 与直接调用 $v$ 的区别在于，$u$ 在调用 $v$ 后还会调用一些函数 $k_0,k_1,k_2...$，它们会给这个序列整体乘上一个值

  那么实际上我们把这个乘上去的值标为边权，表示调用 $u$ 所造成的加法影响，相当于调用边权次 $v$ 的加法影响，这样就成功抵消了整体乘的影响

  然后我们来考虑最后的 $q$ 次调用函数

  我们先像原来一样消去顺序性影响

  接着调用一次 $f_i$，实际上就可以直接给 $f_i$ 的调用次数加 $1$

  最后我们 dfs 一次，求出每个函数一共调用了几次，然后先进行整体乘，再单点加就完事了

  woc，我当时怎么想出这么复杂的做法的

  大约 16：30 过了 T3 大样例，当时我真是极度兴奋

• 16：30

  开始给 T1 卡常，不然要 T1 50 了

  首先每次二分都是 $O(32)$（这个的记法不太严谨，不要在意啦）的，十分的慢

  而年份实际上我们可以拿 $\frac{x}{366}$ 来粗略估计一下

  这个估计大概只会差 $\frac{1}{365}$，也就是 $200000$ 左右

  ？真的吗？

  其实是 $2 \times 10 ^ 6$，但是我当时看错了

  因此我的二分边界也是错的，不知道要挂多少分

  而且这题的 test10 是保证答案在 $10 ^ 9$ 内，所以就算我没看错这个优化也是假的

  我是真的服了我自己了……

  当然之后把那个枚举每一天换成了枚举每个月，应该是稍微快了点

• 17：00

  经过了上面一波负优化，我开始看 T4 了

  当然是带着一种随便骗点分的形态做的，毕竟CSP-S 2019 的 D1T3 难度，懂的人都懂

  首先发现对于一个局面，权值最大的人只有两种选择：

  1. 砍最小的，进入 $n - 1$ 个人的局面

  2. 不砍，游戏结束

  那么选 $1$ 还是选 $2$，实际上就是看如果选 $1$ 自己会不会死，如果不死就选 $1$，否则选 $2$

  于是就有了一个 $O(2 ^ n \times n)$ 的做法，就是递归求解这些情况

  ……你确定复杂度是这个？

  仔细思考一下，你会发现其实对于一个局面，只需要再去求解 $n - 1$ 的情况，所以实际上是 $O(n ^ 2)$ 的，就是 $55$ 分

  当我意识到这个时，已经过去了 20min（菜）

  但是问题就来了，我写的是递归，而递归很浪费空间，跑 $2 \times 10 ^ 5$ 会 RE

  于是我就匆匆忙忙地去重写了一遍，隐约感觉好像可以优化到 $n \log n$，只要写一个可持久化线段树就行了

  但是我发觉这个不太好写，而且跑 $5 \times 10 ^ 5$ 未必能过，于是就重写循环式了

• 18：00

  调完了 $55$ 分代码，我去重新整理了一遍所有的代码

• 18：15

  万事具备，我就切到 T4 想正解去了

  首先实际上，每次返回的都是一直 1 然后在某时停下的一个局面

  我先是自己仔细思考了一下剩下 $i$ 个人时权值最大的人在 1 情况怎样才会挂掉

  假设 1 情况返回的是留下 $k$ 个人的局面，那么权值最大的人挂掉只可能在 $k$ 个人时这个人已经挂掉了

  那么实际上只要记录每个人在什么时候挂掉就行了，不用可持久化

  当我想到这里时，已经因为丢了 15 分而有些难过，但更刺激的还在后面

  我又仔细想了想，好像根本没有数据结构支持 $O(1)$ 插入，$O(1)$ 删除，$O(1)$ 查 $\min,\max$

  所以肯定要用题目的条件

  而一直没用过的条件是什么呢

  当然是那个初始顺序递增！

  仔细想想，就会发现每次 1 之后，产生的新数都会越来越小

  所以这个并不需要数据结构去维护，我们只需要开一个序列来维护产生的新数，然后看它们会不会成为最大值 / 最小值就行了

  因为这个新数越来越小的特性，所以直接拿队首和队尾去看看能不能做 $\min,\max$ 就行了

  而用上那个初始顺序递增的条件，不考虑新数的 $\min,\max$ 我们可以直接轻松维护

  于是这题就做完了

  当我想到这里时，距离考试结束还有 5min

  但这是真的吗？

  这个做法实际上是假的（

• 杂想

  想不到我一直混吃等死竟然没有栽在这次CSP

  一个平时很厉害的同学说他考得不好，不知道是不是高估了难度

  不过我这次也有点被高估难度搞了，本来 T4 是可以到 $70$ 的

  T1 其实有个更精确的估算方法，就是按照 $365.25$ 来估算这样，可惜我当时 ZZ 了

  T2 没特判 $n = 0,k = 64$ 的数据，如果卡这个估计又得挂分

  现在的估分：? + 95? + 100 + 55 = ?

  实际上如果发挥地再好一点的话，甚至是有机会AK的

  不过 T3 能想出来就已经是我的能力极限了，也不能强求罢

  希望最终分数能有 $300$，这样能拿个一等奖就不算白来

  当然如果没有的话，我倒是希望惨烈一点，让我从这颓废的生活中解脱出来

• 复赛后一天

  去betway必威体育官方的民间数据测了一下

  T1 不知道为啥是对的，AC了

  T2 没特判，$95$

  T3 一个地方没取模，$75$，实际分数是 ？？？，不过随机连的图是不会挂的，希望不要个个测试点菊花图

  不过冷静分析一下，一棵树的点，只含一或二操作的点，$c_i = 0$ 的点都是一定对的，加起来有 $60$ 分

  剩下的点，如果有一个点被至少十个点指向（期望挂掉的点数为 $20$），并且这个点连出两条边，那么就会挂掉，如果纯随机数据的话，大概可以再得 $10$ 分罢

  T4 没啥好说，$55$

  顺便文渊电脑上跑 1s 的大样例betway必威体育官方上只要不到 100ms，我也是真的佛了

  文渊电脑属实 five 奥

• 关于题目的评价

  感觉这场题目质量还行，但我 dp 呢？去年考了三题的 dp 呢?

  当然不考 dp 对我来说是大好事，这样就不会露出短板了

  T1 出个比较恶心的模拟题其实是无所谓的，也算是锻炼选手的代码能力

  T2 就是一个比较签到的题，不知道为啥在 T2 这个位置

  T3 是一个比较难的 DAG DP + 数论的题目，感觉还不错吧

  T4 是个套了博弈论壳子的一个奇妙 ds 题，可能看不出是套壳会丢很多分

  整体难度相较去年肯定是有下降的，这也导致许多选手因高估题目难度而考得不好

• 11.16

  官方数据是 $100 + 95 + 80 + 55 = 330$

  错解官方数据比民间数据分还高，CCF zun 有你的（

  顺便听说 T3 暴力 $70$，可以可以，真是一场区分度巨大的比赛

• 2020.12.2

  拿了个 7 级，也不知道有啥含金量可言

  想起去年拿了个蓝勾，还高兴地要死，觉得自己天下无敌地样子

  真是可笑。

（全文完）