BJOI2025游记

· · 生活·游记

Week -2

打模拟赛，一直在火大，OI 比赛老挂分，火大。打 UR，T1 被几次 WA 冲昏头脑后只想到了每次改一个没想到直接批量改跑不满直接能过，火大。 T2 想到了变成差分数组上的匹配也想到了子集卷积转换成或卷积，也发现了要求的东西很像行列式，但没想到随机权值之后就可以是行列式，于是写了个指数级容斥拿了 40，正解写不过爆搜，火大，但遥遥领先的最优解看着像是搜索？

尝试打 AHC，发现这次的 AHC 极其难写，第一发提交就接近 5K，最后是写到了 8K+，但最后看高手的方案时发现自己读错题了，有一种操作是被允许的但我以为不能，火大，我说怎么老是排名那么低。

Week -1

有所好转，AK 了几场 acc，又迎来了人生第一次 AK 的 USACO 铂金组，虽然这次题好像简单。

湖北模拟，先写出 100 + \emptyset + 55，然后决定放弃 T2 正解开始码大分块。T2 怎么写什么暴力都过不了样例 3 啊，我写个 bfs 还能假啊？只有十几分钟了还不弃疗？打开首页，怎么还有一个小时？哦原来是数据锅了？然后又爬起来开始写 T2，这种感觉就像长跑最后冲刺完发现还有一圈又从地上爬起来跑一样。但还是调整好状态写完了。

最后 90 + 90 + 55，无 AC 选手的 rk1，为啥只比总分第一低 20 分就被挤到十几名了啊，又要掉大分了，什么辣鸡区分度。T1 两个点运行时间都不超过 2.1s，T2 第一个点因为后缀数组的离谱 bug WA 了，最后一个点 4.14s TLE，火大。赛后经过亿些卡常都卡过去了。

Day 1

赛前看题，秒了 T1，半小时过。

然后看 T2，好像不可做，开 T3，感觉有点想法。

大概快十点半搞出了 C 的 C 性质和暴力，尝试进一步思考但感觉并不可做，如果进一步突破应该就是正解了，所以从难度考虑应该不太可能，于是回去想 B。

但 B 还是啥思路也没有啊，不带修的怎么才一个点还没有对应样例，出题人你是真会给，那些 a,b 单个不带修的真的和正解有很大区别吗，看了亿会才想到了特殊性质 AC 的一个根号重构做法，遂写，顺带把暴力也写了。

如果加上没写的不带修有 36，考虑到我在 C 上的得分，当时突然想到如果 B 其实很水呢？如果有 O(n) 个人拿到 70^+ 甚至更高呢？当时感到很慌，尝试思考也无果。

但性质 AC 的做法似乎有点拓展性，感觉可以类似 dsu on tree 地去维护每个点的可达集合，盲猜在 DAG 上的“轻儿子”大小总和也是 O(n \log n) 的，开写。开写后发现由于此时的“重儿子”可能被调用多次所以甚至不能直接用一个线段树继承而需要用可持久化线段树。

但是 OI 是个你不想写也得写。

于是不顾升天的复杂度和常数继续写，最后还真写出来了，但是 6 \times 10^4 的都要跑 15s，离谱。给那么多看不出有啥用的特殊性质也不给个数据范围稍微小点的部分分，什么离谱设定。最后优化了一下重构的位置，由修改次数而不是操作次数决定是否重构，这样能过不带修了，并且如果有一些极不均匀的测试点也可能可以卡过去，但机会不大。当时想到了 DAG 链剖分，但我不会 DAG 链剖分，甚至不知道它是用来维护什么的（

最后半小时尝试突破无果，看着 T2 的题面，无法预知自己排名如何，这会是把我送走的题吗？虽然当时没有明确的证据确定我这次打的不好，但想着 188 的估分就让我感到失落。

比赛结束，迫不及待地跑上去问了几个周围的在前几天集训时认识的 rdf 选手，发现他们也不会 B，大部分人都是 20 或 36，放心了，并且一大半都不会 C，之后又多采集了一些样本，可能 B 拿到较高分的在 [\log n, \sqrt n] 的样子吧（？）

最后估分 100 + (36 + eps) + 52，希望不挂吧，应该还可以的分数，像 T2 这种题就只能祈祷 NOI 上不遇到了，Day 2 稳中求胜就行了。

Day 2

赛前看题，A 好像是容易的，看 B，这么困难，哦 n \le 15？诶这不是去年 D2T2 吗，这年头 CCF 这么缺题的，去年 D2T2 我补了！记忆犹新！！！感到了一丝翻盘的气息。

隐约的翻盘的气息让我很兴奋，于是敲键盘很快，声音也很大。半小时过 A，一开始就想到了线段树二分解但刚开始写的时候感觉能直接用离散化后的数组搞得简单一些，但写出来后发现不对又改，最后搞了半多小时。

看 B，尝试推出转移式，B 性质可规约到 C，先考虑 C 性质，在这个 dp 里套上最小生成树看上去并不可做。开始考虑转移，当时莫名地感觉非常兴奋，但我好像推不出来啊！尝试回忆去年 D2T2 的做法，发现细节已经想不起来了，而且那个是 DAG，而这个需要维护强连通方案数。

先考虑转移的起点，那需要是一个强连通分量，强连通方案数咋维护啊？急急急，好像搞不出来啊！无法区分独立的若干个强连通和单个啊！好像只能是联通块数带上一个容斥系数啊！急眼，还能翻吗？

开始使劲想知道了所有子集后怎么求，肯定是减去不强连通，那肯定枚举缩点后入度为零的分量，但不唯一啊，有多个会统计成啥？诶带个容斥系数，但这个带容斥系数的好像就是前面“只能”求的？诶，好像……通了？？？写！！！

然后就是写写写，正好小样例满足 C 性质，好的带系数的好像求对了，那答案咋求？发现转移好像就不关强连通什么事了，先不考虑复杂度，写个 O(3^nn) 先，这里的转移好像是套路的，感觉翻盘近在眼前了。

写完，调，小样例过了，把大样例满足 C 性质的扒出来，诶咋不对啊？写个暴力验证下先，这概率咋乘上 4^m 还不是整数啊哥们？调的时候看着时间一点点过去，有点慌，如果没写出来还因此没写别的题呢？我知道如果放弃而打好 BC 暴力进队应该也是没问题的，但我想赢啊，我也想拿下一次高出人均的分数啊。

调调调，然后越调越诡异，发现加了 O2 之后答案在变化，调了一年没搞明白为啥这些语句被莫名优化掉，汗流浃背了。先放下不管，不加 O2 的好像也有个地方被莫名赋值了，看看，哦，原来是数组开小了/tuu

开小了一个数组卡了半小时，炸裂。改过来后又花了点时间恢复那些调得狂暴的时候改的东西，然后大样例过了！ 忘了具体时间，大概是还有 2h 罢。但其实在看到通过的时候反到没有开始写之前那么激动和兴奋了，可能是已经接受翻盘的事实了吧，更多的是冲击正解的野心、开 T3 并写到大众分的急切和差点被尿憋死的感觉。

有了正确性，然后就是传统艺能之改一点就测一遍大样例确认答案正确，一点点改到了 O(3^n)，接着花了点时间写上了 B 性质和 A（暴力？）性质拿到 64，写完大概是 11:45 的样子，得快点开 C 了。

感觉爆搜分好少啊，AB 性质好像可做，开写。稍加计算后就开始动（四）手（处）实（碰）践（壁）。最后只好手搓了1 2 3和2 3 4的答案并进行调试，最后经过（观）严（察）密（大）计（样）算（例）调通了式子，但最后一类的 2^n 我自己也没推明白具体为啥。然后就导致没发现需要按 a_1 是否为 1 分类，并怎么都搞不明白为什么大样例过了却跟手推的2 3 4答案不一样，最后发现原来大样例都是 a_1=1，最后一组不是并且我的答案不对但一开始没看见（

然后写 8 分爆搜，开始写前发现好像答案都很小，似乎爆搜能过一些？于是开到前六个点，用哈希表优化掉记忆化的 \log，随了几组发现还真挺快，有机会啊！但如果满足 AB 性质好像反而答案很大，感觉会被卡。

最后几分钟又检查了几遍 BC，应该是没啥问题，希望不挂吧。

出考场后问了一圈好像都说不会 B，但不知道意思是不会 100 还是不会 64，我觉得应该是不会 100。虽然出过一次这次 B 肯定不会像上次切的人那么少，而且这次只有 64 而不是 100，但我知道如果我不挂的话我就真的翻盘了。

估分 100 + 64 + [28,44]。

后记 + upd

等出分，在游记中抽样调查，得出结论：

看了眼 D1T3 题解，发现好像是我比赛结束前十分钟想到的思路，那时候想了一下感觉不可做，主要是也来不及了。之后看了眼题解后继续想，但还是觉得不可解，最后画了一下图发现原来我在考虑的那些情况不合法，不像推 C 性质的时候一样画图导致的。

也想象过 D1T2 和 D2T3 多放一些点，最后总分能达到 400，虽然 D2T3 多放的分别人应该也会拿到。但也有点担心挂分，虽然想不出哪里能挂，而且大样例也比较全，但万一 D2T2 那几组数据真的没找出来问题呢？虽然计数题不太可能这样，万一一些拼特殊性质的题大样例其实没过但人眼比对没看出来呢？虽然也都看了很多遍。总之可能是站在玻璃栈道上往下看的时候的恐惧吧。

最后确实是没挂，但也没多，数据造得挺强，但 D1T2 似乎不带修的没过，那就是那个奇妙的做法连那几次多测都没跑不过去，不管了，反正就 4 分。但 O(nq) 放了 88？但那种实现方式确实是没想到，找最大直接按权值扫找到就退出确实会跑不满，而且单次循环本来常数就小，加上 6s 的时限估计确实卡不掉。这种大数据结构题还是别出成 OI 题了吧，在这种要求时空限制在 std 两倍以上的正规比赛中确实难以避免这种情况但考虑到出了两遍的 D2T2 找这种题可能也确实合理。

省选总分是 BJ rk5，那加上 NOIP 和 Day2 权值高估计是进 A 队了，而且前面好像有个初三，最后好像是 rk4。ssf 好像包揽了 AB 队最后一名？赢麻了能再争取个 D 类最后一名吗。

感觉这次比赛整体来说区分度比 NOI 好多了，至少任何一个层次都找不到一个统一的分数分布。