THUSC2022 游记

· · 个人记录

发现打比赛一个特性，如果在赛后写游记，就不会特别寄！

upd：假的

更好的阅读体验

Day 0.5

试机赛。

T1 传统艺能 A+B。

T3 简单模拟，随便写了一下就 pp 了。

T2 大模拟，写完之后懒得调了，摆。

Day 1

传统场。

先看题，想了 20min。感觉会了 T1，T4，以及 T2 的 50 分，感觉稳稳。

写 T4，大概就树剖，整链维护一个哈希，链之间暴力取 X 个点做 kmp。发现细节多的一批，而且仔细想了一下只会 O(n\log^2 n)，感觉不优，就润了！

写 T1，发现读错题了！

写 T2 的 50 分，交上去发现爆蛋了！

真好。

开 T3，想了很久终于会了一个期望 O(\sqrt n) 的做法。

从 X 向外搜 dfs 树，令深度不超过 \sqrt n 的点为好点。关于好点的连边由深往浅连，其他的连边由左部点向右部点连。

那么随机取 \sqrt n 次点，每次让这个点暴力走出边，可以发现如果第二步走到了好点就可以暴力走到 X，否则再走最多一步一定走不下去了。

写了 114514 年终于过了本地数据，交上去就 WA+TLE，很带感！！！

此时只剩两个小时了。

重新读一遍 T1，发现直接倒着 dp，令 f_{i,j} 表示在位置 i，走了 j 分钟且还没下大雨，到终点淋的最少雨数，转移一步直接分讨会不会下大雨，随便拆式子算算就好了。（显然下大雨之后会走二类权值到终点的最短路）

写了一会儿，pp 了。

补了一手 T4 的 20 分暴力，修好了 T2 的 50 分暴力，终于签到了，感动。

本地用链调了一下 T3，调了很久终于过了自己手搓的随机数据。

只剩 20min 了，冲了一个 T4 的 X=1 就睡觉了。

下考几分钟终于测完了我的 T3，T 成 24 咯！

被暴力老哥吊打，哈哈。

没有人均分，明天怎么翻？？？？？？？？？？？？？？？？？？

pretest：100+50+24+30=204。

Day 2

工程场。

看了一眼题感觉都很传统，决定顺序开题。

T1 很快就写完了，死活都调不过第三个 pretest，到 1h 的时候就润了。

T2 感觉简单很多，随便写了一下就过了。

T3 看上去也是一个简单的模拟，写完之后死活调不出第二个 pretest，skip。

T4 是一个更简单的模拟，随便写一下就过了。

T5 看上去有点恶心，仔细读了一遍差不多明白了。算熵的时候有个地方写错了，最后 20min 才调出来。

然后调了调 T1 和 T3 都没过，寄。

pretest：12+17+14.25+22+26=91.25。

Day INF

领了张废纸，不懂，这都有优秀？