一晃一年过去了,又是一年 CSP,可惜我并没有什么长进,所以有没有一等奖还真不好说
-
初赛前的日子
学校我们这一届的其他 oier 在做初赛题,我因为去年做过了就没和他们一起。
他们讲题的时候我看了几眼,发现我基本已经忘了基础知识了,顿时感觉很慌
于是就一直很担心自己考不好
-
初赛前一天
想着要好好准备初赛,然后打了一天游戏
果然我还是个懒狗
最后晚上的时候临时补习了一直没学的 Tarjan(因为担心初赛考这个然后我完全不会),然后复习了一下板子
结果我复习的都没考 -
初赛
单项选择题(1~15)做得挺顺利的,因为没啥奇怪的计数或者计算机基础知识、NOIP比赛相关题。最后一个香农我只有一个大概的印象了,不过还是选出来了。
-
我没看出求的是最大 or 和,不过靠着 hack 选项还是选出了所有结果
-
是快排 $O(n)$ 求 kth
以前知道这个东西,但因为我是懒狗,所以一直想着直接用
nth_element()
混过去,没想到初赛考了。不过之前看过一点快排的思想,所以大概填出了选项。那四个选择题我基本都是靠着快排期望 $n \log n$,最坏 $n^2$ 水过去的
-
大概看懂了是一个旋转字符串之类的东西
前两个选择题都很容易地选出来了,最后一个选择题我忘记了是对 $[0,m]$ 或者 $[m,len]$ 旋转,以为没有一个公共位置可以旋转,所以是 $O(n ^ 2)$ 的,就选了错。但虽然我想错了,还是选对了,属实运气好。
两个 4 分选择题全错,还是我水平不太行
-
经典的贪心,随便选选就做完了
-
万万没想到,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 难度,懂的人都懂
首先发现对于一个局面,权值最大的人只有两种选择:
-
砍最小的,进入 $n - 1$ 个人的局面
-
不砍,游戏结束
那么选 $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 级,也不知道有啥含金量可言
想起去年拿了个蓝勾,还高兴地要死,觉得自己天下无敌地样子
真是可笑。
(全文完)