闪击GDOI——哇！图论是 M！V！P！

· · 生活·游记

本人定位：初二开学，2022 初赛没过，2023 S 和 NOIP 都没能一等，24 年高一，闪击 S 组 240，NOIP 272。

给自己来个实力评估就是和季风五五开。

Day -17

TPOI Round 1 & 省选加油赛。

A 题比较猎奇交了一万发才过。

B 题旁边同学发现了会 n\le20 就可以了，他写了神秘做法我观察到了一个神奇枚举，枚举哪一位前面都是最大值这一位取次大值后面的大小全都可以拉满。神秘 TLE 卡满 1.2s。\ 复杂度大抵是 O(TS(!^{-1})^2\log(S(!^{-1}))) 的，注意到 T 是十分之一的点跑了 120ms 可以卡常的，把一个调用数次的 set 的操作改成 sort 就卡过了。

同学神秘做法怎么过不了哦哦，欸你怎么取了取模后的最大值？把取最大值前的取模删掉过了。但是还是没有看懂神秘做法哦哦。

C 因为赶地铁没做，目测这是马拉车和组合数学板子。

B 是绿题？？我倒闭了。

等级分上 1700。

Day -15

VP 了 CF ER 174，E 调了一下午怎么调不出来啊？DeepSeekR1 给我调出来了。倒闭了。

Day -7

IAMOI Round #1。

赛前看到是难度绿到紫的 Div.1 哦哦，一眼盯出 A 题结论但是觉得没有绿题难度？对自己进行智力检测发现竟然没有问题？？24min 才过。

这个比赛时间很不牛了，把饭带到机房吃。

B 题也不是很牛的样子啊，中位数二分很典了，就是大小脑打结了卡了一会。

额怎么高三突然又要占用机房了，被赶走了呃呃。

C 是构造啊那不做了，打了暴力下播。

等级分 1800 了。

拿这场比赛测 DeepSeekR1 https://www.luogu.com.cn/article/moatnznh，100+0+40+12=152 哦哦。D 题疑似是被卡常了，B 题也是被它的奇葩人类智慧级猜结论整乐了。

Day -6

【LGR-216-Div.2】洛谷 2 月月赛 I & FTLOI Round 2。

A 又是比较神秘了。B 很贪心了，加个线段树秒了。

C 很神秘了，讨厌数学。

因为是数学本来想摆了，同学发现了是除以最大的质因数哦哦，那 $O(Tn)$ 秒了。 同学报的 Div.1，声称有了正解但是怎么 50 分啊。 打了 D 题暴力跑路了。这都能有 34 名？ 真的有些无聊了，花了四个小时让 DeepSeekR1 复现这场比赛，文本达六十四万字。 结果是 100+45+15+5=165 分，罚时 28.18min+116.58min+135.28min+213.33min=8.22h，在 1648 名正分参赛者中排 394 名。 ## Day -5 上午基础赛秒切前三题。D 题怎么长得这么模拟？那不打了跑了。 --- 去某大学打什么校队选拔赛，可能是能人都在校队里了所以感觉选手都很不牛。闪击 C 题这不是 BFS 板子吗为什么 WA 了两发？原来是出锅了读入地图结果两个字符之间有个空格。 四道可做题目测红橙黄绿，剩下一道很数学一道很猪国杀。 一个小时做完可做题，还得在座位上干坐四个小时。理解为什么让带纸质资料了。 又有小恐龙又有冲浪欸。还是可以的。 --- **Dino Hot News!** @[chenxi2009](https://www.luogu.com.cn/user/1020063) has got 4507 in [Dino](chrome://dino) and reached Tourist! [Share it!](chrome://dino) --- 但是和梦熊比赛撞了，失去了获得十分之一个原神小月卡的机会很不牛。 为什么是原神小月卡呢虽然我不玩原神但是我也不玩小粉兔和谷子而且我们学校化学竞赛省一好像都玩原神那就送他们好了。 ## Day -1 HBTSC PRE 2025 同步赛，进去一看怎么是 OI 赛制啊瞬间没动力了。时间也不是很好不打了。 ## Day 0 去石实。竟然有 Windows，还有 14 的 Dev-C++ 真是太棒了。测试 O2 一秒可以跑 $2.33\times10^8$ 次 long long 乘法取模赋值。 我会变成鹿蛇（loser）吗？ ## Day 1 进场。 T1 这个一眼是连续的啊，二分没了。哦我是堂食吧，`1 10 1 1 1 10 3 3` 就 Hack 这种想法了。那其实还是可以二分的，然后排序离散化差分前缀和把中间不可能为 $b_i$ 的数去掉就行了。一个半小时不到 A 了 T1，感觉胜利在望了。 T2 这时空一眼根号吧，但是我不会根号分治和分块啊，我唯一写过一次分块是在线段树的模板。性质一个也不会。 T3 怎么又是图又是排列的，排列和逆排列思考的时候一直在搞混，思考不了一点。性质一个也不会。 后面两题全是暴力。$100+20+8=128$。 从未如此期待过 CCF 能够脚造数据，但是我觉得 $O(Tnq)$ 不能够 6s 过三个 $6\times10^4$ 吧... 同学声称会 T2 没调出来，去吃饭的路上把自己 Hack 了。 晚上 ABC 打进 180 名上蓝名了。 ## Day 2 二进场。 这 T1 很一眼吧？作为一个经常水线段树和 CF、AT 贪心的人秒了。 还是太菜了，线段树二分调到一个小时才好。 T2 怎么又有图啊？要患上图论恐惧症了。 这个 A 明显暴力啊，写的时候没注意 $w_i=2$ 强写下去了，首先求出最小生成树包含各长度的边的个数，$O(4^m)$ 搜索每条边的情况，对应边个数先检查，然后挨个扒出 $n-1$ 条边查看是否构成最小外向生成树并且边权够小。这是我写过最累的一次暴力。 T2 B 才是全场最简单的性质吧，最小生成树唯一，正确的最小外向生成树一定是“来自”原图最小生成树的，搞个树形 DP，口胡了一个结论这棵树不能作为合法方案当且仅当不连通或有一个点有两条边不出。设计一个 $f_{i,j}$ 表示结点 $i$ 在向儿子的边里有 $j$ 条非出边的合法方案。 怎么过不了样例？发现 `1-->2<->3<--4` 是非法的，要把我口胡的结论中的点改成强连通分量。改一下状态转移就过了。$O(Tn)$ 放在这个数据范围感觉好浪费。就一个样例不知道对不对。 C 看着很容斥啊，那我一道容斥题都没写过又怎么样呢？40 分啊。 T3 估计是印证大纲中的“复杂动态规划”了，没有什么精力去思考性质了啊，考虑暴搜，用 $m+1$ 当模数把序列转换成数字，开 `map` 数出现的不同数字次数就好了。 手制极端数据测试，T1 跑 1.53s 应该没问题。 $100+24+8=132$。 同学跟我说 T3 $n\le18,m\le70$ 的答案好像不会很大啊，一想按我的方法 __int128 是可以装下哈希后的序列暴搜的，不过并不信任自己的 $O(n^2)$ 转移，这 24 分也不是我应得的吧。 总分：$100+20+8+100+24+8=260$。比较难平，性质只拿了 12 分。但是该拿的都拿了。 NOIP：$100+100+40+32=272$，按广东的方案 NOIP 占 30%，进不了队包的。 --- --- --- --- 逛游记，有 10 勾 D2T2 12 分。金勾 D2 $132$ 的不少。仿佛每一次比赛后洛谷的游记区就是 OIers 的停尸间。 Day -1 时逛到一个他校学弟的 NOIP [游记](https://www.luogu.com.cn/article/kx91ajdr)，似是联赛打烂将要退役的。顺自己的心意评论了几句。 我很喜欢打比赛，当把自己能拿的分都拿到的时候就有了满足感。我觉得我是出考场的人中最平静的一个。 也许不以分数作自己的目的是更好的态度。考前一周翻了翻 @[chenzhe](https://www.zhihu.com/people/GFCTS_554077074) 的知乎，也许瞥见了数年前信息学竞赛面貌的一角。天上朵朵乌云滴下的是什么？ 今年年初看完了一本不知名的网络小说，出于某些原因并没能完结。在开头将两句古诗拼凑到了一起： > 朝如青丝暮成雪，是非成败转头空。 逝者如斯，我也是要离开 OI 的。你为什么 OI 呢？ 有一种可能性很大的可能我并没有机会能进省队。 如果你不能 AK IOI，不能保送清北，不能进队，不能省一，过不了初赛，你会悔吗？ 如果你考前多学一种分块可以少丢 80 分，多打一道容斥/状压可以少丢 40 分，你悔吗？ recall 确是追忆，不如给过去的自己打个电话。 你悔吗？ \ \ \ \ 相信每一个当下的选择，都能让自己变得最好。OI 以一个爱好的身份与我共生，便不会因它没了对我升学的帮助就予以舍弃。在功利的思潮之下，每一个行动仿佛都要处心积虑，坚定的抉择弥足珍贵。 recall 吧，那不是幼稚和愚蠢，是偶然挣脱功利束缚的人的思想。走在路上，纵死不悔。 人是贪心的，只有当下才最真实。作茧自缚畏首畏尾，结果正有如 DeepSeekR1 在 [此题](https://www.luogu.com.cn/problem/P11761) 中做出过多的假设臆想，三次[得出了序列的最小值](https://www.luogu.com.cn/record/204043662)。 为什么图论是 MVP 呢？但是我们不以边权最小的无环连通子图勾连，不是被做最大匹配的边，也不是在各点间随波逐流的浪花。 总想去切最短路水题。图论能让你找到 A 市去 B 市的最小花费，却找不到你人生的最优构造。 活在当下，实在过去，才有未来。生活不是贪心问题，但这在线修改的交互题更不能够动态规划。 一如初中某本课本的序中所道：心中妙想口难言。 聊以拙文表吾心。 2025.3.5 ## Day 6 出分，$260$ 一分没多一分没挂。\ NOIP 也是这样的，结论是控好自己心态是关键啊。 还是输在学的太少，去年暑假才开始认真学。bitset 没学过断绝 D1T2 得分可能，甚至考后才第一次见到它并质疑这玩意复杂度保真吗。又因为认为 T2 一定比 T3 简单所以时间集中在思考 T2 性质。如果早两年学估计今年就要去 国家奥运会参赛队身份认证（NOI） 叱咤风云了。 难评的是 NOIP 和联合省选分数在自己学校都是第一。教练说这个成就足够了？但是我觉得 SZ 四大高中之一的最强者可能 D 都申请不了实在是太菜了。 神中进了一个，Day 2 中午在我们隔壁桌吃饭来着。 我想去 D 我想去 D 我想去 D。 有一说一 D1T2 放过 $O(Tnq)$ 那我大概知道出题人姓什么了。