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

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