RainAir' blog

Blog

NOI2021 退役记

2021-07-31 16:50:22 By RainAir

Day -??

在南京跟着号爸那边集训,每天都被 所有人 吊打。

记得有一天的时候是复习 dp 专题,每道题都是 lyp 带我/流泪

模拟赛感觉打的也不怎么样,基本每天都是在奋斗尝试切掉 T1,而他们基本都在怒切 T2T3。

Day-?

由于台风的原因,余姚这边要求提前报到,但是到了的时候被告知因为去过南京(是的并不区分低风险和中高风险地区),所以不能进学校。

当时以为自己就要爆零退役了,后来成都的那边也一块来了,因为人比较多所以在余姚中学本部安排了一个隔离考场,不过这也就意味着我们和 NOI 除了考试以外的所有活动都没有关系了。

隔离考场是一个人一间卧室,一间卧室四张床两个桌子,除了饭是每次买的盒饭不好吃之外其他还不错。

下午做笔试,没想到考了一场真正的笔试(指用笔),由于排版问题没看到某个题目的正确答案差点选错/fn /fn /fn

考前为了保持状态一直在 vp ARC,恰好 Day0 晚上恰好有个 ARC,就直接上大号打了。这场最后切了个 E 打了 28 名获得了 3010 的 perf (不过 D 挂了很自闭)

当时就感觉我 Day1 要起飞了

Day 1

昨天打完 ARC 之后由于比较累很快就睡着了。Day 1 5:40 就醒了,由于余姚中学本部是老城区,下面已经快淹到一层了,幸亏加了沙袋才不至于让水淹到一楼(

所以一直没有人来送早饭,于是我先根据传统惯例开了一杯咖啡,喝完之后感觉整个人都饱了。之后他们那边说派军用车把我们接到备用考场,到了那边后发饭,不知道为啥是米饭和面食,直接生吃米饭咋吃的下啊(于是就啥都没吃。

进场之前感觉人都是慌的,想到去年自己不会 D1T1 导致打铁垫底自闭,还有之前的 hb 模拟赛经常做不出 T1 的经历让我感觉很慌。不过 lyp 给我说做题的时候不要思考比赛,所以我尝试让自己不要去乱想。

进场之后读了第一题,整个人都傻掉了:这不是 ZR 联赛模拟 T4 么?题目链接

虽然当时并没有确定这个题的来源,但是感觉就知道要重链剖分,然后线段树维护重链,轻边打时间标记来维护最后的边是啥。需要特判一下 lca 有两个边的情况。于是写了 2h 就写完了。

由于这个赛季挂分挂的都很严重(CSP,NOI,WC,省选),所以我抓紧写了个对拍,在 2h30min 左右的时候拍上了。

然后开 T2,由于之前没有见过偶-奇这样的东西,当时想了很多东西,发现我们如果知道了总数和答案,就可以解出偶数和奇数的个数,那题目为啥要求输出偶数方案数-奇数方案数呢?思考了一下发现求总数是求积和式,是 NP 的,所以看起来很不可做。对着这个想了半天,想到我要枚举一个排列,突然想到了一个可以快速枚举排列的工具:行列式!其实这个就等价于邻接矩阵的行列式,于是我快速写完了 $n_1=n_i$ 的 75 分,之后没有继续去猜结论很自闭。

开 T3 的时候只剩下 1h 了,首先 $n \leq 1000$ 很好做,然后树发现也很好做(只需要建立特殊点,bfs,并且容斥求若干次 lca 就好了),可惜最后都没调完,并且更自闭的是:这个原图缩 SCC 后就是个树,所以如果写完了树理论上我能 A 了这题!所以还是自己手速不够,T2 重新想花了太多时间比较自闭。

最后得分大概是 100 + 75 + 36 = 211,本来以为挺好的结果出来一问被吊打了,zjk 300,不过其他很多人好像因为 T2 的一些答疑的问题被坑掉了?感觉很惨。

后来发现好像 30+ 个 AK 的,感觉就很自闭,瞬间发现集训队离我远去,就自闭了 不过本来就没有集训队水平其实也没有那么自闭

下午查分前要拉去一块做核酸检测,这个做鼻拭子并且戳到最里面还转好几圈的感觉好酸爽,转的时候忍不住的咳嗽/自闭

下午查分前的时候,由于分会场需要传到主会场评测,所以延误了很长时间,在门口就很自闭,去年 D1,省选 D1 疯狂挂分的场景仿佛就在我面前复现。当工作人员宣布可以查分的时候,我飞速爬上楼梯,进去之后到达自己的机位输入密码差分,打开之后:

T1: Right Output! 100

T2: Right Output! & WA 75

T3: Right Output! & WA 36

一分没挂,这是我今年比赛第一次没挂分,感觉很感动。其他人好像因为 T2 的原因都考的很炸,就不好意思问了。

后来发现 T1 现场过了 250 个人,继续感叹 OI 界进步之快。

Day 1.5

社会活动在隔离考场不存在的,于是摸了一天鱼。

Day 2

由于 Day1 有 211 分了,据说 Day2 爆零也有银牌,于是我的目标就变成了保前 100 争金。

考前我又想起了去年 NOI D2 9 分的场景,感觉很自闭,并且我 D2 一般都是翻车的,就感觉没啥希望。

进场之后先看 T1,由于看到「随机」,一开始的想法是建 Trie 并且预处理子树来进行分块,不过复杂度看起来不对。思考了 1h 后毫无思路,1.5h 后毫无思路,这时候大家已经开始敲击键盘了,瞬间意识到自己处于了去年 D2 的情景。中间上了几次厕所强行要求自己冷静下来。之后以一种比较绝望的情绪来思考乱搞,由于随机,如果我们固定了 $k$ 位后,就只需要检查 $\frac{n}{2^k}$ 个数字了,初始时我想的是每次随机一些位置,要求这些位置强制相等,其他位置再去 check。发现这样每次成功概率大概是 $\frac{1}{2}$ 的,不过不太行,因为需要快速提取出某些位相同的所有数字不太会做。经过转化后发现由于一定有一个长度 $\geq 15$ 的不反转的区间,所以我就去枚举所有 $256$ 个区间并且 check,这个做法是很垃圾的空间也不行。

不过后来我突然想到,是不是只需要检查 $16$ 个互不相交的区间就好了?其实确实是可以的,因为最多会操作 $15$ 个位置,根据鸽巢原理,一定会有至少一个位置没有被操作,所以枚举后 check 就好了。复杂度就是 $O(\frac{qn}{2^16} \times 16)$ 之类的,但是被卡常了,看起来只能获得 88 分,

这时候已经过了 3h 了,感觉比较慌,所以开始写部分分。一开始以为 T2 是要输出分数取模后的结果感觉很神秘,后来发现要输出两个数 =-=,所以我就写出了一个答案的递推式,写了 50 分的暴力,由于时间不够没有去对拍(flag)

感觉 T2 正解应该是类似于平衡树使劲维护之类的,感觉没时间写了,就扔了去看 T3。发现 T3 $O(2^n \times poly(n,m))$ 是简单的,按照样例二提供的容斥思路模拟即可。在还剩 30min 的时候写完了这个容斥。之后去尝试卡了下 T1 的常数,然后强制让自己去检查 T1T2T3 为了防止挂分(但是没有进行静态查错这一步骤),当时看到自己得分只有 158 应该是急了,没有使劲去检查,比较失败。

最后打算写 T3 的性质 A,但是只剩 10min 了,于是就不敢乱动了。现在想想如果有时间的话性质 A,B 都是不难的。

出来就比较自闭,不过发现自己考的并不算差,他们都觉得今天 150 多大概是队线。

下午还是先做了自闭的核酸检测,然后查分的时候:

T1: Right Output! & TLE 88

T2: Right Output! & TLE & WA 30???

T3: Right Output! & TLE & WA 20

T2 为啥在第一个点 WA 了???

后来发现是我暴力的 sub 把 n 和 q 写反了,痛失 $20$,Day2 最终得分 88 + 30 + 20 = 138,自闭。

最终得分是 100 + 211 + 138 = 449,由于今年题目很水,只获得了 82 名的成绩。今年队线大概是 498,如果 D1T2 能及时扩展,D1T3 能调完树并扩展完到一半情况,D2T2 不挂分,D2T3 有时间写性质,上面任何东西完成几项都可以进集训队,不过感觉还是自己水平太低造成的吧,自闭了。

不过拿到了 82 名的成绩,顺利的拿到了银牌和(应该能换 thu 营一等奖),也算是有可能有学上了 虽然我感觉一年高考 620+ 还是不简单,暂时还是有了新的目标了吧。

我们明年 thu 见!

总结

截至 OI 主线截至前,各大 OJ 的 rating 和 practice 大致如下:

Codeforces: Grandmaster 2437, 1291 problems

Atcoder: 2280 2Dan, 189 problems

Codechef: 2000 5 star(不过好久不出 long challenge 了,怀疑是印度疫情的原因,我们怀念他)

Vjudge: 336 problems

UOJ: 38 problems

ROJ(平时模拟赛补题的 OJ):97 problems

Luogu: 632 problems

感觉自己不算特别卷的。。做题也不是很够

庆祝 ROJ 题数超过 100 🎉🎉🎉

2021-06-19 22:56:10 By RainAir

题目链接

但是截止发布时间,ROJ 的补题率竟然只有 $67.6470588\%$,简直是太鸽子了

不知道在退役前,ROJ 的题目能到多少呢?

我是Qingyu的粉丝

2021-06-16 22:01:52 By RainAir

[Deleted]

XXI OpenCup.ru: Grand Prix of Krakow

2021-05-17 18:44:08 By RainAir

The contest is over. Lets discuss problems.

How to solve H. Social Distancing and L. Patrol Drone ?

I have read editorial but get totally confused...

庆祝 ROJ 第 100 次提交!🎉🎉🎉

2021-04-01 11:45:36 By RainAir
RainAir Avatar