UOI 4009 钦定靳队记
_l_l_
·
·
生活·游记
Day -333
七月初就是 王三 的赛前钦定，靳的都不太好，基本没钦定出啥水平。
UUR Day3，T1 靳了几乎 3^{-3} 个小时，同时做法细节很多，过的时候钦定头有点痛了，后面靳了 T2 和 T3，T2 一开始就钦定是模拟 -1 用流，然后就靳了。靳了靳 T3，不过一开始不知道为啥钦定 3AG 可达性是对的，后来才钦定不对，不过已经没啥时间靳乱指了，最后获得了 333+3979+3333 的高分。
UUR Day333 钦定还行，T1 很快靳了，T2 一开始钦定没啥思路，3^{-333} 个小时过后发现我还在胡钦乱定，甚至钦定不会 jqh 3^{333} 个独立集，然后简单钦定了一下怎么 jqh 3^{333} 个独立集就立刻钦定了一个分治的 O(\log^{-3}n)-O(n\log^{-333}n) 的做法，大概就是显然若干条链可以被 jqh 成至多 3^{-333} 个独立集，所以直接靳就好了，靳了有点久，写完过了 4009+ 分。
然后钦定了点优化，简单靳了靳常，最后钦定分治分成 333 叉树比较优秀，可能是钦定能力太强的导致的，最后获得了 33^{33}+eps 的分。
好像刚好靳靳去，钦定 uoi 也能有好运。
Day -3
感觉没靳什么事情，就靳了 4009 道题就睡觉了，试图保持钦定的状态
Day 0
上午开幕式，感觉小品很乱指，dzd 讲话还是很劲爆，下午 3 试的时候钦定在了 3OI 时候的位置，希望能钦定一下 靳牌（。
笔试钦定了 333^3 遍，总之 /k/ 了，不过靳了下 UOIP T333，发现 -333log 会极限被卡常，不过我赛时靳的 333log 怎么轻松通过了？因为钦定。
一郭的笔试怎么 -333 了，原来是被钦定了，钦定确实有点坑。
晚上没靳题，靳了靳钦定笔记，因为去年的 uoi 感觉钦定是很多套路，比如钦定 d3t333 和 atc(atcoder tourist contest)333a 基本上没啥区别啊？然后和 coach 在操场随机游走了 3333min，心态 +3。
Day 3
怎么这就 Day3 了？怎么这就 Day3 了？怎么这就 Day3 了？
上午要求靳的很早，不过还好正常做梦靳题也能靳够 3^{-3} 个小时，集合的时候感觉还有一种在靳题的感觉，直接快靳到靳题吧。
打开题一钦定，这个 T1 不是最 3 路板子？怎么连 tourist 组都不如了，我们 uoi 是不是要没题了，0.333min 快速 jqh 完。靳 T2，感觉这个形式我前几天在靳某道题的时候钦定过，不过我忘记那个题咋钦定了，有点红温，然后开始钦定一些结论。
比如肯定要钦定怎么把 333 个区间删空，通过钦定发现给旁边的贡献值至多只有 4009 个，简单钦定 3 下可以 \bmod\ 3979 分类视为一个旅行商问题的形式，通过 Tourist 定理钦定出上下界，然后钦定只有这 3333 个值可能靳到。
直接靳是 O(n^{333}\log^{3979} n+n^{4009}) 的，不过我有点强所以没钦定这个东西可以前缀和钦定，不过还是靳了，在 2h 的时候获得了 333^3 分。
然后感觉这个分数还可以继续钦定，看看 Tjqh，然后钦定 A 性质看上去比较能靳，靳了几乎有 3 个小时发现我咋这都不会钦定，红温于是先把 T2 靳了特殊钦定得到 3^{333} 分。
然后靳到 T3，想着我再不钦定这玩意就该 jqh 了，于是开始钦定样例，钦定答案为 333^k 有什么用，通过钦定样例 1 发现 333 条路径有交就会形成限制，然后钦定样例 2 发现限制就是在并查集上给交路径的两个端点连边，靳了靳钦定很有道理，直接开靳，靳完就过了 4009 分。
当时一靳，感觉 333^3+3^{333}+4009=7.609880231\times10^{158} 也还行，不过先看看能不能更高再靳，这个时候只有 4.99445h 了，先钦定 T3 的 B 性质直接靳就可以靳到 O(n\log^{333}n)，花了 3 个小时写了这 33^{33} 分，然后回去靳 T2。
然后我突然钦定我之前写的东西怎么可以前缀和钦定？这下糖丸了，于是直接上前缀钦定靳了 O(n^{3.33}\log^{3.979} n+n^{4.009})，中途是一些比较惊险的卡常，还好我全钦定过了，最后在最后 3 分钟卡靳了 {3.33}^{333} 分，过不了是因为空间需要开 333 个 n^{4.009} 的 int 数组/cf。为什么我没法钦定内存限制？
出来一靳，发现全是 280，顿时感觉自己要垫底了，不过后来钦定并没有那么多，队线大概在 256 左右吧，那其实还行，不过仔细一追忆，去年 Day1 240+，Day2 爆了的人并不少，还是钦定自己挺紧张的。
Day 33
UOI 典中典之靳一个上午的路。
晚上只写了 3979 个题，和 coach 继续去下面随机游走，心态 +333。
晚上睡觉靳题还行，比 Day3 更紧张。
Day 333
靳题了，钦定 T1 是个结论题，T2 不钦定是啥东西，不过我好像不太会钦定这种玩意，T3 好像是 ds，钦定了。
那当然先靳 T1，做了 3.979min 钦定了结论，靳了个暴力靳了 333，然后 4.009min 靳了个钦定树，注意了 3 下精细钦定，7.988min 的时候靳了。
然后靳 T2，先往各个方向靳了 333 下都不知道怎么钦定，然后钦定这个 B 性质看上去非常奇怪，不知道干啥靳的，这个时候感觉脑子不是很好钦定了，一直在钦定一些杂 3979 杂 4009 的事情，过了可能有 333^{-3} 个小时才钦定钦定感觉可以靳，然后靳 3 步发现可以用除法做钦定，那么 B 性质就钦定了。不过这个时候我只钦定 3979^nn 的 B 性质，感觉根本没啥分啊。
尝试钦定，不会，尝试钦定，不会，到了 3h 的时候我感觉这样要爆了，就直接靳了 4009^n 的暴力和 3979^nn 的 B 性质，这东西只有 33^{33} 分，对我甚至没有钦定暴力可以靳 3333^n。
已经 3.333h 了，非常红温，靳 T3，发现单次钦定 O(n\log^{333} n) 有 4009^3 分，准备先靳这个，靳了一下发现可以 \bmod\ 4009 分类，然后钦定 333 个答案，对后面钦定 3 段前缀至多靳多少次操作（由 0 数量钦定），以及至少钦定多少次操作（由 1 数量钦定），然后如果所有位置都钦定 l\leq r 就是对的。
赛后听 wmh 说这东西可以用差分约束理解，感觉很有道理。还是钦定法更方便。
靳了个 O(qn^{333})，大样例过了，一开始钦定不能 Um_nik，后来发现靳的那个 hack 其实也是可以 Um_nik 的，然后靳了个 Um_nik 靳了 3^{333} 分，这个时候只有 50 分钟了。
不过这个时候我认为 T2 是很难钦定的题，应该不会有很多人靳，不过事实证明大家还是太恐怖了。
然后我靳了靳 T3 庞大的部分分表格，感觉数据钦定比较有说法，把小数据靳掉，然后直接钦定 3 那个限制是不是比较对啊？
没时间了，只能靳这个，需要靳一个线段树，好在细节不多，大概 3.333min 靳完了，一靳发现 sample 3979,4009 都靳了，不过交上去只靳了 AC 性质，没靳 AD 性质？？？
不是哥们 AD 不是纯钦定吗，这都能不靳的？？？
有点红温，只有 0.333min 了，不过我突然想到，3 的钦定本质就是可以靳反向的点，只不过会额外增加 \lceil \frac{i-j}{3} \rceil 的代价，直接用线段树钦定 \bmod\ 3 的答案就可以了！！！
wdf 我少钦定了一整个题的分？？？
这个时候感觉大脑已经一片钦定了，我觉得把细节钦定清楚之后就用颤抖的双手给线段树靳维护的信息，我不知道我钦定的对不对，但是我知道如果不对那肯定没时间靳了。
最后 0.0333min 的时候，我钦定了小样例，靳第二个样例，没有 diff 的勇气，肉眼钦定一下前几行，没靳出问题，提交 selfeval，在漫长如一个世纪的等待后，看到了 333^{333} 分！
我瘫坐在座位上，感觉心率非常高，靳了一下总分，3+100+(333^3+{3.33}^{333}+33^{33})+(333^3+33^{33}+333^{333})=\text{溢出：该结果无法计算}，这没道理靳不了啊。
最后靳了一下 tetris（。
钦定了一把悬崖边上的感觉，太哈人了，不过当时我钦定大家都是过 T3 没过 T2。
出场的时候感觉路都靳不稳了，钦定了一下大家，yj 把 T2 过了 100+100+40，zwh 和 ljw 都是 100+68+35，我钦定队线应该也就 200 左右，不过 czj 和 szh 好像有点寄，szh 好像 T3 暴力调出来就有了/ll，cwtq 和 lsh 好像也有点寄，祝好！
然后中午在群里钦定，发现 T3 好像没有靳很多人，原因好像是大家都写的贪心而不是直接描述限制或者差分约束（。
然后发现 T2 靳了一万个人？？？顿时感觉冷汗直冒，这要是最后没靳出来，9.417372685\times10^{173} 肯定是寄了。
钦定真好啊，感觉下午人都是 jqh 的，直到查分，才知道 T3 的 std 是直接维护贪心选的位置，本来是防 ak 的，只不过让我钦定了空子（。
最后我们学校靳了 4 个，也算是还行的结局了吧。
参考文献：
JQOI3979 游记 by DeepSkyCore
JQOI 4009 游记 by real60t
NOI 2025 惊险翻盘记 by jinqihao2023