CQOI 2025 游记

· · 生活·游记

Day 0

试机日，去西附试了一下机，当时测试的结果是，考试虚拟机的效率和评测机的效率差距并不大（flag1），感觉可以根据考试机时限卡常？

晚上回去之后感觉很紧张，虽然已经有 Ag，但是感觉还是不甘心就这样结束，所以压力其实并不算小，晚上没看板子，只是看了一下去年的题，越发感觉去年打的唐了。

Day 1

我在干什么.jpg

睡的还行，但是仍然紧张。

进场之后先调了一下虚拟机，按照预定开了 4 核，然后简单配了一下 vscode。

看样例，发现有两个题的输出文件都很大，不会是 ds 场吧？

开考之后读了一下 T1，感觉很唐，直接二分一下就行了，一开始没判中间的数是否出现过，不过很快修好了。

然后读 T2，发现是 ds，然后仔细读了一下，不是这也是题？？？？这一上来就不弱于 dag 可达性了，空间 2048，肯定是要 bitset，不过这个修改的形式看起来很抽象啊？？？

于是，我没怎么想就直接把这个题扔了，事实证明，这个决策相当错误。

然后看 T3，想了一会感觉是推性质题，想了大概 30min 想了一个 AC 性质的假的做法（这个不是重构树的 dfs 序，虽然只是加了一些特判），但是当时感觉这个做法挺对的，只是需要写一个启发式分裂。

去上了一个厕所，顺便想了一下 T2，感觉会了一个 T2 的 A 性质 O(\frac{nq}{B}+q2^B+\frac{n^2}{\omega})，感觉能过（flag2），回去数了一下有 52 分，那这不写？

然后去写了一下 T2 的暴力和这个做法，大概花了 40min 写完了，然后一测大样例发现跑了 8s？（flag2 回收）感觉卡卡就能进去啊，于是我就在上面投了整整 30min，然后发现越卡越慢了？？？（赛后感觉这就是虚拟机的问题，越跑性能越低了），然后我就感觉就是卡不进去（flag1 回收），去 windows 下测试，结果忘记开 O2 了？？？？？

然后心态有点小崩，去看 T3，花了很长时间实现了一个 O(n^2) 的，发现过不去大样例，和暴力一拍才发现假了，这个时候已经很急了，因为我发现现在还没有几分，然后开始硬修这个结论，修了一会应该是修好了（但是这里只写了 AC 性质，没写拼连通块），和暴力拍上了，但是测大样例的时候又发生了一件非常离谱的事情，就是我 sample8 跑出来 user time 是 0.5s，但是 real time 高达 8s？？？？

经过了若干中间变量调试，发现里面跑的很快，但是输出输出了 8s？？？我尝试写了普通快输，但是并没有什么用，于是我冷静了一下选择相信这是虚拟机的问题，但是时间已经所剩无几，这个时候我发现拼连通块很简单，然后试图写完，不过最后还是没调出来。

于是就以搞笑分数 100+[28,52]+32 离场了。

但是这个时候我还没有意识到问题的重要性，因为我想大家应该都是 200 分，那么 noip 优势还在。

出来一问，240，再问，240，再问，240，再问，252，再问，300。

我终于意识到问题的严重性了，这个 T2 原来是人均题？？？？

然后心态就爆了，回家之后和教练通了电话，教练说现在还没有下队线，明天好好打能进，同学们也都相信我能翻的，感动。

晚上自然是不想做题，看了一下笔记然后去公园里面走了很久，不断告诉自己打个队线肯定是没有问题的，Day1 的问题出在策略太差了，调整策略肯定是能上队线。

晚上十点睡的。

Day 2

虽然形式比 Day1 更严峻了，但是反而没有 Day1 紧张了，进场前和教练在操场上走了一圈，聊了一会心态上的问题。

感觉今天状态还行，看样例，发现三个题的输出都很小，然后有两个题的输出都有点像计数，但是另外一个题作为判定 yes/no 的题大样例看起来并不强，得拍。

开题，读了 T1，一开始不会做，于是想 B 性质（也就是区间两两不交），然后想了一会发现我这个都不会做，猜测按照 t-(b-a) 排序，但是画了两下叉掉了，不过似乎叉掉的情况指向了直接按照 t 排序？

上了个厕所，大概思考了一下正确性，发现调整就可以证明了，感觉自己有点搞笑，因为已经过去 30min 了，不过代码好写的，只需要写一棵线段树就行了，不过我还是没有忘记这个题该拍，写了个暴力拍上了。

这时大概过了 50min，感觉这个题还算有点反直觉，应该不是所有人都秒吧？

然后开 T2，发现确实是计数，等会，这个题面？n\leq 15，图强连通性，计数，这不是 dag 容斥吗？

于是开始想这个感觉比较本质的 C 性质，合法条件显然就是图上缩点后仅存在一个点的入度为 0，这个直接容不好容啊，那么直接枚举这个集合呢？

发现算内部的方案数是容易的，但是这个时候唐了一下没想到外部怎么算，于是就没有继续考虑容斥，然后想了一下按照 bfs 顺序统计，但是这样至少是 O(4^n) 的。

已经过了 30min 了，感觉没啥想法，去洗了一把脸，回来继续考虑容斥的方向，发现我只需要对剩下的集合中的零度点容斥就可以了，但是这里我又唐了，认为必须要枚举出发点的可达点集，这样就需要子集和，是 O(n3^n)，不过我觉得这东西也应该没道理过不了，就开始写。

写了大概 1h 写完了，测了一下大样例 3 的第一个，飞快啊，那这个随便过吧。

然后又花了 30min 写了前面 24pts 的暴力，这个时候已经过去了 2.5h 了，因为 T3 还没有动，于是我开了 T3。

想了一下先把爆搜写了，然后开始分析结构，然后分析了半天还是只会 B，并且感觉 A 一点用都没有，以及我的想法感觉必须要 a_n=max 才能分析下去？

于是就写了 28pts，这个时候是 3h50min，感觉 T3 不太可能突破于是我又回到 T2，看看能不能搞个 n\leq 9 之类的东西。

扫描线边权是肯定要做的，那么其实就是合并连通块，我需要知道每个连通块哪些点能到达连通块内所有点，但是这样状态数有点多……？

等会，我直接爆搜所有状态复杂度是对的，2^n-1 的增长效率不会高于 3^n，那这个题不是直接做就行了？！

但是感觉有点难写啊？？？最后 40min 怎么写的完呢，不会要复刻 Day1 了吧？？？

于是我只能拼命写，遗憾的是，到了最后我都没有调出来，于是我两天都以没有调出来一档分遗憾离场了，100+64+28。

出场的时候感觉是人均分，但是听说队线没有这么高，这说明我还有一些容错，进队应该是稳了的。

Day ?

出分了，要来代码的时候很紧张了，测了一下发现没有挂分，并且 d1t2 跑了 48pts，只有同时 AB 性质没过/fn/fn，同时听说 O(nq) 过了，只能说出题人太有素质，不过比预期高就是好的，成功逃掉语文考试！

最后是 100+48+32+100+64+28=372，似乎大家都挂了点分所以有 A？