萌萌猫咪,不怕困难

· · 生活·游记

Day -?

在只完成了一科学考的前提下,因为太懒,我仍然选择推掉了学考去上海进行集训。

在集训期间,我感觉自己在渐渐对 OI 失去热情。在模拟赛里经常先做喜欢的计数题。所幸模拟赛里的计数很多都是区分题,也有不少牛鬼蛇神的东西。所以做出来之后排名倒也不差。不过这也让我对自己的水平认知彻底乱了。

在这段时间里,最开心的事情就要数某天晚上打 ucup 了。我和队友都封榜后压线过题,纵使排名没有特别好,也是很激动人心了。

我一直觉得 acm 会比 oi 压力小一些,毕竟自己不会的题可以推给队友,推了一圈都不会就直接开别的题去了,队友还可以在比赛期间给你提供情绪价值。不过也可能是我纯打着玩的心态导致的,真实的 acm 或许并非如此。

在模拟赛之间,我还要学习星火计划安全攻防的预习材料。所幸 lhf 报的也是安全攻防,一块学起来效率高很多,不过还是赶不上其他的那些卷王。

到了集训的倒数第二场模拟赛,我鬼使神差通过了一道无敌魔怔题,这让我感觉自己还是有一定实力的。

最后一场模拟赛我直接摆了,看 T2 是 wtf 题还以为根本没人过,结果一下过了 7 个,小正太更是觉得这是信心场,直接给我整不会了。

不过作为去年的集训队,今年就算爆了也只是不能进入国家队而已,所以我的心态也没有很差。不过感觉自己能否再次进入集训队确实完全听天由命。

然而教练还在奶我进入 noi 前十,我感到十分幽默。

Day 0

报道日那天联考直接从上海包两辆大巴车开到了绍兴,中途在一个看着很豪华的服务区停了车。

停车过程中我偷偷溜去 kfc 买了个汉堡,结果差点没赶上车。

今年换徽章的热情不及去年,大概是随机找了几个认识或不认识的人换了一下。

小正太订了 flammable dumpster 的徽章,给了我和 flama 一人十个去发。感觉 flama 的手绘徽章很萌。

Misty7 的徽章换完了,于是就用一个弹珠和我交换。

下午把卡了我一百万年的蔚蓝第九章最后一面过了,我已无敌。

最后背了一下笔试就去睡觉了。

Day 0.5

笔试前要排一个小时的队,感觉真无敌了。

在等待进场的时候发现了 lhf 和 cxy,我问国家队也要打笔试吗,cxy 表示他也不知道。

笔试没有挂分,然后把 noip t3 写了一下就摆了。

离场前发现了在开火车的众人,于是加入他们一块开,后来 lhf 也加入了,非常趣味。

晚上把 8b 也过了,感觉蔚蓝水平来到了前所未有的高度。oi 是啥,真不熟。

Day 1

早上起的太早了!!!

排队时间比起之前有所减短,气温也没有那么高了。

进场看 T1 发现这不是煞笔题吗,但是突然肚子一阵剧痛,只能先去厕所。

回来后在 0.5h 的时候通过了。

然后开 T2 T3,咋都是计数啊??

不论得分,至少打这场比赛会比较开心了。

然后一做 T2,发现可以划分成一些区间,每个区间合成一个数。

同时可以发现这个数的值是确定的,因为一次操作不会改变 \sum (-1)^ia_i。于是也可以确定这个数在的下标的奇偶性。

判断能否合成就是对每个位置求一直向右/向左最远能到的位置。

于是这样就能做第一问,开始思考怎么做第二问。

发现如果有两种划分方法都能得到相同的结果,一定存在第一种划分方法的一个严格细分还能得到这个结果。

因此我们再要求这个划分是极细的,具体只需要再考虑一下第一次减出来 0 的位置即可。

写完直接过了,此时时间是 1h。

于是我就有 4h 的时间做 t3,感觉不知天地为何物了。

然后 t3 发现自己根本什么都不会,直接玉玉症了。

想了一个多小时得到的唯一做法是维护子树内剩的结构的多叉树,然后暴力抵消。

这时我思考了一下 A 性质,感受到这个答案会和两侧有多少棵“相同的”子树有关,至于具体怎么有关以及“相同”是什么我都不知道。

我猜测相同是子树的可重集合相同,而套到整个题上可能是子树的随机异或和一样。

然后对着样例合理猜测试了几次发现是 2^{2n+i-|S|}S 是所有子树异或和的不可重集。

直接写有 56 分,只修改链上的点就是 80 分了。

此时大概是 3h,我感到很幽默。

为了给自己找点事干,我继续思考怎么优化。

考虑回归本源,把异或和看作长为 n 的二进制串,我发现第 i 次询问就是求每个串保留前 i 位之后判断有多少不同的串。

于是只需要给这些串排序然后求出 height 数组即可。

然后一个基于线段树合并和二分哈希的 2log 是显然的,并且我还见过那个优化成 1log 的主席树 sa trick。

已经无敌了。

于是我直接先写了 2log,发现直接通过了,只需要 2.5s 左右。同时我还发现把 sort 换成 stable_sort 会变慢的抽象事情。

我开始思考 1log 的细节,但是发现我的做法空间爆了。于是剩下的时间都在摆烂。

出场以后发现 AK 的人并不多,但是很多人有 280。好像 T3 有一个比较自然的 80 分做法,但是不太好继续优化。

查分没挂,但是发现自己 T1 其实没判 deg_1=0 的情况。感觉消耗了大量 rp。

很多认识的人也考的不错,flama 和小正太都是 280

晚上没有干什么特别的事情,但怎么明天还要早起啊!!!

Day 1.5

社会实践一如既往的如。

看球幕电影的时候感觉头很晕,差点就吐了。玩 mc 的时候也没这么晕 3d 啊。

晚上还是没干什么特别的事情,但是偶尔会思考自己 Day 2 爆炸会怎么办。不过爆了也就爆了,只能说明我就是没有什么实力。

Day 2

一走到座位就瞬间绷不住了。

我草,我怎么坐 flama 旁边?

看到我,flama 也直接绷不住了,但是并没有说什么。

最后一场正式 NOI 竟然发生了这种事,就连做梦都未曾设想过。

对我来说,坐在认识的人旁边可能算半个 debuff,因为我有时会不由自主地思考熟人的发挥。而当他就坐在我旁边时,我可能会潜意识里在意他的每一次敲击键盘。

我也担心我的行为会影响他的心态,所以我暗示自己这场比赛不要有太大的动作。

不过从事后来看,这个 Day 2 的幽默程度让我的担忧显得有些莫名其妙。

先看 T1,感觉有点难。

找了一会规律以后得到了一个线段树维护一百万个东西的做法,然后开始写。

大概在 1h- 通过了 T1。

然后开 T2,怎么还是集合幂级数?

这个世界怎么了。

直接对两个东西一块容斥看起来就很对,大概是 n^22^n 的,尝试写了一下。

写到一半发现想假了,然后开始重新推。

发现把容斥改对以后只需要 n2^n 的复杂度,需要用一下 |S|+|T|-|S\cup T|=|S\cap T|

看了一眼数据范围,发现处理 0 有高达 50 分,干什么?

思考了一下发现直接保留最低次项就是对的,因为计算 f_i 的时候只会用到 i 的子集的项,且 i 的子集的 0 的次数一定不比 i 更小。

然后直接写,写完调完直接过了。

此时大概是 2h 左右。

和 Day 1 是一样的剧本,此时我的总分已经有了 605,感觉输不了了。

于是开始比较激进的打法,先用半个小时做了下 t3 35 分就开始想正解。

发现根本不会优化,继续玉玉症。

玉玉症一个小时之后发现大样例答案相邻两项差很小,就改成了 40 分。

但是还是对正解毫无想法。

最后发现大概有一些和前缀最大值个数相关的做法,有通过串和修改都随机的询问的点的希望,然后就开始写。

写完发现只有十几分钟了,然后喜闻乐见地没调出来。

赛后问 flama 发现他也 240,也是没写完。

遇到 wtc 说他 T3 \log^2 没调完,感觉很惨。

在群里看到大手子说自己是 100+40+100,有点太变态了。

lhf 和 cxy 都觉得这个 t3 太答辩了,根本写不了。

晚上查分没有挂,感觉还是比较稳的。

小正太好像爆了,看来 flammable dumpster 终究不能一块进军国家队选拔了。

不过至少他去年已经保送了,祝他能在预科生活里也找到自己想干的事情。

篝火晚会有点抽象,有幸看到 flama 和小正太开了一局。

有好多人说我是并列 rk2,感觉有点魔幻了。

感觉今年 noi 出了就跟出了一样,基本没有什么区分度。我能获得 rk2 就足以说明一些问题了,不过 2.6 道计数也干了。

晚上躺在床上思考人生,感觉自己可能还不完全是路边。

Day 2.5

感觉文艺汇演的大家都太牛了,歌都非常好听!

晚上闭幕式颁奖改成了逐个颁奖,有点抽象。

站在台上,手里握着沉甸甸的奖杯,我终于确认了自己 rk2 的这个事实。

在台下坐着的选手里,我能看到许多熟悉的面孔。

这过去的一年里,我与许多未曾谋面的高手结识,也与其中一部分成为了朋友。这些都是我以前只能幻想的事情。

回想起来,在这条路上有许多人帮助了我很多,我最想感谢的人就是我的队友 flama 和小正太。从第一次组队到 thupc,再到这几乎每一场 ucup,我深切的感受到自己还是有人要的。感谢他们对我的帮助和接纳,没有他们肯定不会有今天的我。

另一个我很想感谢的人就是小青鱼,在我去年还几乎是个透明人的时候,青鱼出于一些机缘巧合认识了我并和我聊上了天。在她的帮助下,我认识了许多来路各异的网友并和他们混了个脸熟。

希望青鱼能早日战胜她面对的这些不公,蜕变成为一条大青龙!

嘛,肉麻的话先说到这里,接下来的路还很长。

祝可燃垃圾堆聚是一团火,散是满天星。期待能在 ucup finals 的赛场上,在这支队伍的最后一舞上再次见到大家!

国家队选拔就看着办吧,毕竟运气也是实力的一部分。不过肯定要先摆脱现在的舒适区,多做一些能让大脑升级的非传统题。