HBOI 2024 游记

Day 0

考试前一天早上睡到十点多才去机房，感觉在考试之前睡觉比复习重要的多。

打了一下之前不会的 (ex)BSGS 和二次剩余板子，当然这些东西在正式考试中出现的概率小之又小，学这些东西大概只是为了补齐基础科技树上一些残缺的部分。别的板子在脑子里大概过了一遍，感觉常用的板子我还是很熟悉的。

还补了一个之前的 CF 题。

晚上很早就睡了。

Day 1

在家里睡的就是比在学校睡的好。

早上快八点钟进了考场，今年因为 NOIP 运气好拿下了 HB-001 的编号，Day 1 坐在机房的左上角，还是很奇妙的。现在 8:15 才能开始试机，那感觉早到真的没有什么意义，八点来就挺好的。

顺序开题。

这个 T1 看起来很恶心，想来想去没什么好的思路。最后要求的是两个绝对值的和小于等于一个一次函数，因为两个绝对值的和的图像是三段直线的形式，我最后写了个分段求交点的东西。代码比我想象中要好写一些，不过等最后写完调完还是过了一个多小时。因为大样例太弱，我随手用大样例拼了一组 $\sum n\approx10^6$ 的数据，测了一下发现跑的非常快，然后就没管了，但是事实证明这里还是太草率了。

T2 感觉在 trie 上 dfs 做一遍就很对啊，想了一下感觉很多分支是可以剪掉的，再想一下好像剪到严格的 $O(nk)$ 了，直接开打。打完之后大样例没过，但是答案求大了，说明应当不是剪枝的问题，调一段时间，改了一些细节之后就把大样例过掉了。场上觉得非常厉害，这样的话就期望有 200 分了，说不定 Day 1 真的能拿下标准分。

开 T3 的时候还剩一个小时左右。对着题目在纸上画，样例比较有启发性，推了一段时间发现应当是将图上已有的连通块按大小分成等价类，求每个等价类内部连边的方案数只需要用 $m=0$ 的情况乘上和联通块大小相关的系数即可，有了这些之后感觉做一下 dp 非常有前途，但是时间剩的实在不多了，只好先从 $m=0$ 的 dp 打起，结果直到最后也没写对，连 $m=0,k=1$ 的分都没拿到。

考完试听 hsy 的大多是 150 左右，就是拼了 T2 和 T3 的部分分，外校不少人宣称过了 T2，有的是 $O(nk^2)$ 剪枝拿下了所有大样例，太夸张了。

回家之后在洛谷和云斗上很快就有人自己造了 T1 的数据，我一测，我草，怎么只有 40，怎么只有 60，太炸裂了，总不可能是直线求交点写错了，而且错误的数据我求的答案都是 $0$，怎么回事呢。看了半天，发现我代码里有一处没有隐式类型转换的 $n\times k$，而我 $n,k$ 开的都是 int，考场上大样例 $n$ 和 $k$ 都很小导致我根本没发现有这个问题。这样就很炸裂了，T1 直接挂 60。

下午在云斗上测 T2，发现也爆炸了，测出来只有 64，大概是正确性问题。晚上想出来是剪枝剪多了。wlj 的 $O(nk^2)$ 真跑过了，lyz 也把这题切了，真的是很厉害。

云斗上测出来我 T1 能跑 80，虽然我也不知道为什么，但是大概还可以期待一手官方数据看能不能让我少挂点分。

Day 2

nevercoffee 的冰博客拿铁喝着还行但是有点甜，而且莫名其妙的会让我睡不好觉，以后不喝了。

T1 可以二分 + dp 确定第一位的取值，由于整体访问顺序一定是某个 dfs 序，所以确定第一个位置之后整棵树就被分成了 $\log$ 棵子树，按顺序分别求解即可，这里如何分配总魔力值 $K$ 有一些细节要处理，但是都不困难。写起来无比简单，这题做的比 D1T1 还快。好像很多人写的是先做一个二维 dp 然后再贪心，其实实现起来应该是我这种更简洁。

T2 就是要将 topo 序分成有标号的 $k+1$ 段，这可以做 dp，问题在于没办法对两个不强制先后关系的段定序，这样在 dp 的过程中方案就会算重，后来又想了容斥，但也没什么结果。最后只能拼下性质，拿了 30 左右。

T3 不想写。

总分在云斗上测出来是 100+40+0=140（为什么有 40？），大家基本上都是这个分，极少数人拿了 T3 的部分分。

Day 3

在家里睡大觉。考完试之后睡觉也比上学重要的多。

Ending

云斗上总分是 80+64+0+100+40+0=284，省 rk4，看上去没比去年好多少的样子，考场上不对拍可能真的是有严重后果的，有的题对拍确实比较麻烦，但是以后至少要弄一组极限数据测一下。

估计正式成绩要比这惨。

去年在游记里形容说初三生活不美好，哪里不美好了，薄纱上高中吧。

Update on 3.5

D1T2 已经改出来了，一些分支没考虑清楚，加三行讨论就过了，是严格的 $O(nk)$。

好像 3.7 就能出成绩，非常迅速啊。

Update on 3.7

分出来了啊。早上 macbook 不知道为啥上不了网了，网上说是 usb 影响了 wifi 模块，扩展坞一拔真没问题了。真要受不了这 macbook 了。

最终得分是 80+36+0+100+35+0=251，省 rk5，不理想。D1T1 还是让人松了口气，但是 D1T2 爆炸了。之前看到某群里有人说这个 T2 出题人是对着金牌验题人的错解造的数据，看来确实很有强度，反正这下和暴力同分了。

标准分能到 850 左右，省里还能排个第 2，全靠 NOIP 了。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。