SDOI2025游记
2.28
上午上学。下午收拾东西出发。路上学粤语歌，颇有成效。
吃完晚饭试机，机子远比想象中要好用，于是很开心。
晚上感觉很累，十点半就睡了。
3.1 (day1)
早上 6：38 起床，精神很好。在酒店吃早饭，差点吃多了，幸好及时止损。
发现外面似乎下雨了，于是拿了伞，很凉快。
慢慢走到山师附中，才 7：40。等待进场，于是成为了第一个走进校园的人，但是并不是第一个到达考场的人，原因是一个老哥走太快了。
7：58 进入了考场，开始试机，写缺省源。三个题是 lucky,recall,graperm。
8：24 拿到了解压缩密码：keeP*drEAm&iNg。很好。直接开始读题。
8：28 读完 T1，似乎不太好做（？）开始读 T2。
8：30 读完 T2。比赛正式开始。
8：32 这个 T2 竟然 6s+2G，n 却只有 1e5？？？什么巨大的 DS 题，似乎会有很多分可做（？）想了一小会儿，还是只会 20pts。还是回头做 T1 吧。
8：38 哦哦，我大概会 T1 了。做法除了排序以外是 O(n) 的，具体就是排序+二分+贪心，懒得说了。写写写。
8：50 过编译。
8：55 调过小样例。大样例怎么过不了的。
9：12 苦思冥想之后，终于意识到答案不一定是一段连续的，有可能中间会出现一些不被给定区间覆盖的位置。那只要和给的区间取个交再求并就好了。
9：18 过掉所有大样例。感觉有点慢啊，一眼秒掉的题应该也就是个绿题吧。
9：25 这个 T2 好难啊。除了暴力 20pts 一点儿不会啊。上厕所，吃薄荷糖。我来看看 T3。
9：35 妙妙的构造题。想想树怎么做。C 性质有 48pts。意识到子树的放置只需要用一个 stack+set 维护，每次取 min 的放，放过的就要等到下一次退栈退到它的时候才能放，即可（？）
9：45 打好了前两个点的 8pts 暴力。准备冲击C性质。
10：00 逐渐假起来了。怎么要 O(n^2) 的，这样才16pts 好像。
10：10 怎么两个例子的放置策略不一样了？？？疯狂手玩。
10：20 好乱，找不到统一的构造方案。上厕所。尝试将森林通过加 0 号点转成树。树上递归去构造。
10：30 咋做。还是不要 0 号点了吧。
10：35 欸等等，如果我已经求好了每个连通块的方案，合并是简单的，就是用我刚开始想的那个用 stack 和 set 的做法就好。
11：00 苦思冥想到 11 点，发现怎么只有两个小时了。而我还是只有 100pts。急急急。在回头转战 T2 和继续死磕 T3 中徘徊。最终心一横，不破 T3 终不还！
11：15 好热。上厕所。哦不对！我突然意识到根节点处的放置和下面竟然不是一样的！根节点由于没有向上的边，那么可以随便放；而普通的点就必须不能放在自己子树的内部！那么只需要分三类去写就好了！
11：30 写完了！调调调！
11：42 过不去大样例！怎么只有 1h+ 了！急急急！
11：45 把写的暴力拿过来，上对拍！等待了 eps 秒出锅了！哦！原来是根节点处的儿子访问没有 sort！
11：47 过了大样例！怎么 1e5 的又爆栈了！我又忘了怎么手动开栈！不管了！应该能过！上厕所。
11：55 尝试拉到 linux 下测，然而不太会用 system 输入输出文件，失败了。
12：00 还有 1h，我还有救。转攻 T2！
12：10 先把 20pts 暴力写了。想了若干个复杂度高于暴力的做法。最终找到的最好做法是一个 O(n^2*logn/w) 的奇妙做法，能跑 6e4？？？但是要写树套树+线段树套bitset，有点过于抽象了。
12：20 突然意识到我的 T3 已经会了树之后是不是只需要 tarjan 一下就能拓展到图上了？那不就 100pts 了吗？
12：25 冷静冷静。仔细思考。
12：30 思路大概成形了。环怎么放？应该一定是从最小的放，一定是连续的一段？
12：35 我会了！还有 25min！冲！疯狂砸键盘，全身都在发抖。
12：48 写完了！最终代码无注释 360+ lines。激动的心，颤抖的手，按下 F11，一堆编译错误，仔细修改；再次按下 F11，运行错误；dfs 没打标记，改；F11，样例 1 只过了第一组测试，第二组死循环了；找环的 dfs 出锅了，修改；F11，样例1 WA 了；找错，改。
12：53 过了样例 1！手抖得更厉害了，干呕的眼泪都出来了。强行压住。测样例 2，只过了一小半！心凉了。不死心，继续修！
12：56 赶紧先把 T1 和 T3 的代码放到文件夹里。监考跟我说：你这个建的不对啊。我说：我知道我知道，我有数。
12：58 真的没有奇迹发生了吗。把自己 360+ lines 的代码注释了，把前面的 240+ 行的 52pts 代码复制过来，放入文件夹。
12：59 点开倒计时，盯着屏幕，联合省选2025 day1 的最后半分钟。
13：00 结束了。
出来的时候感觉又想哭又想笑，感慨万千却不知从何而谈。我觉得这一次我拼尽了全力，极其可惜的是如果我再有半个小时可能就能调出 T3 了，庆幸的是我敢于放手一搏，死拼 T3，而没有在似乎很难得分我也不太擅长的 T2 上浪费时间。最为懊悔的是前期做 T3 的 C 性质太过于浪费时间，思绪理不清楚；而最后 30min 反而是一场中思绪最为清晰的时间。如果前期我能再快一些的做出来，最后也许就能拿出充裕的时间去调 T3 了。然而哪有什么如果。回宾馆的路上，感觉我自己就像灵魂出窍了一样，浑浑噩噩，不知道在走路。
回到宾馆后，翻了很久洛谷群，才舒服了一些。看到洛谷给的评分是蓝黑黑，属实惊到我了。我差点就当场做了一个黑题？？于是开始写游记。写到赛时 12：58 的时候突然意识到最后那一份代码没编译！又慌了。但是安慰自己已经过去了就不要再放在心上了，于是心情又好起来了。
自己预估 100+20+52 = 172pts。不知道民间估分。但是感觉会在 SD rk20 以内吧，SD 队线会在 192pts 左右吧。
调整状态，明天再战！
3.2 (day2)
昨天晚上十点早早睡了。今天早上六点半起床，状态很好。仍然在酒店吃早饭。
发现外面下了雨，于是打着伞缓慢前行，结果还是湿了鞋尖/kk。
到校门口等待进场。进入考场。意识到今天必须在队线内才能有希望进队。
8：07 才允许开始试机。做了和昨天一样的事情，但是考虑到昨天后期用了对拍，于是先打好了对拍（虽然今天没用上）。上厕所。
8：22 拿到密码：ReM#Ain(LoVinG。开题。三个题是 move,years,seal。这个 T1 怎么这么熟悉的，我似乎做过原题？但是我警告自己不要想原题怎么做，只去想这个题咋做。读 T2，被题面吓到了。T3 看上去是计数题，先不急着读题。先把文件操作弄好了。
8：30 比赛正式开始。我来想想 T1 咋做。性质 A 由于所有的 ti 相同，那么操作顺序就无关了，那就是简单的。B 性质直接把 bi-ai 加起来就好，这是没有交错的情况。那么不难想到将原序列中所有分成两类：ai<=bi 和 ai>bi。那么只需要考虑相同类的最大连续段。而这也与性质 C 相吻合！保证了只会有一段。我突然发现这题只要会 A,B 两个性质再加上暴力就有 44pts 了，那这个肯定是签到题。
8：40 先不急着想怎么处理若干段之间顺序的问题（感觉就是按时间的 min 排个序就好）。我来尝试做 C 性质。
8：45 有了想法。于是假装自己会了，开始写。
8：50 不妨设我在处理的段的类型是 ai<=bi 的。如果一个 ai 在向后移动到 bi 的过程中如果被其他的 aj 挡住了，那么形式化的式子就是 aj<=ai+j-i。这里的 ai 其实是 pos_i，代表的是 i 箱子当前的位置。那么又由于保证了 ai 和 bi 分别单调递增，这个东西其实就很强了。我在为了让 i 能走的过程中，挪动 j 的时候，如果被 k 妨碍了，那么 k 就一定也会妨碍 i。这样的话只需要根据 i 就能确定这个需要移动的区间了。
9：00 但是我这个怎么要 O(n^2)。那这样才 60pts。上厕所。
9：05 这怎么要维护区间赋值等差数列的。哦哦不对，aj<=ai+j-i 改为 aj-j<=ai-i 就好啦。又因为 ai 单增，所以 ai-i 一定不降。那我直接拿线段树维护 ai-i 不就好了。修改是区间赋值，而算答案只需要维护区间和。然后二分。哦这个直接线段树二分就好。这样才 1log。
9：10 那这个选的顺序怎么弄？猜了一下一定是按照 ti 从小到大。调整法感性证明了一下，似乎很对。写写写。
9：25 写完了，测了一下 C 性质都过了。那这个不同段的顺序咋弄，中间会有交叉啊，咋做，好乱。上厕所。
9：35 哦不对，是不是直接把 n 个箱子都按照 ti 排序就好了。似乎很对。改改改。
9：40 怎么只有 move5.in 中的一组数据过不了的。大样例强度感人。尝试 #define int long long 无用。我来输出调试一下。
9：50 似乎都挺正常的？哦是不是我没算刚选出来的这个箱子对答案的贡献？加上。这一组错误的数据过了。怎么小样例又出锅了？？？哦不对，我这个已经包含在线段树的 query 结果里了。
9：58 欸欸欸，这个不对，移动到的应该是 pos 吧。怎么小样例还是过不了的。
10：00 呃呃呃，想反了，应该是把所有 pos 改成 bi。改之。
10：02 通过所有样例。感人。这题会有紫吗，理论来说省选 day2 不能再放一个绿/蓝了吧。要真是紫那我就轻松场切了一个紫题耶。上厕所，吃薄荷糖。
10：10 发现带的东鹏特饮还剩一半，尖叫已经喝没了。我先来读一读 T3。
10：15 这个 T3 怎么计数啊。我怎么只会 O(ans*log) 的暴力。
10：20 欸这个 T2 怎么 n<=15 的。这是什么题？我来做一做。
10：25 我好像会 A 性质了（？）直接暴力就好。
10：35 我好像会 B 性质了（？）由于任意 wi!=wj，那么最小生成树是固定的，也就是说最小外向生成树的边权也是固定的，那么只有 n 种树，每种情况算方案数就好（？）。上厕所。
10：45 这个 C 性质咋做？wi=1，那么只需要保证 G' 这个子图中存在一棵外向生成树。看起来像 Matrix-Tree 定理，但我忘了啊！
11：00 不会做 C 性质。开始写 A,B 性质。
11：05 欸不对，我 B 性质假了，怎么会有重复！上厕所，路上意识到可能要容斥去算。
11：20 好乱。先写 A 性质吧。
11：25 欸不是怎么暴力也假了？？？
11：30 盲目修改无果。冷静冷静。上厕所。先切换至 T3。
期间有一点小插曲，原因是我在复制文件的时候不知怎么的，任务栏就消失了。但是其他都能用，并且好像 windows 键无效了。询问监考后，监考也不知道怎么把任务栏调出来。然后我发现这样我就看不了时间了，可考场里也没有表。于是不得不重启电脑。
11：50 写了一个能过 n,m<=10 的爆搜。怀着侥幸心理测了一下 n<=18,m<=70，怎么也能跑出来？还只要 1s？
11：55 观察数据强度，似乎也不算弱的。但是我的输出怎么略小于答案？
12：00 哦哦哦，原来我的哈希的基数是 m+1。那咋改。
12：05 索性改成双模哈希。unordered_map 打标记。顺利通过样例三。预计得分 [8,32]。转回 T2。
12：20 做性质 A。反正 n,m<=6，索性大力乱来，写了一个 O(4^mC(m,n-1)n^2) 的垃圾做法。顺利通过 A 性质。
12：30 做性质 B。反正最小生成树是固定的，那就直接 3^(n-1) 枚举树上每条边的方向。非树边任意。复杂度 O(3^(n-1)*n^2)。顺利通过。
12：40 做性质 C。好像一般的 dp 和容斥都不好做啊，好像只能用矩阵树定理啊。我不会矩阵树定理啊！火大。
12：50 收拾文件，确保三个题都过了编译，防止和昨天一样出现不好的问题。
12：53 收拾东西。安静的看着倒计时，等待离场。
13：00 结束了！
预估 100+24+[8,32] = [132,156]pts。看起来 NOIP+省选如果真是 288+172+132，就有希望进队。希望 D1T3 能过编译。
接下来是幻想时间。如果我能会做矩阵树定理，那么我 D2T2 就能有 64pts 了，如果我 D1T3 调完了，就有 100pts 了。那这样就有 (100+20+100)+(100+64+[8,32]) = [392,416]pts 了，这个分数在山东差不多就是 A 队了吧。哈哈。
省选前夕我在 CF div2 中刚刚获得了 rk3 的好成绩，这说明确实是省选这几天是我状态的巅峰期。我感觉这是第一次刚好比赛碰上了我的巅峰期，基本上算是发挥出了我的最高水平吧。预计差不多在队线外一二名吧。
我从2021年3月1日开始接触信息学竞赛，这次省选刚好是我学 OI 四年整。总的来说，这次的省选，是我这整整四年以来打过的最痛快、最刺激、最舒服的比赛。另外，我今年是高一，因此还没有什么心理压力，毕竟这一场不是决定我命运的最后一战，这也是为什么我敢在 Day1 的最后半小时选择冲 T3 正解。并且如果今年进不了队，明年机会仍然很大。如果今年侥幸蹭进了队，我也很清楚我的实力并不能达到银牌水平，甚至省队和课内的双重压力会让我从3月到7月国赛这一段时间非常紧张和痛苦，而最终却只能获得一枚铜牌，还失去了明年省选的5分附加分。从这个角度来说，这也是我参加这次省选最好的结果吧，既发挥了自己的实力，也不会让自己因此获得更大的压力。所以，我对这次省选的结果非常满意！我也希望我能够在接下来到明年11月省赛的过程中再接再厉，保持这几天的最佳状态！
等待出分吧，别多想了。
upd on ???
民间估分是队线外第一名。
正式出分，288+(100+20+52)+(100+20+8) = 288+172+128，是队线内最后一名。成为了山东 B 队守门员。备战 NOI！