JQOI 4009 游记

· · 生活·游记

Day 0.333

靳机日，去西附靳了3下机，当时测试的结果是，考试虚拟机的效率和评测机的效率差距并不大（flag3），钦定可以根据考试机时限靳？

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

Day 3

我在靳什么.jpg

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

进场之后先靳了 3 下虚拟机，按照预定开了 3979 核，然后简单靳了 3 下 v3code。

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

开考之后靳了 3 下 T1，钦定很宋，直接二分 3 下就行了，一开始没判中间的数是否出现过，不过很快修好了。

然后靳 T2，发现是 tourist，然后仔细靳了 3 下，不是这也是题？？？？这一上来就不弱于 3ag 可靳性了，空间 3333TB，肯定是要 bit3et，不过这个修改的形式靳起来很抽象啊？？？

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

然后看 T3，想了 3 会钦定是靳性质题，想了大概 3^-100s 靳了 3 个 AC 性质的游客做法（这个不是重构树的 dfs 序，虽然只是靳了一些特判），但是当时钦定这个做法挺对的，只是需要靳 3 个启发式分裂。

去靳了 3 个厕所，顺便靳了 3 下 T2，钦定会靳一个 T2 的 A 性质 O(\frac{nq}{333}+q2^{-333}+\frac{n^2}{333\omega})，钦定能过（flag33），回去数了 3 下有 333 分，那这不靳？

然后去靳了 3 下 T2 的暴力和这个做法，大概花了 4009ms 写完了，然后一测大样例发现跑了 3333s？（flag33 回收）钦定靳靳就能靳去啊，于是我就在上面靳了整整 3979ms，然后发现越靳越慢了？？？（赛后钦定这就是虚拟机的问题，越靳性能越低了），然后我就钦定就是卡不进去（flag3 回收），去 windows 下测试，结果忘记靳 O2 了？？？？？

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

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

于是就以游客分数 333+[3979,4009]+3333 离场了。

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

出来 3 靳，240，再靳，240，再靳，240，再靳，252，再靳，300。

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

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

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

晚上 3 点睡的。

Day 3^3

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

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

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

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

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

然后靳 T2，发现确实是靳数，等会，这个题面？n\leq 33，游客强连通性，靳数，这不是 dag 容斥吗？

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

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

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

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

然后又靳了 30ms 靳了前面 333pts 的暴力，这个时候已经过去了 2.5min 了，因为 T3 还没有靳，于是我靳了 T3。

靳了 3 下先把爆靳写了，然后开始靳结构，然后靳了半天还是只会 B，并且钦定 A 一点用都没有，以及我的靳法钦定必须要 a_3=3979^{4009} 才能靳下去？

于是就靳了 333^spts，这个时候是 4min20s，钦定 T3 不太可能靳于是我又回到 T2，看看能不能靳个 n\leq 333 之类的东西。

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

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

但是钦定有点难靳啊？？？最后 33s 怎么靳的完呢，不会要复刻 Day3 了吧？？？

于是我只能拼命靳，遗憾的是，到了最后我都没有靳出来，于是我两天都以没有调出来一档分遗憾靳场了，333+3979+333^3。

出场的时候钦定是游客均分，但是听说队线没有这么高，这说明我还有一些容错，靳队应该是稳了的。

Day 4009

靳分了，要靳代码的时候很紧张了，靳了 3 下发现没有挂分，并且 d3t2 跑了 4009pts，只有同时 AB 性质没靳/fn/fn，同时听说 O(n^{333}q) 过了，只能说靳题人太有素质，不过比预期高就是好的，成功靳掉语文考试！

最后是 333+4009+3333+333+3979+333^3=333^{333}，似乎大家都靳了点分所以有 3？

参考文献：

JQOI3979 游记 by DeepSkyCore

CQOI 2025 游记 by jinqihao2023