GDOI2025 游记

· · 生活·游记

打的很难受，但由于未来很长一段时间碰不了 oi 了，还是写一下吧。

noip

被这场比赛区分了。

day 0

没有试机环节，下午到了考场附近一个城中村的酒店，和朋友在一起打 gal 摆了一晚上。然后 10：30 就上床睡了，一直睡不着，算是每次考前的经典操作了。2 点多的时候又被外面的人吵醒了，到 4、5 点都没睡着/ll，结果只睡了几个小时。

day 1

8：27 发题，先总览了一遍，我草怎么两个计数。

8：30 仔细思考 T1，发现应该是个贪心，上下两个段肯定每次能匹配就匹配，不然放到以后匹配跟现在匹配没啥区别，为了方便写了个并查集，大概花了 20 分钟过大样例。

8：50 的时候开始想 T2，好像有点困难？不管了先写个 \Theta(n) dp 出来，然后判几个边界，过了小样例。然后又胡了一个矩乘上去，9：30 调完了过大样例。

然后看 T3，这啥玩意先跳了，直接看 T4。看到这个区间 lca 果断想到了模拟赛一道扫描线维护 lca 的东西，然后想了一会貌似是一个矩阵覆盖斜线求 max 啊，咋不会写这东西，开始鱼鱼蒸。

到了 10 点还是不会，还是回去看 T3 了，先手摸一下一个根的情况，在一个分叉点的时候只会先走父亲的边再依次走儿子的边，然后思考一下从一个下面的根开始的方案和上面有啥区别？好像就是可以先走若干个儿子的边再走父亲的边再继续走若干个儿子的边，然后先把这种情况叫做特殊状态。然后开始写写写，设 f_u 是根在 1 的方案，g_u 是根在 u 子树里的答案，写调到 11 点还是过不了大样例啊。红温了，去了个洗手间清醒一下，回来的时候发现好像还有一种情况是 h_u 是根在 u 子树里的答案但是没有特殊状态。12 点终于过大样例了。

继续鱼鱼 T4，先写了个 32 分，分别是暴力还有 k = r- l +1 的扫描线。然后看链，想了一会发现可以二分主席树求最大连续子段和，然后 12：30 左右写完了，好像测了个大样例没问题，就没管了。

12：40 开了 linux 测，发现怎么段错误？？开始红温了，最后 12：57 保存了代码也不知道为啥。出考场发现朋友 ak 了，T4 不是神秘扫描线，居然还能区间相邻 min 就对。段错误应该是没开栈空间，应该问题不大，回去摆了两天。

day +?

实在没忍住复现了一下 T4，结果交上去一测链挂完了？？为啥？？我草怎么最大连续字段和初始化是 0，应该是 -inf 才对，我草原来大样例是两个特殊性质在一起的，傻逼吧。直接 -[16,32]。

day ++？

出分了，只有 100+100+100+32=332，完全掉出了省队线，真的鱼鱼真了，差了 T4 的 12 分。后面两周直接逃课不去上学了。

GDOI

day0

中午和大家一起坐车到了佛山，只有半小时试机了，这学校咋这么破，感觉完全不如去年松山湖的好。到了机房也是座位好窄，感觉打的好难受。看了眼配置才 i3-7100，有点唐，但是居然有配置好的 vscode 和 cph，这算是唯一一个优点吧。

晚上去吃了麦的两个 1+1，然后点了个奶茶喝，回酒店打了一会板子后就摆了一晚上的 adofai。10：30 上床，忘记开空调了，又开始经典操作了，但是一直鱼鱼，到了 3 点还没睡着？？？后来迷迷糊糊可能睡了一会，6 点多又醒了，完全睡不着，脑子好迷糊。

day1

早上起来发现朋友也跟我一样，有点想骂这个酒店了，但确实是我的问题吧。

8：27 发题了，怎么还有 6s 题，好像是个数据结构，不管了先看 T1。先考虑一个点可以被取的条件，那我肯定让能取它的都取它，不能取的话设小于它的个数有 [L1,R1]，大于它的有 [L2,R2]，如果两个有交那直接取相等的就行，不然肯定左边的取最大值，右边的取最小值，判一下就好。然后离散化再上个差分就能搞定，不到半小时过了。

9 点多开始想 T2，怎么在考 dag 可达性啊，这个不是只能做 \dfrac{1}{w} 吗？为啥会出这种题。先打了个暴力，这时候旁边老哥开始发力了，开始砸键盘，又在用力敲笔，这时候就有点红温了。然后继续思考，好困好困好困，不行，去上个厕所洗了把脸。AB 性质咋做啊？为啥我这 4 分都不会，10 点钟还不会，只好去看 T3，先打了个暴力，貌似没啥思路。隔壁老哥又开始说话了，太几把唐了。

然后又回来想 T2，这肯定是个什么外面套层 a 的值域分块，然后 AB 性质的话可以直接对 a 的每块对 b 排序后 bitset，复杂度是 \dfrac{n}{B} \cdot \dfrac{(n+q)B}{w}，先写了这 4 分。那带修改的是不是就是加个时间轴分块啊？或者再套层 b 的分块，这能二分吗？算了一下好像带个 log 连 60000 都过不去啊，而且不会咋实现，急了急了急了。

感觉拿不到分了，就去手摸 T3 的树，这肯定是从逆排列考虑方便一点，那 1 肯定放 1 号节点当根吧，然后把这个线段的图画了出来，好像每个子树都是连续区间，把大样例复制过来 assert 了一下，是对的。那直接预处理每个子树里的节点编号最小值，对每个 u 的所有儿子和 u 按照 f_u 排序就对了。

又去浪费时间鱼鱼 T2，还是不会啊，就算写刚刚那个东西也来不及了吧？和它爆了，怎么旁边老哥还在唐啊/ll。

11：30 的时候只有 150 多分，感觉要爆了，于是回去继续想森林。又画个图发现应该贪心还是对的，但是有时候可能要做到一半开启一个新的树，这个好像可以只用堆模拟，每次找最小的那个树。写了一下发现不对，由于要做完一个树才能返回，是个栈状东西，改了一下堆只加入根就对了。

12：30 了，只有 176 分，感觉真的不能再拿更多分了，这个 B 题是不是真是简单题啊，但咋就是不会/ll。

出考场发现大家都过 B 了，没过的也有 88 分，鱼鱼了，队线应该要 200。

晚上好久没骑单车了，和朋友出去骑了 5 公里，回来好累，开了个空调 11 点就睡着了。

day2

睡了 7 个小时，状态比昨天好了点。

8：27 先看题，不好两个计数。这个 T1 咋出典题啊，肯定是按 t_i 排序去做，不然的话调整一下是不劣的。然后思考一下咋实现这个过程，发现每做一个点的时候会把若干个点都推到 b_i 的左边右边的一段，好像可以颜色段均摊去做。没有更好的写法了吗，非得模拟啊？好吧那由于相对位置不变，就写个 bit 维护每个点的当前位置，方便查询，然后上个 set 维护颜色段，调调调，9：50 才过，有点难受了，花了这么长时间。

看 T2，咋要求最小外向生成树，matrix-tree？不对应该不可能，因为这个边不一定存在。最小外向生成树真的存在多项式算法吗，我咋不会。先写个 12 分暴力，然后就是边不相同，可以直接 \Theta(n) dp，花半个多小时写了这两档。和原来最小生成树边权和相同有啥性质？就是每种边权的数量也有一样，那也就是从 1 开始加边，每次加完之后形成的联通块集合也一样，但是有啥用。

先看下 T3，这啥啊，没思路，还是回来 T2。想下 C 性质，欸我是不是可以缩点，每个 scc 肯定是每个点都可以作为根的，然后条件应该是这个 dag 只有一个 0 度点，求这个 scc 可以直接容斥，用 4^m 减去这个集合是由多个 scc 组成的 dag 方案数，直接上 dag 容斥就好。写写写，为啥不对啊？已经 11 点多了，开始红温了 。哦我草容斥系数不是 (-1)^{|S|+1}，是 scc 个数 +1，唐唐唐。欸还是不对，最后只有一个 0 度点咋求？？超级红温了。然后在草稿纸模拟 dag 容斥的过程，必须要刻画一个容斥使得最后恰好只有 1 个 0 度点才行，欸恰好只有一个？是不是可以尝试一下枚举一个 k，要求钦定的 0 度点个数至少是 k，然后还有个系数 (-1)^{k-1}，我草是对的，已经 12 点 20 了，赶紧写写写，12：30 过了 C 性质大样例，牛逼。但是是 n \cdot 3^n 的，我不会优化找两个集合直接的边个数啊？不管了 52 分也行，赶紧 T3 打了个搜子拿了 8 分，也没想着拿更多分了。给 T2 卡了卡常，怎么 14 都得跑 2.7s。

出考场发现今天忘开 O2 了，有点唐。估分两天加起来 336，当时还真以为有希望进队呢，哈哈哈。

下午回广州和几个朋友去吃了 200 块的火锅，爽。

回家后完全静不下心，打游戏也不知道打啥，为啥不给代码啊/ll。

到处问其他人成绩，发现好像有 20 个比我高的，爆了。

day3

早上请了一上午假，中午回班里上文化课了，怎么还感觉文化课有点意思，和朋友讨论了一下周末出去玩。

下午又开始疯狂约老师补课了，好日子过完了。

day4~5

第二天起床上早 7，我从来没觉得上文化课开心过。

上课听不懂啊，想睡觉，睡了一上午然后中午回机房刷 b 站，下午又继续睡。

晚上老师给我补课，感觉老师对我们很好，但是我还是学不下去啊啊啊。

day6

中午好像发数据了，怎么 recall 数据这么水，在食堂爆骂了出题人一顿，但其他人好像都把我当傻逼了哈哈。

下午直接逃课等特派员了，然后 3 点多终于拿到我们学校的了，居然挂了 -12 分，最后是 348，但是标准分只有 76.51 啊，队线好像是 79 多，怎么 GD 这么强啊啊啊啊啊啊啊啊。

听说可能 C,D 类会取消，不要啊我草。

看云斗测的榜好像有前 16，但是 noip 排名 20 多/ll/ll/ll。

真不能要了。

傍晚和同学去练游泳，怎么我 100m 都游不动了啊。回来点了个 kfc 疯狂星期四，结果一个小时都不送，补完课回来 21：30 才吃完饭，有点神金。

回宿舍看了 mujica 第 10 集，这写的啥啊这么生硬，我都不知道真是故意这样写的还是真有病。咋 mutsumi 突然没征兆的融合了。

day7

请假一天，然后早上来写游记了。