OI Diary 05：NOIP2022 游记
顺流入大海，海不问我从何处来。
说起来也是第一次正式比赛吧，但期望比较低所以紧张感不强。
学的晚，只有高一高二两次参加 NOIP 的机会。居然不知不觉已经用掉了一次。
详细写一下游记吧。
Day -2
学校 OJ 测了个信心赛。大概就是 T1 模拟，T2 数学推导/找规律，T3 单调栈/笛卡尔树，T4 经典树的直径+并查集启发式合并(crc赛时说的普及算法居然是真的) 然后混了 个 $320pts$ 并且后面订正满了。
比较摆烂，发现早上比较困，于是模拟赛是先睡一会儿再打的。
下午整了点模拟退火做，然后学了下笛卡尔树，补了星战那题的正经哈希写法。
Day -1
上午来了个小模拟， $2$ 题我都不会并且没有大样例。hy233 讲评的树形背包是一个很强大的写法，我看不懂，于是最后也摆烂没补题。下午老师让打一打板子题然后说一说坑点，只能说大家的坑点都很共通了。希望 NOIP 不要犯各种错误。
晚上看到某个数竞题，然后突发奇想自己造了个题，写了 checker 挂到了洛谷上，看来考前就是除了复习什么都想做阿。
Day 0
下午要看考场了早上还有模拟赛？仔细看一眼好像是 $2$ 题水题。一题模拟一题 dp 还是原题。于是大家都愉快的 AK 了。crc 老师讲了几题字符串。我也跟着做了一题字符串 hash，然后学了一下 01trie 的板子(最长异或路径)。然后其他字符串算法不是很想学了，因为考纲里根本没有阿。
下午学校租了个大巴把 oier 带到 AHSFNU，今年福建高中考生都在这考好像。可惜没拍照片。
到五楼机房一去试机，键盘非常阴间，是键程非常短的薄膜键盘。然而好像一整个机房都是这种，但是我问了别的机房同学就不是，反正可以用就接受了。之前没选 NOI Linux，于是分到了这个机房。明年还是去有 Linux 虚拟机的吧。听说即使不用它，挂在后台，只要写完放进去测一遍样例也行。
可惜没有面基到人，因为我根本就不认识别校的人阿。而且社恐人看不清别校校服。只有 AHSFNU 的校服非常显眼。
在大巴上因为下雨嘛，窗户有水雾可以用手在上面画画。大家于是画了 $No\ String$， $No\ DP$， $No\ DS$，$\dots$ 氛围很好。
晚上回去八点多就穿着校服睡着了，属于是很累。没复习什么东西了。
Day 1
早上 $6:20$ 被叫起来，把材料证件都准备好，随便吃了点早饭就骑上车去学校了。前几天都有雨来着，但是当天就没有，挺好的。在学校租的车上还有人在卷蓝书，我有点晕乎乎的，睡太久了反而会有点困，又忘记带咖啡了。把手机拿出来，看了几眼自己 Blog 上的做题记录和模板，然后看窗外发呆了一会儿，小睡了一会儿。
大概 $8:10$ 到了机房，趴了一会儿，硬生生熬到了开考 $8:30$。
开题。T1 在稿纸上画了一下理清了题意。数据范围要写 $O(n^2)$ 没有一眼看出思路。T2 是个神仙构造题，SPJ 但没给 checker，挺无语。翻到 T3，总算出现了图论题，但是没什么思路，过。T4 题意显然，是个神仙数据结构题，估计纯暴力有 $8pts$，作为保底。
阅览完题面已经 $9:00$ 左右，回去思考 T1。这是赛前决定的保险策略，即至少把 T1 拿到满分。然后发现显然 F 型是 C 型的延伸，考虑对 C 的贡献乘上向下延伸的距离就是对 F 的贡献。然后发现 C 型的答案可以通过预处理向右延伸的距离得出。于是一个 $O(n^3)$ 的暴力就写出来了，如果数据随机就能 AC。不过决定还是继续优化到正解。想了一会儿发现直接做两个前缀和就够了，改完直接过了所有样例。测了一下多测清空，也没来得及测极限数据就去看 T2 了，因为此时已经 $10:20$ 了。
跑去上了个厕所，回来想 T2 构造。但是此时我开始急了，T1 写了太久，我想着暴力打不完怎么办。于是根本没保证有效思考时间，想了 $10$ 分钟就直接开写暴力了。写了个 $20pts$ 的 dfs，测了下对于那一档的数据跑得飞快就润了，大概是 $11:00$。
然后越到接近结束，心态越绷不住。先去写了 T4 的 $O(qn^2)$ $8pts$，然后思考那个排列的性质，考虑各种对答案的贡献方法，脑子里冒出各种古怪预处理想法。分块？莫队？然后花了 $15$ 分钟写了个 $O(n^2+q)$ 想拿 $20pts$，结果样例都跑不过。此时已经 $11:30$ 了，有点慌了，把 $8pts$ 的代码先复制到了提交的目录下。
然后有点饿了，开了个面包吃，重新思考 T2 的正解，想着留 $30$ 分钟给 T3 的暴力。然后思绪非常杂乱，没看到那个 $k=2n-2$ 的部分分，就对着题面瞎想，结果面包吃完了也没想出来。又去上了个厕所，这次被要求下楼，跑上跑下，接触了流通空气，稍微冷静了一点。
$12:10$，开始写 T3 的暴力。这时看到其实有树的部分分，有点像树形 dp，但是我不想思考了，只想赶快把暴力打完。然后一通乱敲 bfs，枚举每个军营的选法并判断之类的，此时不知为何非常紧张，因为这个暴力要是打对了或许能有省一。时间逼近结束，我只能逼迫自己往下写，然后测了样例，RE 了。改了几个地方，这下变成 WA 了。大脑开始空白，我闭了一会儿眼，思考今天做题的经历，让自己接受这一切，然后抱着放弃的心情记下了代码的字节数，估了分：$100+20+0+8=128pts$。$12:45$。看到有链的情况，应该能推出个 $O(1)$ 的式子。然后到结束前就一直在推，结果到最后也没推出来。最后 $3$ 分钟检查了一下提交的代码都能过编译，文件名也没写错，然后就离场了。
考后出来发现人均 $140+$，感觉自己有点小丑了。T2 有许多人都拿到了不错的部分分。听完他们讨论 T2 发现 $k=2n-2$ 非常好写，要是写了就有 $35pts$ 了，略可惜。T3 也有人拿到了不错的部分分，正解应该是缩点+树 dp，之后有空补一下。
还是有一点难过，回家的大巴上一直在看窗外。发现 OI 的正式比赛，实力其实不是影响拿分最大的因素，心态更重要。如果 T1 能写得快一点，没有犹豫呢？如果多留一点时间想 T2 的构造，是否能多拿 $15pts$ 甚至更多呢？如果 T3 的树或者链拿到了，是否能多拿 $20pts$ 甚至更多呢？如果 T4 写出了分块 + ST 表的优化暴力，是不是就能省一了呢？
现在只能爬回去学文化课了。
我非常非常希望，明年至少拿个省一。
这只是第一年学 OI。
我不会放弃的。
$\text{NOIP2023 rp++}$。
(离开 staff 前拍的照片)
以上。
12.14 更新
回来更新一下，首先分数确实是 $128pts$ 和估分一样没有挂，其次这个分数居然能够拿到省一，果然今年是彩票竞赛。。听闻许多大佬这次都挂分了，区分度真高阿不愧是你 CCF。
其实拿了省一之后还是很迷茫的，因为本来学 OI 的目标就是拿省一，然后侥幸擦线拿到了。刚入学重点班开会说什么有省一就不会被分班分出去，那时候我们几个 OIer 笑谈他说的是 CSP 还是 NOIP，然后我又说 NOIP 省一对我来说还是为时尚早了。。然而彩票竞赛。
但是在省内排名也很烂，离队线非常远，至少明年是不考虑进队了hh，只有高二一轮省选机会的话那不是概率约等于 $0$ 吗。。果然还是应该早点学是吗。（别刀了呜呜呜连数学老师都有关心我 NOIP 排名然后知道我太晚学的事。。）
然后其实理性来讲 NOIP 省一真的没用阿，比数竞省一含金量低很多，，理性来讲为了自招政策我是不是应该转去学数竞？？但是果然还是保持做自己热爱的事情就好，首先数竞基本学不会看不懂没学过，其次我绝对不想放弃自己这一年学的宝贵的东西（对我目前来说）。
作为一个高中生，或许不需要那么冷静。作出一个不理智的选择，可能会失去很多，但是只是成长过程中自然走进的岔路而已，要自己好好承担阿。
然后说说最近，文化课真的学不会，作业真的补不完，疫情新政策让心态不是很平缓，学校的上课进度又慢的离谱一直在新课……使得我以前的课没补又要学“很多”新的进来，，导致感觉上就是啥都没学会。。尤其化学和文科（化学是因为我们老师的上课风格太雷厉风行）。很迷茫，害怕自己学业成绩被薄纱，要好好调整。
然后被诱拐报了洛谷的省选计划 B 组（其实是我自己也想报）。跟着他尽量把知识点都学一学，作业尽量做。不过这周的作业就有一题我听了也不太知道咋写的emm总之不要太心急反正可以回放，健康为重！！！这周新知识有 CDQ 分治、整体二分，然后终于大概理解了 KMP 的实现（之前是背模板）。紫题自己一般是很难做出来，那么数量上涨就靠你了省选计划！
就写这么多吧，生活加油，OI 也加油。
- 上一篇 OI笔记 | 杂类模板
- 下一篇 OI笔记 | 2022.11 做题记录（四）
♥