GDOI省选游记

· · 生活·游记

GDOI省选游记

3.3

开始写并脱产。

开始写 2026 省选赛前模板赛。

3.4

上午和kwQin和Clx_Holmes打duel，拼尽全力无法战胜，切了一道1800神秘图论，一道2300神秘四维dp。

之后和kwQin疯狂duel，并把幸运数字补了。

3.5

依旧和kwQin疯狂duel，又切了一道蓝dp，爽了。

3.6

上午把推箱子调过了。

下午去纪中试机，不得不说纪中环境真的好我们学校是什么lj，但机子挺慢的，打了几个板子就走了。

晚上和朋友玩干瞪眼、德扑真的太好玩了。

3.7（比赛日1）

早上定的闹钟声音太小，还是烟花声把我吵醒的不然就可能迟到了。

进考场不让带水？好吧又让带了hyw。

昨天试机键盘接触不良，今天怎么还这样？

8：30开题，把题都看了一遍，决定倒序开题骗分。

先看T3，把简单的暴力+ m=1 15分拿了，然后思考 m=2。注意到这题实际上可以把序列看成一个环，每次合并相邻两个数，不过有位置限制。开始暴力分讨，直接暴力枚举第一个可以对应 B 中的数的区间，之后再判断最终是否存在两边无法合并或位置相反的情况。用20分钟搞懂checker.cpp怎么用后发现没过大样例，于是注意到数据范围比较小，直接把所有区间全部尝试一遍，然后就过了，此时是大概10:00。（240行代码才24分阴不阴啊）

然后决定直接看T1，尝试是否能切。题目背景是不是再致敬追忆。先认真思考然后决定把暴力打了先，接下来胡了个 O(n) 做法？写了，第二个样例过不去，发现假了，有想了想，想到了NTT，但是不太能用的样子，遂放弃，把链性质打了就去看T2。此时大概11:00。

T2用时10分钟看懂题目，然后依旧把暴力打了，接下来思考B性质。观察大样例，似乎是用1把0隔开来计数，遂每次选取能选的最多的0，然后用1分割，但是没过大样例，发现取尽量大的不是最优的，遂写了个背包状物，过了。然后思考C性质，依旧观察大样例，发现似乎是直接往两边补0，然后调了1h计数，发现没过，发现可以先+1再补0，遂写了个 O(3000\times3000\times3000) 的暴力枚举判断，反正跑不满，剪枝一下就行。

然后罚坐1h。

Day1估分：28+45+24=97 跟我数学一个分

出来问一圈发现我咋似乎是我们学校rk1？依旧骗分仙人

晚上完德扑，一把爽赚34点。

玩4399神秘小游戏，太好玩了。

3.8（比赛日2）

早上把闹钟调到最大声，终于准时醒了。

8:30开题（键盘终于没坏了）。

看到T1是交互？wtf？省选出交互？我除了二分以外就没写过交互

准备先写T1部分分，依旧先把暴力打了。思考 n\le10^2 咋写，想到了每次二分下一个数，然后把不重要的数丢进一个数组单独处理，最差大概是 n \log_2 n，但由于写的太屎调了2h才调出来。此时我忽然发现我T1才拿了二十多分,非常慌张，于是赶紧去开T2。仔细研读题面后发现连暴力都不会。于是开T3，发现题面都看不懂，遂决定死磕T1。注意到A性质只需要把 query(0,i) 问一遍再用相同方式二分即可。B性质先二分0的位置，然后暴力往左右扩展即可。C性质用二分应该能过。然后又想了一个神秘的 \log_2 n+1.5n 的暴力扩展写法，写完已经12:30了。之后开始罚坐，啥也不会。

Day2估分：80+0+0=80

靠不是怎么n个人过了T1，前缀min等于后缀mex为啥我没看出来？这不炸了？