CSP-S2024 游记

· · 生活·游记

Day -3

到了机房想 [NOIP2016 提高组] 蚯蚓 这题。

绕机房走了几圈之后想出了一个假做法,遂实现之,然后就发现它假了。

看了题解之后觉得自己实在是退役水平的选手了。

Day -2

霜降。

今天进行了英语听口考试,然而我是当天背的课文。Open Question 感觉回答得稀烂。

考完之后大家心态都不太好,据说 A 卷转述很难?

Day -1

下午班会课在操场举行了极其抽象的英语活动,我几乎是全程摆烂。

跑操完了回班,发现班里一半人不见了,听说是去听讲座去了,于是慌乱地(并且拿着作业)也跟着去听讲座。

结果发现基本上就是一个清华大一的和一个北大大一的全程互黑对方学校的两节课。

Day 0

下午强基课,但是讲解了如何比较两个势相同的无穷集大小,感觉非常非常非常不严谨,但又能怎么样呢。

去了食堂才发现只剩下买两个饼吃吃的时间,于是买了两个饼吃了吃。

到了机房,并没有开始复习板子,反而开始了水谷。

后来开了一道廊桥分配,转悠了一会想出来了,但是偶然发现有人在玩三国杀。

最后意识到了该复习模板了,于是开了【模板】线段树 2。

然而总所周知,我的复习效率与机房里的人数成反比,尤其是在机房里有一只咋咋呼呼的 sbno333 的时候。

导致直接写到下课都没写完,遗憾离场。

晚上到家之后颓废了很久,什么也没有学。

Day 0.5

早上好!又是睡到了九点才醒的一天呢。

发现昨天没调出来的线段树是因为没开 long long。果然太久没碰 OI 的话这种事也会忘记啊。

接着写了快速幂(指数和底数搞反),欧拉筛(从 1 开始筛),dijkstra(单向边连成双向边),感觉没救了。

想复习一下 tarjan,但是脑子一团浆糊看不懂。

于是决定在路上看一眼,但是事实上又变成去颓废了。

最后进教学楼前狠狠地抱了一波佛脚,快速学习了 tarjan、点双和边双。

因为穿初中校服所以考前还被问是 C21 还是 C24 了......

Day 1

这次的环境真的是一眼虚拟机。好在 VirtualBox 我知道怎么调全屏。

考场大屏上写了解压密码,然而下发文件根本就不需要解压密码,我也不知道是什么情况。

观察样例,然后记事本卡死了。

于是不管样例了,去配置了一下 geany。

然后就到开题时间了。

T1 看了一眼然后秒了。但是处于对提高组 T1 应有的尊敬,我仍然反复思考了我这个算法的正确性。结果发现确实是秒了。遂实现之,一遍跑通所有样例。一共用了大概不到十五分钟。(其实紧确界应该就是十分钟)

开 T2,帮助我复习物理期中考,这是好的。依照我曾经的物竞教练的教导,我分类讨论并画出来了 v-t 图。

然后就是,还是,秒了。大约半个小时后过了所有样例。

开 T3,看起来比较神秘,于是觉得还是先看看 T4 吧。

开 T4,这个看起来非常的可做啊,首先 AB 两个性质怎么做是显然的,然后就是考虑怎么做 O(n^2) 的点。稍作思考之后决定不管询问了,直接挨个往里面加元素,把每个数量的答案都挨个算出来。然后就意识到每次加元素其实只影响树里最右侧 O(\log n) 个点的答案(擂台赛胜者),然后依照题意模拟,维护左边哪些点可能会获胜,右边补进来的点从哪一点开始可能获胜就就行了。我写的时候直接懒了,用了 set 维护,因为显然这玩意非常不好调,跟个大模拟似的。

果然他的确很不好调,大概从开始想这题到过大样例用了接近三个小时。中间真的非常慌,很怕自己假了或者调不出来。

写完之后有两个选择,写 T3 的 20 分纯暴力+优化 T4 的复杂度,或者想办法写写 T3 的部分分。

我感觉 T4 优化了也顶多多 8 分,于是选择了后者。但是回去想 T3 发现根本没有思路,而且现在即使想出来也肯定来不及写了,于是赶紧写了那 20 分纯暴力,跑路去优化 T4 了。

此时只剩 15 分钟,我首先试图在不用 ds 的前提下优化,因为我觉得这点时间我必然写不出来任何数据结构,但发现好像不得不用。于是就变成了生死时速之十分钟能写出一颗权值线段树吗。显然并没有写出来,然后考试结束了。

最后在心里算了一下复杂度,\log n\times\log n\times\log n......好像过不了啊......

Day 1.5

发现考场老师是我曾经的竞赛教练于是打了个招呼......其实有点怀旧的说。

下楼的时候又想了想复杂度,发现好像可以势能分析,于是复杂度其实是 \Theta(Tn\log^2 n),好像能得 68 分,赢赢赢。

遇上其他同学了,本来前两题过了有点小骄傲的,但是很快就清醒地认识到这根本就是场切题,一等线肯定是 200 往上了。

后来知乎刷到了 如何评价 CSP-J/S 2024 第二轮?,以为自己掌握了 T4 正解于是一顿乱糟糟的输出。然后被人提醒这题是黑题才赶紧到洛谷上看了一眼,发现 \Theta(Tn\log n) 既过不了也优化不了,自己成小丑了,于是连忙把回答删了自闭去了。

晚上发现有程序公示了,于是赶忙下下来解压,然后怎么着都解压不了,哦,原来是被加密了啊。

总之就是破防破防破防。

Day 2

早上起来决定复兴拜占庭,但是玩到一半奥斯曼跟俄罗斯签了共防,于是寄了。

拿到了赛时代码,据说是强行破解的,这里感谢学长。上洛谷测了一下,100+100+20+76=296,感觉还可以,但是不排除人均 300 的可能性。而且我也不知道为什么能 T4 能拿到 O(n\log n) 的分。

然后和初中同学联机开了个别的档,玩了一会就去吃饭了。

吃完饭理完发照完相洗完澡就开始写游记写到现在。写的过程中发现云斗也有数据了,测了一下发现仍然是 100+100+20+76=296

先这样。其实写游记的主要原因是想投稿专栏。