NOI 2023 退役记

暴力出奇迹 · 2023-07-26 17:30:06 · 生活·游记

这回真退役了。

准考证号 AH-05。

7.14

UNR 笔试模拟，阿克了。

7.15

UNR Day 1，签到失败，30+10+20=60，垫底，下大分。

7.16

UNR Day 2，冲分段多项式+lagrange 插值，最终 50+20+30=100。竟然上分了 /kx。

喜报：两天加起来 Cu。

下午听了一个易错总结与策略。

7.17

省内活动日。

7.21

成都，启动！

ztq 坐我旁边，一开始差点没认出来 /jy。

高铁上凑了一上午的 时代的眼泪 暴力。

感觉要成为时代的眼泪了 /ng。

晚上吃了串串，不会要考串串了吧 /jk。

下午进校，去了宿舍，顺便换了徽章。

笔试，启动！

选手可以串寝吗？可以，但需要先提出书面申请，经领队、科学委员会主席签字确认。

代码长度限制是小于 100KB 还是不超过 100KB（

晚上打板子。

成都七中澡堂（打一省选题）：无处存储。

7.23

上午开幕式。

喜报：耳朵龙了！！1

音响好闪，拜谢音响。

下午笔试+试机赛。笔试考了好几个题库没有的题。试机赛是 noip2021，一开始编译没过，意识到必须放在相应文件夹下，写了 T1 和 T2 的 50pts 暴力就跑路了。

有 SelfEval 好评。（实际上减少挂分就不太能进队了，差评。）

吃过饭拿密码条，座位 A127，出题人不会是 127 吧 /jk。

回去继续打板子+颓废。

晚上 10:30 睡觉。

7.24 Day1

早上 6:30 起床，去恰了饭。

进考场，考前不能碰电脑。开场先敲文件操作吓唬人（

开 T1，很快就想到了做法，但是感觉 n \le 10^9 离散化细节有亿点多，不太好写，直接开始冲 95pts。到 9:00 冲完，挂上拍就跑了。

开始想 T2，n,m \le 4 就暴力枚举 fa 数组，暂时没写。猜 m=0 答案为 1，口胡了一个证明，看了下大样例是对的；继续猜 m=1 是 2n-1（要么当儿子，要么插入），看了下大样例又是对的；继续猜 m=2 是 4n^2-1，结果大样例的 k>0 不对，自闭了一小会，然后发现 k=0 是对的；根据大样例答案猜测少了 n-1，过了一会口胡了个证明，就把 m \le 2 冲完了。继续猜 n=1,k=0，本来胡了一个 O(n^3) dp 试图打表结果 WA 了，修不对了然后开始瞎猜，直接推广 m=2,k=0 然后就猜到了 (2m-1)!!，验证了一下是对的；继续推广到任意 n 就从 2n-1 开始乘 m 项，测了一下大样例又对了。所以找规律搞到了 60pts，先把这些写掉，暴力 10pts 先留着不打。

然后去冲 T3，\texttt{s-dfs} 树等价于非树边全为返祖边，立刻就有了 O(2^k \times poly(n,m)) 做法，36pts，先写完。继续冲一条链，胡了个 O(m) 然后假了 /ll，然后发现只能胡平方做法，冲完之后编译过不了？？？这时候还剩 1h 左右，心慌了，进行若干修改还不行，突然发现 dp 数组开了个 10^5 \times 10^5 /kx/kx/kx。修完之后又 WA 了，发现又错了，查半天查不出来。

只剩下 40min 了。还剩 T2 的 10pts 和 T3 的 8pts 没写完，很慌。决定先去冲 T2 暴力，还剩 30min 写完，然后输出全是 0，查了几个错再冷静一波输出中间结果，还剩 18min 调过去了。但是好像有点卡常，来不及测极限数据了。接着冲 T3 调试，手造了一组小数据发现暴力和 dp 对不上，输出中间结果发现方程一个细节写错了，最后 4min 冲过去了。

一出考场就听有人说 x_1>x_2，还以为保证了 x_1 \le x_2，经人提醒才意识到只有斜线保证了。。。这把要 Fe 了。。。

结果群里一车人都没判，希望不是 yyl（）

中午喝了橙汁，后来群里有人说考前喝果粒橙会获得巨量 \texttt{debuff}。

不管了，1kri 胡说，不信 1kri。

回寝室歇了一会，然后去查分，很好没卡，Day1 95+70+44=209，拜谢 Determinant 222pts /se/se/se。听说队线 200 左右，感觉有机会。

晚上浴室里一群“五音不全”的同学一起唱歌，唱到膜你抄的时候泪目了。

7.25

嘉年华提前了。去玩射箭脱靶两发，保龄球脱手两次，最后凑了那个眼疾手快，喜提三枚印章换了个纪念品。

音乐厅放电影，好像是波特总动员，不去了（

一个 k-d tree 调了一下午，结果是 init 函数写完没调用 /kx/kx。

晚上吃饭之前拿了密码条。回去写了 exkmp 和 lyndon 分解，PAM 和 SAM 不写了（

再奶一口明天有串串（

chengch（远程）：奶一口明天有个题叫 \texttt{determinant}，然后 Determinant 1min 切了进集 /se/se。

Determinant：如果叫这个名字就不会是线性代数了吧（

LitDarkness（？记不得是谁了）：如果题目名称是 string 那是不是串串题（

暴力出奇迹：随机串的 \texttt{parent tree} 树高是多少来着？如果字符集是 \{a,b\} 随机还能乱搞吗？

（喜报：详见 Day2 /kx/kx/kx）

7.26

Day2 进场，开题看到一个 string，感觉要寄。

仔细一看特殊性质 A 是 \{a,b\} 随机 /jk。

开场半小时轮流瞪 T1 和 T2，不会正解，先冲个 T3 的 O(Tn \times 3^n) 状压暴力，写完发现题目有两处读错了。

然后继续瞪 T1 还是不会，再冲个 T2 暴力，写了个后缀数组写错了三处，然后发现题面又读错了 /kx/kx/kx。

修完之后继续瞪 T1，想了半天还不会，甚至联想到了 k 短路。同时脑子抽了没想到平方做法，只会特殊性质和大概会 m 比较小（但是要写虚树 /tuu）。到 10:00 突然意识到 dist(x,y) 等于把所有边反过来的图的 dist(y,x)，然后把图反过来递推每个点到各个祖先的最短路径就行了。直接开冲，然后 10:30 冲过去了，写个 Floyd 挂个拍子就跑。

后面 T2 和 T3 一点不会，想了一会 w_i=1 一开始以为是线段树结构但是过不了大样例，突然反应过来不用状压集合，可以直接改成 O(n^3)，改了一下冲过大样例了。

然后就一点不会了 /ll/ll/ll，到结束也只有 100+36+30=166。

听说人均 200+，队线没戏了 /ll/ll/ll。

下午查分发现没挂，所以总共 5+100+209+166=480，队线听说 500 左右，寄。

咋还有一群人 T2 T3 乱搞过了巨大多分 /jk/jk。

吃完饭看群里说 Au 509pts，Ag 407pts，现在 OI 都卷成这样了吗 /jk/jk/jk。

上午选手演讲，csy 纯纯劝退吧。

《我一题一题过，打到了 Day2 rk1》

闭幕式发牌，《让我们用掌声恭喜所有获得铜牌的同学》

linshey /ll/ll/ll 话说我还换到 linshey 的徽章了 /ll/ll/ll

峰峰峰 /ll/ll/ll

哦喊到我了啊，那我上了。

恭喜 zak 捧杯！

然后有一项团体前八，AH 竟然进了（rk7），泪目。

dzd：题目难度很合理，没有选手爆零。

jtt：考察了诸多算法，比如搜索。（此处掌声雷动）

闭幕式结束的时候来了一句“明年重庆相见”，绷不住了，明年就要高考了。。。

数了一下还有几个徽章滞销，所以吃过饭约群友在宿舍楼门口换了。

喜报：xq 的徽章甩到含章楼的大门上面了。（不过最后弄下来了）

晚上省内同学组织唱歌，想想唱歌的同学除我之外基本都是高一，就没唱《退役的你》了。

狂歌竞夜，大概这就是青春吧。

继续在宿舍打 pvz，到 12：30 睡觉了。

7.28

五点多起床，坐大巴走了。

文化课，启动！/ll

喜报：火车下午三点半在荆州站卡住了 /kx/kx，玩台风玩的 /kx/kx

生涯回忆待补。

此生无悔入 OI！

update：挺喜欢才艺表演的那首《蜂鸟》。不确定歌词有没有写错。

我们到底在追求些什么

为何一直不断往前冲

捏出血的双手 忘了也能够

稍微退后

我们总是以为能够自由

回过头那世界却依旧

唉～ 爱它来的时候

紧握的拳头 别忘了捉

那个梦