csp2019游记

CSP2019 游记

转眼就过了一年,去年看着高二学长的状态就感觉他们的心境会和当时的我完全不同,现在看来的确如此。在这样事关重大的赛季伊始,过去的种种都不影响了,现在一个失误就可能葬送全局1,即使平时自诩心态还行的我也在考前有些许担心。

Day 1

开场看到三道题后两道没大看懂怎么做,剩下 T1 试着在脑中回想一下格雷码的构造无果一看题意才发现直接给出了构造(然而要是考到构造明明见过却记不住,这也许是平时看书当做消遣却不认真记录的后果),直接写了个递归(有趣的是 SCOI2019 D1T1 也直接写了个递归以为可以过就没管了最终挂 50)想了下大概需要开 unsigned,然后一遍过了所有样例感觉还行但极限数据 $n=64,k=2^{64}-1$ 时却输出不正确,乱改一通没什么作用,把左移的一些东西预处理出来才过。(考后得知因为左移 64 位是 ub(undefined behavior) 所以可能挂,而且题面中还有一个 $95$ 分的部分分是专门给没开 unsigned 的选手,居然没有发现这个提示)

第二题主要问题是求以一个节点结尾的合法括号序列个数,这个感觉很熟悉但考场上只想到了要求个区间 min 的多带了个 $\log$ 的辣鸡做法,还很难写导致调了巨久。在 Windows 下开栈过了最后一个样例。(写完那个 min 的判断后直觉感觉可以再优化但数据范围已经可以过了就没管)

第三题一开始以为是简单题,试着猜结论例如一条链只能覆盖一遍或者一条边只能『传』两个东西到彼此的对面,感觉样例很强就打算先写再看能不能过样例,花很长时间写了一堆线段树的东西发现过 RE,调完 RE 后过不了样例一,调完样例一才发现算法是假的而且根本修不了(中途想到了直接按边拓扑排序但是又随手造了组数据卡掉了)在没确认算法可以通过所有小样例的情况下写题,这是策略的巨大失误(原因的话我想可能主要是去年 NOIP 的 D1T3 并不难,当时就是大概感觉从小到大排序或者从大到小排就行,先把代码写完最后来调,幸好最后十分钟调出来了)导致这次对难度的预估不够)(经验主义害人)(然而 CSP 和 NOIP 没有任何关系)又试着思考一下链和菊花的部分分发现都没有任何思路,要是知道思路细节多还可以慢慢调,但当时是完全连思路都没有,感觉需要特判的条件数不胜数,搞得整个人头晕脑胀。之后可能只剩一个小时了还没有测代码在 Linux 的编译是否通过,急匆匆 rush 了个 10 分暴力打开虚拟机,发现其他样例都能过就 T2 最后一个大样例不输出弹出一个: 『已杀死』?

我转念一想是不是没开栈?使用只有模糊记忆的命令 ulimit unlimited ,再测发现毫无作用,再凭借几乎没有的英语理解认为开栈空间就是开内存嘛,内存 = memory,所以打了一遍 ulimit -m unlimited 还是无用,当时心态就完全崩了,这 T3 一个高点的部分分没写 T2 还过不了?那不是当场退役?(主要还是去年 NOIP Day1 几乎人均 AK 导致对于 D1T3 的难度没有正确认识,以往几届 D1T3 并没有去年那么简单,然而我几乎没有系统做过往年题目又导致这个认识并没有解决)

最后半个小时各种乱改乱删,平时的代码整洁度都没有管了,只要能过!然而并没有任何作用,在 Windows 下开栈后完美运行的程序在 Linux 下就是跑不出来,写个中间过程的输出结果输出到一半就『已杀死』了,把一个调用求 min 的函数注释掉后就能跑完(这让我又确认了不是栈空间的问题,因为我凭感觉认为调用后的程序栈空间会和调用前完全一样,那么注释掉的那个函数一定是写成 ub 了。最后半小时的各种细节暂且不表,只记得最后看着各种增删填补的像扭曲污秽的打着各种补丁冒着黑烟滴着黑油的废土中的早已不能入眼的程序仍然只返回一个冰冷的『已杀死』时就像是自身也被『已杀死』那样的内心浓烈的绝望与无力感以及之前被当做玩笑话说过无数次但它可能就要发生在自身上的颓丧的一句:

也许,我就要退役了。

(最后五分钟时监考人员来收草稿纸,然而我并没有交,感觉交了就像递交了战争中的投降协议完全放弃了一般,但是到结尾也没能调出来的那种感觉或许只有完全经历过的菜人才能理解吧。)

(最后出来 210 的人应该不少,还算守住了标准分)

(有班上的神妹 T3 AC T2写挂分还是比我高,实力差距啊)

(最后出来有人告诉我是 ulimit -s 因为栈空间是指栈 stack 和内存 memory 是两个东西。当时的想法可能有许多:如果我早知道这个或许最后半小时能多拿一个 T3 的部分分?我平时都用的 Linux 却把开栈的命令记错了?可能种种都有,最主要的只有希望它的确是因为这个的缘故被卡的)

Day 2

T1 看到题想到是容斥+背包(D2T1 考 998244353 ,真有你的),T3 部分分似乎很多,T2像是斜率优化。(顺带确认了下默认的虚拟机是没开栈的,昨天似乎确实是没开栈的问题)

中间过程暂且不提,最终 T1 写的太久 T2 先想到了个 $O(n^2)$ 感觉可以优化成 $O(n)$ 写完发现是假的过不了样例 3,写了个边界可能有误的 $O(n^2)$ 过不了任何一个样例,最后只能写个 $O(n^3)$ 匆忙跑路。T3 部分分有 75 比昨天 T3 良心多了就没去想正解(时间安排也只留了 75 分)(要是有足够的实力也就不会这样『限制自己』的时间了吧,也是以为 T2 比 T3 简单,但真正有实力的选手 T1 会几分钟内解决,T2 第一遍 $O(n)$ 就可以直接过掉所有大样例,也不会存在没时间想 T3 正解的情况)写完后尝试改 T2 边界无果,最终老师又来收草稿纸选择了交出去,像是认同了事先预料到的这样的结果一样,大致检查了下文件就到时间了。模拟考许多人会的题不会,正式考试又能『超常发挥』到哪去呢?

(出来的时候的确基本上同班的所有人都会 $O(n^2)$ ,又如 THUSC 一样掉在了没拿满标准分的坑里,不过实力比不过也确实是只有认栽吧)

(写这篇不知道在写什么的东西时候有的班上同学已经改完了今天的题,我却半点没动,实力啊)

总结:

目前为止成绩没出,在班上各种民间数据是处于倒三的状态,至少应该能去 THUWC ,NOIWC 不清楚不过不是重点,至少希望接下来几个月能提高点实力


1. ——LOL 英雄卡莎

写到这忽然想写一些一直想写的毫无作用的碎碎念,(如果这次退役了以后就没机会写了)对游戏有 PTSD 的可以关掉了:其实一直以来有个感觉就是 OI 和电子竞技有着许多类似之处(比如都是用电脑打比赛?),(比如CSP 考前一个月正好是 LOL S9 全球总决赛)。今年最终夺冠的是一支赛前人气并不是很高的来自中国赛区的战队,但比起这支战队来说,另两只中国赛区的战队『似乎』队内都有着更强的选手,但却都没有走到最后的领奖台上,个人认为主要是因为他们都或多或少有着某个致命的缺陷或短板,能看出来的是只有最强的一个人可能不能带领全队走向胜利,但有着默契协同和完美配合的五个人可能加起来会产生远远大于五的效果(并且这支队伍还有一个完美的节奏发动机)。感觉就和 OI 中各个板块类似,一个人只精通某些类型但比赛可能完全不考那类题,就会陷入毫无用武之地,你需要至少能做出每个版块的中档位置的题最好还有一个精通的版块才有希望考出理想的成绩。

另一个方面来看是:能走到全球总决赛的舞台上的(至少纸面实力上)无一是弱旅,但正式比赛中却常有出现『不知道该怎么赢』,就是团战有来有回两边看上去还差不多,实际上两边的实力有着天壤之别,在暗中两者的经济差早已拉开,劣势的一方只是在像无头的苍蝇一样四处乱撞,一步步走向优势方的陷阱中最终被一波击溃。这或许和平时模拟赛大家都看上去考的都差不多,背后的实力差别却可能早已产生,像是温水煮青蛙一样,可能最终的一次重要考试在『打醒』某些人时就会一并将其『打死』了。(目前看来我可能还没有陷入被『打死』这个境地,顶多是一次『打醒』吧)