HAOI 2023 游记

· · 个人记录

\text{Day -2}

复习了一些可能完全没用的东西。

\text{Day -1}

下午感觉有点头痛，害怕是甲流，不过好在晚上就不难受了。

试机的时候写了支配树和平衡树，\text{fhq-treap} 写了\text{20min}，感觉要完

\text{Day 1} 上午

\text{8.20}

先瞅了一眼大样例，发现有一道题有 \text{15} 个大样例，感觉很逆天。

\text{8:30}

看 \text{T1} ,一开始以为是线段树优化建图，又看了一遍题发现只要走被覆盖的位置就好了，然后差分打标记就好了，\text{3min} 写完然后测了大样例之后就跳了。

\text{8.30}

### $\text{9.00}

暴力显然就是一个费用流，然后也有一个比较经典的可并堆维护的模拟费用流，大概又 \text{48pts}，感觉挺多的就写了。

\text{9.30}

删除显然套个模拟费用流就好了，但是 \text{A}性质完全不知道怎么做，链感觉也很麻烦，只能想到一个每次暴力增广的做法，但是复杂度假的，感觉没分就没写。

### $\text{10.00}

写完测大样例发现不过，然后看了看题发现把v_i=1看成了 x_i=1。 然后发现就发现只能 ddp，但是很难写就回去看 \text{T2} 了。

\text{10.10}

写完暴力的 \text{25pts}，然后去想多项式做法，树的情况显然是一个连通块，然后就发现普通情况一定也对应 \text{DFS}树上一个连通块，那么 对于每个非树边，相当于是限制它在树上对应的路径上的边要么完全属于连通块，要么完全不属于。但是好像还是不好做，想了一些乱搞的做法，比如给每条边随一个权值，但是不仅正确性很炸裂，复杂度也很炸裂。

\text{11.20}

还想了想把一条路径拆成两条，但是很假。 去上了个厕所，然后突然意识到一个非常重要的性质， \text{DFS} 树没有返祖边，也就是说每条路径天然就是直上直下的。 画了画发现只要连通块的下边界和上边界没有被截断的路径就是合法的。 然后开始写，中途换了一个比较容易的写法，并且发现在 k=0 的时候只有 n^{\frac{1}{3}}个dp，因此说不定能过 2000.

\text{12.20}

写完过了小样例，但是大样例是 k=1 的，没办法只能又改成 k=1的 dp，好在也不难写，但是答案却完全不一样，调出了两个小错误之后还不对，心态炸了，读了好几遍也找不到问题。

\text{12.00}

检查了文件就交了。

\text{Day1} 下午

刚出考场发现 HA 并没有人后两题有高分，感觉还比较好。

然后在和 \texttt{Displace} 讨论的时候意识到一个严重的问题，我 \text{T1} 差分的时候是把区间差分到点上了，但是题目给的是要求每两个点之间都能联通，粗略算了一下能被卡到 \text{0pts}，但是感觉只有 \text{[1,2],[3,4]}这样的区间可以卡，只要不是特意构造就不会被卡太多分。

但是整体心情很炸裂，万一 \text{Day 2}很难或者很简单，万一真的被卡到了\text{0pts}，加上联赛也不是很有优势，有可能连省队都进不了。

很痛苦，完全做不下来，满脑子都是想的不好的结果。

真是可笑，从 \text{NOI D1T1}看错题，\text{noip T1}多测没清空，在到如今，真的是受了什么诅咒吧。

也是我自己应得得后果吧，如果去构造了几组小数据，如果 \text{T2} 能调出来，也许就不会是这样的后果吧。

很想大哭一场，但是觉得连大哭一场的心情都没有了。

去校园里走了走，很安静，一个人也没有。

路过操场，就去跑了 \text{2} 圈，也许是被身体的疲惫所占据了吧，反而心情没有那么难受了。

一个人也没有，和往常一样。

晚上不出所料的失眠了，一直在想为什么调不出来 \text{T2}。

重新捋了一下，意识到问题所在了，我找到的限制是路径的边不被覆盖，但是我却写成了路径上的点不被覆盖，也就是说，有一种特殊情况我没考虑到。

真是可笑，同一天两道题犯同样的错误，也很难找到第二个人了吧。

不断安慰自己， \text{Day 1} 没考 数论和字符串，这两个还是比较擅长的，说不定 \text{Day 2} 考了就能翻盘。

最终反正在 \text{12} 点之前睡着了。

\text{Day 2}

\text{8.20}

看了看大样例的名字，看见 \text{game}，心肺骤停，不会真的考博弈了吧。

同时也并没有期待的 string ，还有一个不知道是什么意思的 \text{zu}，感觉应该是和喵了个喵一样的逆天题。

感觉翻盘无望了。

\text{8.30}

可能翻的比较快，先看到的是第二题，果然是博弈，完了，博弈一窍不通。

然后顺势看了看 \text{T3}，看起来就是人类不可做的 计数。

没办法只能回去看 \text{T1}，然后发现是一个 模拟+博弈，感觉可以直接退役了。

\text{8.50}

很寄，去看 $\text{T2}

\text{9.30}

看见这个题有很多部分分和特殊性质，感觉还是可以磕一磕的。

先写了个 \text{20 pts}搜索，然后看特殊性质，A,C 看起来比较好做，毕竟和 \text{Alice}的决策几乎没关系。

但是 A 好像只会网络流了，C 只会费用流，觉得过不去 1e5，但是还是要写，写完测了一下发现满数据网络流要跑 6s.

\text{10.20}

然后发现 A 还可以 2-sat，对于每个值跑前缀优化建图就好了。

写完和网络流拍了 \text{5 min}没有问题。

\text{10.40}

浅看了看 T3，猜了个结论是只要所有大小为4的子序列合法就合法，然后果不其然假了，再然后这题就完全不会了。

\text{11.00}

感觉很寄啊，根本没多少分，如果 \text{T1} 不过就真的没戏了。

然后就去磕 \text{T1}，乱想了个做法，倒着拓扑排序，然后根据必胜必败推断前驱节点的状态，最后看起始节点的状态，如果根本没有遍历到初始节点就是平局。

比较难写。

\text{12.10}

写完了，但是第一个样例就不对，调了一会就调出来了。

第二个也直接过了。

但是因为没有暴力也没法对拍，只能检查检查诸如空间会不会小，是否清空的问题，就没时间了。

最后写了个 \text{T3} 的 \text{2 pts}，检查了文件就交了。

\text{Day 2} 下午

民间数据测了测，\text{D1T1}一个\text{30}，一个 \text{85}，只能希望 \text{CCF} 数据水了。

yundou上\text{D2T1}被卡常到了 \text{70pts}，但是觉得 \text{CCF} 的电脑上应该能过。

\text{Day 3}

上午开摆，下午去看了铃芽之旅，比预料中好看。

\text{Day 4}

调了调 \text{D1T2}，然后在xtl上交了有60分，更难受了，本来总分应该有 344的，结果现在最坏只剩 \text{200} 了。

为啥 \text{4.11} 号才出成绩啊啊啊啊啊啊。