NOIP2023 爆栈记
CarroT1212 · · 生活·游记
博主坐标 GD-SZ。
YH 当几年考场了？
Day -21
进 D 了。
教练说今年 NOIP 不一定在 YH，有可能到东莞松山湖那边去。
Day -15
好好好应该不用期中考了吼吼吼。
关于从开学到现在没有写过一次完整的作文。
下周五农业园秋游？不太想去。
Day -12
停课。
……为什么这次不停晚自习。
……为什么要比完赛之后用训练时间补期中考。
……为什么要去秋游。
Day -10
各种挂分。
回宿舍问了一下好像期中考很难。
寄了。
Day -9
点分治好离谱。
其实去秋个游也没什么大问题，只是补不了剩的一堆题比较难绷。
Day -8
秋游。
路过的盐田港大梅沙小梅沙比景区里好看多了。
好远。
好晒。
一群人拔河把对面拉飞起来了。
跟几个重量级的去划船结果一上去木筏差点沉了，于是本来八个人的船给我们四个人单独用了一轮。
但是导游非常善良，以至于被同学问出来是老⚪批。
啊要自己做饭？暴露家务水平的时候到了。
导游：你们今天中午吃什么？
同学：自热饭！
一盘菜做完端下去结果不知道是谁加油加水然后锅燃了。
于是除了第一盘之外的所有菜均混入了一定量的无机含碳物。
但是味道还是比学校食堂好不少的……
看看我们班另一桌摆着七八个菜感觉我们好弱。
看看隔壁班另一桌把烟囱烧了感觉我们好强。
累了不想挖红薯。
其实还是有点意思的，但是回去的时候等另一个班等了半小时出景区的时候被前车卡了半小时进福田的时候被晚高峰堵了半小时搞得比班里另一趟车晚了一个多小时，相当难受，体验不佳。
Day -6
感觉自 CSP 完被扔回去上文化课开始丢失的状态回来了些许。
Day -4
模拟赛因为强制在线写错丢失 10pts。
Day -3
YH 怎么又成考场啦？
一想到今年停课估计就剩最后几天就莫名悲伤。
Day -2
模拟赛打完发现广场上立起了 NOIP 招牌。
并且被教练拉过去当三脚架拍合照。
Day -1
距 NOIP2023 还剩 0 天！
打八个题的手速赛，喜挂三题，详见主页。
考前攒攒 rp 还是挺好的。
怎么又拍合照。
czk 反复祈祷 T2 蓝题 T3 DP T4 没部分分（？）。
睡得挺早。
感觉模拟赛都打得还可以，比赛状态应该会不错。
但是几场模拟赛都是在 T2 卡了半场比赛左右，虽然最后都写出来了但感觉不是一个好兆头。
6:45：被同学的闹钟唤醒。
7:30：准备出宿舍然后意识到身份证还在教室里，找同学紧急要了钥匙飞过去开锁拿回来了。跑一跑身体好。
7:40：用早饭把自己填满了。
8:00：去考场。
8:10：开始趴桌子。
8:27：RP++！
8:30：大样例给得很足的样子。
8:34：建好文件开题。
8:35：没有短题面。
8:40：T1 会了。扔到 Trie 上乱搞。场上感觉 sort 过不去。
8:50：T2 会了。把关系求出来然后按 2-SAT 套路乱搞。
8:55：T3 会 25 了。随便 DP。
9:00：T4 会 36 了。随便 DP。
好像还可以。但是大样例怎么基本全是特殊性质！
想了一下，觉得先把前两题切掉可以大幅改善继续推题的心态，于是直接开打。
9:05：等会，T1 直接上 Trie 是不是开不下啊？
哦不。
那就不得不请出我的链式前向星建 Trie 了！
9:30：过掉所有大样例。dict4 跑了 0.4s，感觉还可以。
10:15：T2 写丑了，非常艰难地过掉了前面三个样例。
然后比赛走向从这里开始不太对劲了。
10:16：T2 在最后一个数据范围拉满的大样例爆 RE。
以为是什么数组开小之类的神秘锅便多开了几倍空间，但照样 RE。
又以为是什么数组下标不小心混了一个负数之类的锅肉眼瞪了一下，没看出来。
于是调了一下看看在哪炸的。
在建边 2-SAT 用并查集维护 scc 的时候出事了。
这怎么挂，再看看。
10:31：一段艰难的调试之后发现：
是在并查集里面爆的？？？
我什么时候连并查集都能写挂了，怎么回事。
看起来这个点确实是用并查集要在最后一段建边的时候压缩掉很多祖先。
但是没有看出递归终止不掉之类的问题。
而且是在 find 了两万五千多层的时候突然挂掉，甚至下一个去的节点都已经枚举出来了。
那这怎么挂啊？
诶这会不会就是那个别人说的爆栈问题啊？
但是爆栈应该不会这么快就爆啊。
话说不是有个指令能开大栈空间然后防止此类问题出现啊？
-Wl -stack=536870912
怎么过不了编译啊喂！！！
10:55：怎么就剩两个小时了，先写后面暴力去吧。
11:18：过 T3 25。
然后发现做一点常数优化还可以飞过 35 分，赢。
11:30：过 T4 36。
这时犹豫了一下要不要把调 T2 的时间分一点出来想后面两题。
决定还是去搞 T2，因为没爆过栈，不敢现在就确定到底是不是本地问题。
而且前面挂着一个命运未卜的题去想后面还是比较影响状态的。
尝试重构出了并查集转直接建图跑 dfs 的做法，但是还是爆在了差不多的位置。
感觉很怪，于是把 dfs 部分单独拎出来测了一下看是不是被程序里的其它因素影响到了。
然后发现就算我只建一条 (i,i+1) 的链然后从 1 开始做一个裸 dfs，并在过程中记录每个点有没有被遍历过和此时的递归层数，它还是在两万五千层炸掉了！
确定了，本地评测问题。
但是大样例测不了还是挺难绷的，试试能不能卡进去。
尝试在简化版 dfs 上重构了链式前向星建边并似乎还是失败了。
那就不管了吧，就祈祷只是本地环境问题了。
这题怎么一个爆栈耗了我这么长时间……
12:25：去看 T3 T4。
没啥思路。
12:35：诶 T4 有个 B 性质，赶紧写掉。
12:40：过样例，赢。
12:57：交吧交吧。
预期 100+[?,100]+35+44=279。
12:59：但看样子大家都考得不错，十分感动。
zjh 也爆栈调一个多小时……
问了一下 291 的 czk 我为什么无限栈指令过不了编译。
啊啊啊啊啊啊 Wl 和 stack 中间有个逗号！！
输。
13:30：身份证从教室拿出来了结果书包还在里面，老师和拿钥匙的同学都不在，我有一个非常合适的理由不写周末作业了，赢。
17:30：小丑了。
T1 没判 n=1，挂 10 分，输。
T4 性质 B 完全忘记要判
但是 T1 这个大概率挂不掉，因为
16:20：云斗测得 100+100+35+36=271。
师兄 AK 了！
然后晚上 ABC 的时候键盘右 shift 和右键同时坏掉，不想打了。
Day 1
处于一个麻了的状态。
主要还是在机房泡了一个半月结果还是等到了回去搞 whk 的这一天就很难绷。
但是不久后得知过一段时间还会停课，立刻复活。
Day 2~6
先滚回去上一周 whk。
补期中考。
五个小时考六科，真是美妙。
Day 7
279。
T4 没？挂？
很符合我对 CCF 数据的想象。
至少比 S 高。
算是稳定发挥了……吗？
怎么说吧，没想到这辈子第一次被爆栈创死是在正赛里面，下次大概就知道了。
死磕爆栈的 T2 这个选择不能算错，主要还是因为缺乏应对爆栈的经验，场上不太能确定到底是不是本地问题。
但也间接地把后来才发现的 T4 性质 B 给差点带走了，同时也失去了想到
所幸最后并没有挂分，大概能卡进省 rk100。
再一次延续了 NOIP 在第二题卡半场比赛的传统。
不过今年 YH 喜提一个 AK 两个进队线三个 rk30-，可喜可贺。明年扛下 YH 排行榜的任务就包在我们身上了啊，任重道远。
祝各位下次比赛好运。