HAOI 2023 游记

想了想还是写个游记。

Day1

noip 队线外一名，前一天晚上不出意料地失眠了，三点多还没睡着。其实是因为 PYD1 在旁边制造噪音，然后我睡不着就一直在刷手机。

可能是守夜次数比较多，早上起来并没有很困。

8:30 先看了 t1。第一思路是线段树优化建图，感觉很神秘，d1t1 怎么会放这种东西。

然后决定冷静一下，先看 t2t3。t3 好像有点思路，但是 t2 看完一点思路没有，直接先写了 \(O((n+m)2^m)\) 的暴力。过了小样例发现大样例一个都测不了就没管了。

还是想测一下 \(m=30\) 能不能过，于是让电脑在那跑着然后去了趟厕所冷静一下。想了一下发现 t1 只需要扩展那个区间，也会了 t3 \(O(n^2m)\) 每次暴力 DP 的做法，并且有一个反悔贪心的想法，回来发现 t2 还没跑完就关了。

然后开写 t1，发现扩展区间的做法还需要写一个线段树。冷静了一下发现只需要维护当前扫到那里就可以保证每个区间只扩展一次了。写完一发过了大样例，结果一拍 \(n=5\) 就拍挂了，心里吐槽了一下大样例强度。调调调最后在 10:20 左右才过拍。

这时候感觉很寄，不过我相信 srz 老师

mrsrz: 你就这样想

mrsrz: 别人都是菜逼

mrsrz: 你不会的别人也不会

我坚信别人这会肯定也刚写完 t1。然后看 t3，发现暴力 DP 只有 \(22\) 分，但是好写就先写了。10min 左右就写完过了大样例。

然后试着实现反悔贪心。非常怕假就先写了链的情况，发现能过大样例。当时比较开心，发现树的情况有合并两个堆这种操作。dsu on tree 当然是可行的，但是算了一下发现 \(n,m=2333\) 的时候 \(O(nm\log^2n)\) 有 6e8，为了求稳写了 \(O(nm\log V)\) 的线段树合并。

忘记写完线段树合并几点了，不过印象里是没什么时间了。发现虽然能过大样例，但是跑 \(n=10^5\) 要 15s 非常难绷。各种卡常都加上去了但是效果不大，然后才发现自己没关 fsanitizer 而且没开 O2。关掉 -fsanitize=undefined 开 O2 之后跑了 2s 就没关了。匆忙把 DP 和反悔贪心拍了一下发现拍过了，但是这会已经开始发密码条了。

去 t2 想了想好像会了 \(25\) 分做法，但是感觉二十多分钟写不完就没管了。最后几分钟手造了一组 t2 的样例发现挂了，感觉很急但是最后也不知道怎么挂的。

出场只有 \(148\)，一看怎么人均 \(173\)，感觉很寄。

下午测一下发现好多人 t1 没拍也过了，感觉很神奇。群里好像不少人切 t2 了，一看我认识的人好像都比我高。一直在安慰自己 day1 没出到自己比较擅长的题，但是心里还是比较难受。

去同学那边用酒店大电视凹了会深渊，凹出来 \(6\) 颗星开摆。然后回酒店和同学打 pvz，后来陆陆续续来了很多人，好像最多的时候有 \(9\) 个，包括 zhiyangfan CuiZhenHang Kongwx_qwq 等等。最后大概十一点左右睡了。

晚上 PYD 还是在制造噪音，不过我说服自己睡不着也不要看手机发现就睡着了。

Day2

回想了一下 Day1 感觉自己 t3 太浪费时间了，其实应该直接冲一个反悔贪心，写了太多暴力和对拍结果没时间了。

看文件名怎么有个 game 啊，不会出博弈论吧急急急

先看 zu，发现 \(n\le 10\) 状态数只有 \(n^6\) 种，然后想起来之前的 ABC261H 感觉很相似。后来发现只需要知道一个奇偶性之类的东西就完全一致了，当时感觉奇偶性这一步太妙了，自己简直是最强大脑，非常高兴。

然后写一会发现可以做到线性但是 abc261h 要带 \(\log\) 顿时感觉很急，但是想了一会感觉没假就继续写了。过了大样例但是不会拍，又随了 \(30\) 组极限数据，因为 \(n,m\) 都不大就一个一个手玩对比。最后这么一通搞下来已经 10:30 了。

然后看 t2，感觉和我之前出的 Aimai Trip 有一点像，于是考虑把 Bob 那边连边建图然后分连通块考虑。发现每个连通块要边数不超过点数，那么只能是树和基环树。基环树的环外点都可以直接确定，那就只剩环和树了。

发现特殊性质 B 是一个大环，特殊性质 C 只需要做个 tree dp，特殊性质 D 给到了很好的提示，我很快转化成了只有 \(|S_i|=1\) 或者 \(S_i=T_i\) 的情形。然后环的情况就很显然了，树的情况还是不太会就先写了环。过了 AB 性质和暴力。

然后写 C 性质，很快就写完了但是过不去。这时候已经开始发密码条了，感觉很急但是一直不知道哪挂了。第二天发现自己环的情况只处理了环没管环外点不过这都是后话。最后也没调出来，看 t3 发现 \(10\) 分暴力也不是半小时能写出来的样子，到最后也没调出来 C 性质的暴力。

最后出场只有 \(100+40+0\)，问了一圈发现都没切 d2t1 感觉有点希望。

晚上就回学校了。

Day3

发现 Larunatrecy 好像挂了，自己似乎暂时是 HAOI rk1 但是 NOIP 太拉了。如果 Larunatrecy d2t1 d1t2 d1t3 云斗上 CE 的分都加上应该就比我高了。

去 LA 群里借了一个码风匹配，晚自习和 PYD 合作写了一个 python 匹配了一下省选和 NOIP 的代码，然后就能算榜了。发现 PYD 似乎是 HA rk2 太猛了。我因为 NOIP 太低，按 HAOI \(288\) 算只有 rk4。云斗上 d2t1 被卡常数了只有 \(85\)，小图灵上倒是过了，而且 d1t2 多送了我 \(5\) 分。

感觉还是好多没打出来，d1t2 的 \(25\) 和 d2t2 的 C 性质 \(12\) 分以及 d2t3 \(10\) 分如果场上稍微写一下就有 \(335\) 了。不过过去的都过去了就这样吧。

现在还不知道 d2t1 ccf 会给我多少，不过只要挂的不多应该就能进。我也不半场开香槟了。