AHOI2025 游记

· · 生活·游记

2.15

抵达浙江。发现公寓没通知我带被子。

被迫入住酒店。太豪华了，亚朵！

2.16

豪华早餐自助。

杂题选讲，感觉难度正常都很能接受，属于上课就能基本听懂的，很不错。杂题选讲1

下午补题，怎么人均卷王，都写这么快，卷不过。这个 vjudge 补题数榜单功能属实是激发同学们的卷王潜力。

2.17

模拟赛，60+5+30=95。据老师说 T1 是之前 noip 模拟赛 T1，而 T2,T3 是之前 NOI 模拟赛的题目。\mathrm{rk} 17，最菜的一次。

全场没人切 T1，却有人写了 T3 爆标写法。T1 不好评价，正解中计数 dp 中间的 f 值全部是错误的，只有最后一个位置的信息是正确的，所有中间的信息都为后面服务，学到了。其实我写了一个很类似的状物，但是容斥的位置错了。T3 我在 zr 的 noip 模拟赛中实现过一个类似的东西，但是这次却没看出来 /ll。T2 暴力没调完。

感觉这场三题都是略高于我的水平，没有什么不可做，但考场就是做不出来。

被一群初中生单调队列了。

2.18

vjudge 练习赛，简称 at 原题赛。

题目质量不错。最大流转最小割再贪心求解，之前没见过。

下午在奋战昨天模拟赛 T3 的原题解做法，虽然被爆标了，但是还是挺有通用性的。感觉就是维护树上联通块的信息的启发式分裂。

2.19

怎么又是模拟赛。

# 2.20 [trick 题选讲](https://www.luogu.com.cn/article/wwb6bg2y) 居然很多道题都见过原/类似题，还有一题见过加强版不依赖题目性质的做法。感觉自己 trick 积累的还是不少的。 成功冲上当天卷题榜前几名。 # 2.21 模拟赛 $100+40+0=140$，$\mathrm{rk}10$。 $T1$ 是恶心树剖题，我写的是值域扫描线后用树上并查集跳连续段累加贡献，由于暴力跳连续段可能会让复杂度错误，我就用重链和连续段均衡了一下，谁长就跳谁。细节很恶心，写了 4.6 kb，对拍调试 debug 了好多处，调 $T1$ 的中间写了 $T2$ 的 $20 \mathrm{pts}$ 暴力。最后在比赛结束前 $35$ min 成功写出 $T1$。然后补了 $T2$ 的另一个 $20\mathrm{pts}$。$T3$ 的暴力分 dp 我居然没有丁真，最后也没太多时间想了，爆零了。 # 2.22 休息日。 雨中从酒店来回徒步 $6$ 公里游西湖（没有算景区内行走的距离，只计算了酒店到景区的距离）。 ![](https://cdn.luogu.com.cn/upload/image_hosting/pbqhpwks.png) # 2.23 讲课日。被 hehezhou 的讲课暴击了，太难了。感觉有 ZR A 班的难度，不过没有 xtq 老师讲的详细。 原来笛卡尔树计数可以转化为括号序列啊。 喂鸽子非多项式科技做法真巧妙，最巧妙的转化部分上课就懂了，倒是后面的统计 dp 部分理解了一下午，看起类很显然，实则细想一下问题一堆，很多小问题想了好久，周围人都是直接贺代码太没素质了。 下午到晚上大战 DFS order 4，这已经是我第三次在集训中遇到这题了，对着 xtq 当年上课讲的做法理解了好久。 一天喜提两题，vjudge 榜单垫底。不过我觉得有深度的思考比一群人无脑贺代码强太多了。 还有一堆题没补/ll，省选回来之后有机会再理解一下。 # 2.24 lbr 生病回去了，于是 ltl 坐到前面来了，本来以为他是一个单纯正经的孩子，没想到他这么调皮。 模拟赛，$100+50+30=180$。这次突然来了一群浙江高水平选手参赛，但是我却取得了在 xyd 的最高排名 $\mathrm{rk 5}$，在原先班级大概是 $\mathrm{rk 2}$。 $T1$ 这不是刘汝佳书里的树上贪心合并联通块的 trick 吗，快速切了。~~并教会旁边同省同学本题做法，ltl 说看着别人受到这题折磨而自己却听了别人思路写出感觉很愧疚。~~ 先开 $T3$，字符串上博弈论问题，感觉这个结构很像 SAM，但是具体做法没想出来，于是暴力提取所有子串放到字典树上辅助建图，跑了一个 DAG 博弈。丁真了 $a,b$ 随机串的做法，但是空间快不够了，遗憾错失 $20pts$，其实后来发现其实可以直接记录哈希值用 ` std::map ` 匹配状态就行了。 $T2$ 打表找了个数字分布的规律，打了个暴力 $+$ 特殊性质。哎哎赛后听讲解才发现自己唐完了，怎么没场切。 下午随便补了点模板默写，记事本模板大战被同省大神碾压了。 # 2.25 vjudge 练习赛，瞎写了点题。下午继续复习。 # 2.26 模拟赛坠机场啊，一眼丁真 $T1$ 结论，打了个表以为自己猜错了，其实是我不小心把值域范围外的也统计上了，后来写了个 dp 重新验证了一下结论，对了。然后成功把判定条件中的 $\mathrm{popcount\le 2}$，写成了 $\mathrm{popcount=2}$，原因是我找规律的时候忘记考虑个位数了。正好由于没有大样例，自己懒得对拍就挂飞了。 $T2$ 把全局变量写成了局部变量又挂飞了。 $T3$ 写了一个平衡树去冲更大的数据范围，结果赛后一看怎么同学的暴力也拿到了同样分数，数据太水！ 晚上继续复习。 # 2.27 省选策略讲解，老师还对于去年的 D1T2 提出了一个压缩 trie 的做法也就是对于关键点建立虚树这样子树的大小就是 $O(n)$ 的可以大力二分了。 下午被约过去谈了一下策略。 打湖北省选模拟，$T1$ 写了个二分 $+$ 记搜怎么还 WA 了，到现在还没查出错误懒得查了。$T3$ $55$ 太典了吧，感觉和某年省选填树的部分分 $O(nW)$ 做法思想一模一样。我用了逆元，在 $5000$ 的数据点 TLE 了，被卡常了只有 $45$，晚上在 LA 群里询问得知可以前后缀积来避免逆元。$T2$ 感觉像 SAM 优化建图，瞎打了暴力和特殊性质，特殊性质挂了是我假了还是写错了。 晚上去杭州的一家西班牙餐厅吃饭，有点贵量不多，但是感觉味道非常地道，酱汁的味道真的绝了，对比去年吃的一家，感觉那个更偏中国化的西餐味道，而这个更纯正。 # 2.28 到达芜湖，疯狂复习板子，快复习不完了。 下午去 asdfz 试机。发现 Purslane 和我在同一个考场，进去之后才发现他甚至和我在同一排。 键盘很恶心，手感超级不好，瞎写了一个 fhq，发现编译不过，显示信息很奇怪。叫来了 lbr 看看，他也没看出来，又喊来了 ltl，才发现是我打了一个中文逗号。 这个垃圾的键盘让我已经没有调试的欲望了。这个时候 Purslane 来和我打了个招呼，在 apio 的时候见过他，但是他当时大概不认识我这个蒟蒻。 然后他就开始 P 了，说我很有可能切掉两天 T1 然后翻盘进 A。我表示不可能。结果他前半句话还真说对了！ 离开考场之后，去吃饭了。这顿开始直到省选考完的每一顿基本都是很好吃的，但是我基本都没啥心情，根本吃不下，感觉肚子本来就是满的。 晚上又疯狂复习了一番，然后睡觉了。 # Day1 联赛离队线差了三名，准备今天翻掉。然后 Day2 参考去年大家得分应该一样。这样子就成功了。 可是现实却恰恰相反。 开场发现空格键问题比昨天更大了，直接要求更换键盘。继去年之后再次以全新键盘开局。 随便打了点代码就发密码了，keep dreaming ! 顺序开题，看了眼 $T1$ 中位数，盲猜是扫描值域然后进行经典 trick $-1,0,1$ 转化。随便写写之后发现不用那么高级，直接就是 $z\ge \max(x-y+1,y-x)$ 就行了。对于线段不交情况是简单的，对于线段交的情况，怎么分配数字？发现左右边都是线性的，因此直接贪心地把所有数放到当前判定的区间即可。用扫描线维护就行了。 想了点离散化的细节，左闭右开就行了。 大概 8:50 了，直接开写，代码很好写只有1kb，开场手感一般加上键盘没那么熟悉，就放慢点节奏 9 点多写完了。 小样例过了，大样例没过。day1 最唐时刻来临，我查了半天错，直到输出了大样例的中间变量，才发现是我在求绝对值函数最值的时候直接对于两个变量取了 $4$ 种端点值情况，忘记值域有交的时候直接就是 $0$ 了。无敌了。 10:00 不到开了 $T2$，一眼 tarjan，哦不对保证了 $u<v$，所以是一个 DAG，不需要 tarjan。想了想很难做，我考场上感觉可以操作分块 $+$ ` bitset `，具体的一些实现方法有点难想，复杂度也未必能卡对。DAG 上动态维护后继信息的偏序最值明显不太可做，于是果断拼了个暴力之后跳了这题。 11:00 不到开了 $T3$，部分分和性质很多看起来也相对能做。这大概是今天的区分题了。 时间还早，不准备去打暴力。我准备先试一下 $O(n^2)$ 的分，毕竟这个可以逐位确定字典序。那么现在的重点就来到给定一个排列/填了一部分的排列，有没有一种很好的判定方式了。 $p_{a_i}$ 这种形式很怪，不好处理。于是根据 AT 某题套路，我先考虑了去逆置换 $q$ 上面做这题，这样子就可以直接根据边的端点得到 $q_u,q_v$ 了，然后字典序最值就改了将 $1$ 尽可能往前方，在此基础上尽可能把 $2$ 往前放...... 这种题我还真过好几道，于是比较有信心。 做了半天发现虽然逆置换上做这题可以轻松进行第一步，但是很难处理约束条件。急了，上了个厕所回来继续思考。发现由于取了逆置换，因此本来的下标有交变成了值域有交，我在一维数轴上很难刻画这个东西，必须变成二维平面，放弃了，还是在 $p$ 上做这题吧，毕竟可以轻松处理约束条件。 上面的思考虽然基本废弃无用了，但还是给我了一些启发，$p$ 能轻松处理约束信息，但是处理第一步的 $p_{a_i},p_{b_i}$ 有点麻烦，因为这个不涉及约束条件所以在假设排列存在的情况下根据值来进行定位。如果是一位一位确定，加入新数的时候就可以直接根据加进来的数到图上来定位一个点了，那么图的形态就很重要，发现有森林的分，于是立刻思考森林。 我发现加入了一个点，就相当于闭合了若干条线段，并且向右增开了其所有连接的为加点的线段，要求线段不交。如果你在不同子树选了两个点，那么在一个子树先取完闭合的时候必定和另一个子树所对应的线段产生交这就失败了。 哎，这不就是要求子树连续访问吗。11:40 不到我就想到了这个结论。准备开写了。 我先拼了一个 $8$ 分的暴力，我怕阶乘枚举之后再套 $m^2$ 的 check 会超时，于是我就写了 一个很简短的 $O(m)$ 的扫描线，发现假了，修改的话还需要加入更多细节，不想花更多时间了。暴力应该跑不满会很快，于是删了扫描线写上暴力 check，这个时候由于题面上将 $m$ 错打印成了 $n$，导致我代码也写错了，查了半天才发现，这个暴力浪费了我好多时间。 于是我猜测了一个构造方式是对于每棵树取最小点为根，开一个虚点当成他们的父亲，然后对于所有儿子 sort 一下进行访问。 测了一下大样例，发现构造错了，前两个点不是父子关系，于是我就修正了一下，子树依旧是连续访问，但是不一定要从根进入。于是我就写了一个线段树维护 dfs 序，每次 $\mathrm{solve(u)}$ 表示处理 $u$ 子树内的信息，然后查询子树最小点 $v$，然后删除该点信息，加入答案，并调用 $\mathrm{solve(v)}$。飞快码完，大概是太过紧张，我线段树在两处将 $p$ 写成了 $l$ 又浪费了不少时间。测过大样例发现还是不对，手造了一组数据才发现，我上面的代码实现出问题了，$\mathrm{solve(v)}$ 返回之后是直接回到 $u$，而不是 $v$ 所在子树的根，但是时间已经来不及我去修改这个细节了。遗憾错失 $44\mathrm {pts}$。 匆匆查了三个题的文件之后下考了。 最后沦为大众分 $100+20+8=128$。 下考后很是破防，我并没有完成在 Day1 就翻盘的任务。错失了直接杀死比赛的机会，如果拿到那 $44$ 分，Day2 随便写写暴力就进队了，会轻松很多。 下午统计了一下省内情况，发现 Day1 翻了前面的两个人，但是被后面的 zhb 翻了。所以由于 noip 的劣势，我还距离队线差两名。 晚上心情稍微好了点，但是我也明白我已经走到了绝境，我很可能在今天就已经错失了最后一个翻盘点。 如果明天还是去年的那个难度的话，大家都是一个分，那就完全没有机会了。 我能感受到自己似乎真的就要离开我所热爱的一切，要告别 OI 了。 很沮丧，坐在窗边，看着城市的万家灯火思考着我的未来。 我明白当我把所有筹码都放在 Day2 的时候，我可能已经输了。 # Day2 没有退路，只能孤注一掷了。 开场浏览了三题，没有去年的那种神秘题了，而且三题貌似都给了不少性质分。看到 $T2$ 我想到了考前复习的一道 ZR 的最小生成树相关的 $3^n$ 容斥题（虽然最后发现两者关联没有那么大）。隐约看到了点希望。 开 $T1$，我居然一眼丁真了？？这不就是 CSP-S 2023 种树的策略吗，线段树二分维护一下不就行了吗。 怕自己假了，先写了一个 $n^2$ 暴力贪心验证了一下自己的结论，发现是对的之后又思考了很多实现的细节。9:25 开始冲正解。比之前写的线段树二分多了点细节，最近有点咳嗽，因此写的脑袋昏昏沉沉的感觉很晕，好在还是强撑着自己想对了写法细节并在 1h 之后写完了。 查了一个错，又在 O2 下面运行一下，卡了点常。做完了，我明白自己拿到了主动权。 11:00 不到开了 $T2$，然后我看错题了，导致一直没思路。只好打了一个暴力，外向最小生成树很难处理，反正数据很小，直接全搜一遍。实现的很丑，写了 100 多行。测了小样例对了，测了大样例发现不对，急了，各种输出中间变量调试。发现自己的并查集忘记合并了。改完之后还是不对，都 12:00 多了，急了，但是没办法，后来才发现是自己读错题了。 > 其边权和等于图 G 的最小生成树边权和 我把 $G$ 看成了 $G'$，我说怎么剩下一个有向图还求一个无向图的最小生成树呢？我当时处理这个的时候就直接把 $G'$ 当成无向去算 MST 了。 写完之后发现只剩 $20\mathrm{min}$ 了，我错误预估了 $T3$ 暴力的难度，其实可以 5 min 写完的，但是我以为要上什么序列哈希存子序列，其实直接用 map 套 vector 就行了。以为写不完了就没写，尝试猜 B 性质的答案，手算了几个发现没找到规律。本题大概是没希望了，最后几分钟又回去看了 $T2$，发现这个 $B$ 性质在我理解对题意之后其实并不难。但是来不及细推了，瞎写了几个阶乘和组合数上去，发现不对（后来看别人代码我应该就差了一点系数），破防下考。 最后是 $100+12+0=112$。 出来了解了一下情况，只要 D2T1 不挂分的话我大概是翻了。火车上又看了一遍其他人的代码，确认了这个想法。 但是 D2T1 我不会造 yes 和 no 均匀分布的数据，就没有对拍了，感觉样例不强，于是心里很慌。 回家睡了一觉，发现云斗出了数据，测了一下过了，超级开心。 后来云斗出了完整榜单，$100+20+8+100+12+0=240$，如果官方数据保持不变的话那应该就进队了。 D1 被很多不必要的失误浪费了太多调试时间，因此没写完 $44$ 分，D2 因为 T2 看错题，导致没拿到 T2 B 性质的 12 并且来不及写 T3 的 8。如果都能拿到，那在省内甚至可以排到前 $4$ 了，不过事后说这个已经没有任何意义了/ll。 整体发挥很烂，我在省内失误，由于水平问题，其他人还会留给我机会。但是如果到了 NOI 呢，越来越高的 Ag 分数线和飞速提升的选手整体水平不会留给我任何机会。如果还是这个发挥估计就要打铜了。 这赛季从 csp 到 noip 再到省选，都是下限级发挥，并没有达到期望 $(240,232,240)/(316,272,304)$。唯一好的消息就是 noip 和省选一分没挂，并且三场考试的排名也是越来越高。 希望能逐步提升实力吧。 先去补这段时间集训所欠缺的 whk 了，蹲一个官方成绩和榜单。如果进队了，未来应该会去 nfls 集训了。 # UPD 进队了。