NOI2020 参赛记

2020-08-21 12:48:15


I. 前言

唉,最近身心都挺累的,但还是抓紧时间更一下吧。

刚好一个月前开始:

  • 7.21-7.27 听了七天的课

  • 7.28-8.6 打了七天的比赛

  • 8.2 大湾区信息学竞赛初赛

  • 8.2-8.3 生病(别怕,不是那个)

  • 8.5 WC2020

  • 8.7 与两位学长开茶话会

  • 8.11-8.12 UOJ NOI Round #4 (只打了一天)

  • 8.12 总算把 CF boboniu round 给办了(事实上我是白给)

  • 8.15 APIO2020

还是挺忙的,遗留了一堆的事情这段时间补。

一开始还是有点急躁的,毕竟还是挺有差距的。在和自己谈了数次人生之后,还是越来越能以平和的心态接受一切结果的。心态放正了,还是挺重要的吧。

  • 8.17-8.20 NOI2020 它来了

II. 时间轴

Day -1 8.16

第一次在疫情期间出远门,终点坐标长沙一中雨花新华都学校。好像算到得比较早的。

中午吃完饭想睡觉,但是门外极具穿透力的说话声没有停下过,躺了一两个小时,反而头痛了。

然后又去校园里闲逛,逛了不知道多久,把墙上的《商鞅徙木立信论》认真看了看。

晚上吃饭只记得出现了奇怪的菜。

吃完饭去见了高爸,在操场绕圈圈谈心。

晚上本来想什么都不做。后来高爸把我带到了自习室,看起来很不错,然后就去那里,看了看之前做过的题。

Day 0 8.17

正式开幕了。

开幕式上自然有轮番致辞,然后有几个简单的节目,显然还要好好帮贵校宣传一下,最后是各省选手展示和拍照。为响应国家号召,还立了一条新规矩:剩饭一次扣一分。orz

下午笔试。没记错的话居然只有 $76\%$ 的人拿到了满分。实际得分 $100$,略记。

然后试机,需要注意的大概就是:

  • 提交到下发文件(大样例)文件夹中,而不是建立 GD-09 再建子文件夹(似乎我省有大佬因为这个而没了,太可惜了);

  • 终端下可以使用命令 ulimit -s unlimited 将栈空间放大,我以前一直以为 Linux 下是默认无限栈。

试机题是去年 D1T2 D1T3 D2T3,都不是特别好写,就随便写了一些东西试了试机,然后和 pb 和 xy 交谈了一番,撤了。

没记错的话晚上又出现了奇怪的菜。之后再出现也不记了。

饭后和高爸绕圈圈谈心。

晚上去自习室写了一道工业多项式题,没写完,并且式子推得稍微复杂了一点,不过也算是小热身了。

Day 1 8.18

居然睡得如此之好。


  • T1: 有向图,从一个点出发,要求经过恰好 $T$ 时刻回到这个点(边权和恰好为 $T$),收益为经过的点(该时刻)点权的和。点权大多数情况下不变,只有 $k$ 个时刻,某个点点权会变,只在该时刻有效。求最大化收益。令边权为 $w_i$ 则 $n\le 50, k\le 200,T\le10^9,1\le w_i\le5$

  • T2: 一棵有根树,有 $m$ 条从上往下的路径,现在要求给边染成黑、白两种颜色,使得每条路径上至少有一条黑边。求方案数。 $n,m\le5\times 10^5$

  • T3: 给一个排列, $q$ 次询问 $[l,r]$ 区间内权值在 $[vl,vr]$ 之内的顺序对个数。 $n,q\le 10^5$

注意到 T1 有 $1\le w_i\le 5$,因此可以类似一个滚动数组来做一个简单 DP,显然是可以类似矩阵乘法优化的。 $k$ 次单点修改是强行进行 $k$ 次询问,倍增预处理矩阵就可以 $O((k+nW)n^2W^2\log T)$ 了。写出了几个错,调了一会,一个小时大概就弄完了这个题。

T2 显然容斥后方案数非常好算。一开始想了一些五花八门的假做法,发现都没有用上路径“从上往下”的性质。然后脑门子一拍,意识到可以从下往上子树 DP 优化这个容斥,状态记一下伸上去的链最长长度,以计算不受限制的边产生的贡献。启发式合并以及线段树合并都能够优化这个 DP,达到 $O(n\log^2 n)$ 或 $O(n\log n)$ 的复杂度。显然后者稳。

写得太快,还是写出了几个错,比如一不小心把一个 pushup 写成了 pushdown,然后一眼扫过去没看出来。然后就《生活在线段树上》,深入模拟了线段树合并的过程。调试搞了挺久,一度搞到 12:00,到后面还是有点急,但是这个做法还是相当稳,因此不可能放弃,只能鼓励自己坚持下去。12:00 过了一点,终于过拍了。

留给 T3 的时间不多了。前面已经写了一个裸暴力。“区间顺序对”显然是要根号做法。发现值域不限的部分分也十分无脑,然后飞快地拼了一个莫队套树状数组上去。这时候可能已经快结束了,还有一些部分分看起来挺不错的,但是写不完了。


期望 $100+100+40=240$。

实际 $100+100+40=240$。

前面 T2 调试用得时间有点长,导致 T3 时间不太够吃了点亏(u1s1,前两天 APIO 的得分和心路历程和当天惊人地相似)。不过并没有拉开过大的分差,因此更有理由保持平和的心态了。

于是就大概小结了一下当天表现。大概就是要更加注重效率准确性,并且要保持良好心态,尤其是不要思考后果,其有害无益。

晚上听讲。T3 居然是 lxl 哥哥出的第十三分块,与前面所讲“根号做法”契合。

当天排名大概在所有人中是 rk50。

Day 2 8.19

好像睡得还不错。


  • T1: 有 $n$ 种原料,各有一定质量 $d_i$,要求做出 $m$ 道质量为 $k$ 的菜,每种菜至多使用两种原料。求判定是否有解并构造方案。 $T\le 10, n\le 500,n-2\le m\le 5000,k\le 5000, \sum d_i=m\times k$

  • T2: 定义一棵无标号、区分左右儿子的二叉树(下同)的替换集合,为将其叶子替换成任意非空二叉树所构成的集合。求 $m$ 棵给定二叉树的替换集合的并的补集是否是有限大的。 $\sum n,\sum m\le 2\times 10^6$

  • T3: 给定一个弦图,求一条最短的从 $S$ 到 $T$ 的路径,使得删掉路径边后图仍然连通。 $n\le 5\times 10^5,m\le 10^6$

按照既定时长看了看题,并没有发现送分的题,并且此时看见有大佬在前面空地踱来踱去,直觉上这是一个阴间场(为什么没有提前意识到呢,今年还拿这套题选 IOI 国家队)。然后一是暗示自己,大家都觉得难,要放轻松;二是临时决定补一点时间去看题。

可能要非常感谢自己当时(有点天真地)暗示自己放轻松,导致后面心态不是很崩。

不过看题时间这一延长好像就不是很妙了,没记错的话看到了十点半。

感觉当时思路有点混乱。T1 猜了若干结论,试了一下好像都不太对。然后就在上述程序上稍加一点改变,变成了一个跑不满的暴搜, $n,m\le 4$ 的点怎么都能过,还想拿它冲一冲 $n,m\le 10$,甚至利用一些不为人知的性质冲一冲更多分。感觉这个做法不怎么样,并且还想后面有时间退退火(真的有吗?),我居然连 checker 都没写,肉眼检查了一下跑样例的输出,看着大概没什么问题(事实上大概很有问题)就没有管它了。(flag1)

后来我干了些什么呢?大概找出了一个判 T2 有限 / 无限的方法,并且还有一点零星的思路,终未成体系。然后看当前情况下又拿不到多少分,就暂时搁置起来了(一搁差点没拿起来)。

T3 根据特殊性质 B 的提示有了一点想法,并且还猜了些结论,能够从 B 推广一下。先写了一个 B 来保底,调了有点长的时间,最终意识到做法是假的。

忘了这个时候是几点钟了,也忘了接下来这段时间具体在干什么了。大概每道题都扫了扫,然后并没有特别显著的进展。

似乎是最后几分钟了,这才把 T2 $\max h\le2$ 的送的分给冲了一下。写完的时间是 12:59:37。(flag2)

T3 的 -1 都没交。


暴力没打满,大概二三十分的样子。当时就这么想。

下午半天不开门迎客,直觉上会鸽很久。碰到 wty 和 jxh 二位 AH 选手,大概和他们聊了会天,然后回寝休息了。一个比较烂的摊子,还要等半天,这种感觉……不作任何评价了吧。

宿舍里提前给爸爸妈妈打了电话,谈了谈心,他们也还是一如既往地鼓励和开导。

然后就出分了: $0+4+0=4$。

flag1: 有个地方无脑不小心写错了,并且 random_shuffle 之后编号没变。改对了居然 rush 过了 45pts。

flag2: $\max h=2$ 的情况手算错了一个点,一多测全没了。

如果只是暴力没有打满那还不讲,但是没有打满的暴力还大面积挂分还是让人无法接受。我对分数的保底还是一向保持着高度戒备的,却被如此重要的一场给击溃了。唉,具体分析看下一个板块吧。

晚上讲题。T2 是献给在新冠肺炎疫情中去世的数学家约翰·康威的,所以采用了类似《超现实数》的对话体描述题意,并且题目名称叫作《超现实树》。T3 是 myy 出的弦图性质神题。

放榜了。我就几乎是拿 Day 1 的分在肉搏,排正式选手中 rk125。今年的银牌放得好像更多一些,有 150 个。我能够接受任何合理的名次和奖牌,但是不能接受过于不合理的发挥,所以也算是留下了一点遗憾吧。

之后去找高爸绕圈圈谈心。第二天就各奔东南了,见一次不容易,就合了张影留念。高爸 Day 1 可能挂了点分,刚好跑到了 Au 线下一点点,也算是挺遗憾的吧。今后的日子里,不论是 OI 生涯还是更广义地说,机会都是很多的,前途皆不可估量,还要一起努力呀!对其他 OIers 来说亦是如此,就顺便也隔空喊个话,希望共勉吧。(后面好像会复读一次)

后来又和爸爸妈妈视频通话,聊了一个多小时,感性理性地把自己的想法畅谈了一番。

夜色如水。突然感觉这次来就好像一场梦一样,好像才开始就不得不画上句号了。又突然有一种对时空浩瀚的怅惘。怅寥廓,问苍茫大地,谁主沉浮,谁主悲欢离合阴晴圆缺?

唉,又来了,心思过于细腻了……

洗完澡,突然接到通知去了解一下换约的情况。一句话概括就是一番折腾,不仔细写了。

Day 3 8.20

早上听六人论文答辩,有幸坐到了飞机位,答辩内容不是特别难,但节奏就像赶火车。选手表现我不应作过多评价,但是看起来评委几乎看不懂其中的内容。

然后就闭幕式了。至少有 Ag 保底,基本任务还是达成的,还是上台挂了一块牌(为什么非正式选手只有 Au 线上才能上台?这不公平……)。赛事回顾剪辑成功入镜 0.5 次。接下来又有几个节目。

小小的琉璃球 渴望变做星星 往天空一跳一跳 总是掉下来……

明年 NOI 是余姚中学办。因为对自己不服,所以还要来。

回家了回家了。高铁上碰到广州二中大军。

体重掉了四斤,平均一天一斤。

(怎么这就写了 7K+ 了)

III. 后记:总结与展望

总体看,今年的题还是出得挺不错的,ideas 挺有意思,区分度还算比较好……至于我当场有没有降智,等我歇几天之后再重新好好看看题就知道了,到时可能会再更一下。


upd:

  • D2T1 突破口显然是 $m=n-1$。当场实际没有完全按照出题人的提示意图走下去,走偏了一点,即直接去想和图的关系。如果转而去想归纳得出一定有解,后面就差不多通了。得要更加果断地放弃一个走不通的思路,这种导向需要长期训练来更好把持。

  • D2T2 的 key observation 就是可以只考虑“树枝”形态的树,因为有限棵树枝不能替换出来可以意味着只有有限的树不能替换出来。有了这个就比较好做了,可以考虑给树枝进行一个简单编码。高爸和我不约而同地编出了一个四进制 Trie 上子树覆盖的做法,可以很轻松地做到线性,发现题解讲来讲去都绕过了这个好方法,是我看走眼了?总之这个树枝的转化还是挺巧妙的,是一道思维难度很不错、思维和实现难度都不过高的题。

  • 感觉自己要争取当场把这两题给干了才行。实际上按照当场的状态和当前的水平,还是挺悬的,既有偶然,也应该有必然。这就是差距吧。整体上思维能力还是不够高,需要着重去加强锻炼。


整体分析这次的表现,其实还是越来越有经验和感觉了。

Day 1 咬得算比较死,不过最后一题的时间上、能力上,还是有差距的。

  • 一是前面的时间需要压得更紧一些;

  • 二是要提升在时间和精力条件不充分的情况下的整体能力,以更自如地面对各种极端不利的情形;

  • 三是提高严谨性和准确性,这个问题常常会与效率问题相互作用。

Day 2 还是挺疼的,暴力没有打满的情况下还挂了一大片,算是比较严重的战略失误。不过原谅自己也是一种智慧,更多要看其教训。

  • 一是策略变形了,临时改变策略一定要谨慎,因为身在其中,很容易片面地作出判断;

  • 二是恋战不甘心撤退,可能和第一点有关系,依旧是站在局部的角度,容易作出与顾全大局相悖的草率选择;

  • 还有其他可能的情况是降智和到最后乱了手脚,它们以及其他因素之间相互作用,形成了非常复杂的输出表现;

  • 其实这天的心态还是不错的,精力主要都集中于比赛拿到更多的分,并没有因为情绪问题分散很多精力。

总之还是要更加注重把顾全大局,动态地、启发式地决策落到实处,落到实处不仅要认识到其重要性,还要意识到并摒弃一切可能阻碍实施的因素(例如太贪心了就想去搞正解的这种想法)。还是感谢有这个机会揭一揭自己的伤疤,它一定会让我印象极其深刻。

过去的一年,把“百业待兴”的自己拉到了差不多的水平,后半年则在此基础上尝试着以更开阔的视野增强各方面的实力。收获总体上还算是比较可观,还是要给自己注入一针强心剂。

命运并没有把我一巴掌拍死,虽然这次收官战打得并不是特别满意,但是仍然有机会按照自己的意愿继续坚持下去。下一个赛季,要以更加开放开明的态度精准施策与整体提升相结合,提升理论和实践的广度深度(尤其注重后者);要巩固前一阶段的学习成果;还有要注重从“大数据”综合分析自己和他人的优势和不足,以及对命题趋势的初步判断,等等;此外,还要加大力度培养一下创造性思维;在之前学习经验的基础上动态调整策略方式;尝试探索效率更高效果更好的 whk 学习模式,注意其与 OI 的互补与结合;再就是要更加注重并更加系统科学地打牢数理基础;最后是把锻炼身体放在更加重要的位置。

唉,又到了悲欢离合的时候。两个月前就已经发表过了长篇感慨,这里就不费大笔墨了。还是要说一次,不论您在 OI 道路上走得顺不顺,它都不是终点,而是起点,从这里出发,走向未来,前途不可估量。

借此机会来致个谢吧:

  • 感谢长沙一中及雨花新华都学校的热情招待,整个赛事从整体和细节中都能感受到付出的巨大心血。同时也感谢其他主办、承办、协办单位的协调配合,保驾护航。

  • 感谢高爸这几天愿意付出大量时间陪我,听我说并跟我说一些真心话(尽管我说的很多都是废话),实在难得可贵,以后还要继续共同进步呀。此外,也感谢其他在此次比赛中以及之前帮助我、鼓励我、陪伴我的 OIers 和 non-OIers,同样希望能够一起为各自或共同的理想奋斗。

  • 感谢学校,感谢严 sir 以及其他老师尽心尽力地鼓励、支持、帮助我这个特殊分子。

  • 感谢父母在竞赛上以及其他各个方面的润物细无声。

  • 感谢一个永不言弃的自己。

  • (感谢读者读到这一行,一不小心写长了)


dqa2020

2020.8.22