chenxinyang2006 的博客

chenxinyang2006 的博客

CSP-S 2020 游记

posted on 2020-10-16 17:42:43 | under 未分类 |

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

  • 初赛前的日子

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

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

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

  • 初赛前一天

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

    果然我还是个懒狗

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

    结果我复习的都没考

  • 初赛

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

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

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

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

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

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

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

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

    4. 经典的贪心,随便选选就做完了

    5. 万万没想到,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$,这样能拿个一等奖就不算白来

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

  • 复赛后一天

    去洛谷的民间数据测了一下

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

    T2 没特判, $95$

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

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

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

    T4 没啥好说, $55$

    顺便文渊电脑上跑 1s 的大样例洛谷上只要不到 100ms,我也是真的佛了

    文渊电脑属实 five 奥

  • 关于题目的评价

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

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

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

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

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

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

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

  • 11.16

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

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

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