联合省选/ZJOI 2021 划水记

转载与本人 [cnblog](https://www.cnblogs.com/-Wallace-/p/tour-zjoi2021.html) 下饭体验选手的搞笑记录（ 反正是体验赛，就当玩一玩咯 ### Day 1 开题！发现 T1 大概是一眼题，似乎比较可做？开始思考贪心之类的东西，二分答案？双指针？ 最后想了想钦定最大值，最大化最小值似乎可以整一波，于是胡了一个看起来很真的带悔贪心…… 大概是钦定 $a_i$ 最大，然后后面的只能全翻，前面每次试着翻最小的，如果翻了反而开倒车那就锁死了。一开始没想好用什么数据结构维护前面的东西，写了个最万能的 ```std::map```，跑了 $5\times 10^5$ 的大样例要两三秒，慢死了。发现可以 ```std::priority_queue```，啪的一下就换掉了，很快啊，速度快了一半！在考场这样的老爷机跑一秒多评测少爷机加 ```-O2``` 应该挺稳。（赛后听说 ```scanf``` + ```std::sort``` $10^6$ 个数就要 3s，那应该挺稳。） 不过 $a_i$ 不一定最大，可能是 $b_i$，然后我寻思这本质相同啊，把 $a,b$ 交换一下，$m$ 变成 $n-m$，跑了一下过不去大样例……过了几分钟我醒悟过来发现 $a,b$ 的地位并不相同！也就是说我还要写一个贪心，而且不一定可以贪…… 一看时间：2 hours elapsed…… 草这时间咋过去的？！！这么长时间没切签到题？！于是开始胡思乱想，在纸上乱写了半小时弃掉了，但这种分怎么能弃呢？小编也很惊讶，但事实就是这样。于是最后也交了一个答案集合中最大值为 $a$ 才能过了沙雕程序。不过在 $n$ 小的时候搞了个数据分治，前 $20$ pts 应该能保住。赛后又发现大样例跟没有一样， FST 预定。 之后觉得自己更 sb 了：既然我的算法只能钦定 $a$，那么为什么不写钦定最小值？那只有答案集合里 $b$ 同为最大最小值才会挂…… 看了 T2，感觉非常乱搞或者非常高明就直接考虑骗分，然后骗了个寂寞，最后得到了 $0$ pts 的好成绩。我也不知道我当时怎么想的，出考场发现是差分约束人都吓傻了。 T3？这种鬼畜图论一看就是什么高明结论，一看就不会，花半个多小时写完了 $16$ pts 暴力。 出考场发现自己被打爆了，大概 $50+0+16$？~~如果数据和大样例一样水的话当然是能 A 掉 T1 的~~ Day1 都没有套路题，赌一波 Day2 一道数据结构，一道字符串，一道数数。 希望 Day2 别那么炸 ### Day 2 没赌上，字符串无了（悲），数数也没了（狂喜）。 一开题，T1 好像可以点分治？大概先离线，将询问根据分治中心拆成两段，后半段可以二分答案，然后这样一下，那样一下，就做完啦！这么快搞出一个点分做法是因为之前 XJ 模拟赛 xza 放过一个 Spy Game，是这个题的严格加强，但是基本不可能写的出来。不过这个题应该会好写很多？不如试试，至少比暴力强。 于是我 5 分钟就胡出了做法（~~指“这样一下，那样一下”~~），开始敲击键盘……然而这只是毒瘤的开始。由于我很多细节没有考虑好，写的很屎，代码里一共有六七个 DFS 函数，活活将代码撑到了 250 行，最后两个小时才写完 /tuu。写完了，还有调呢！于是又花了大把时间调试……没插件的 VS Code 不能单步调试很难受，甚至一度打开 Dev-C++ 只为调试，然而并没有实质性作用。 然后终于过了小样例，顺手过了中样例，感觉中大奖了。然后大样例……跑不出来了？看到输出文件一片空白，我陷入了沉思。哦原来没开栈，一测发现……为什么总是时不时不答案小一啊？！我百思不得其解，开始瞎改，东边加个一，西边加个 max，最后发现二分答案左边界加一就过了，小编也很惊讶，但事实就是这样。由于我偷懒在分治中放了个 ```std::map```，大概是两 $\log$，实际上完全可以 $O(n\log n+q\log m)$ 的，反正跑得快就扔了。重构过的考场思路代码（用了 C++11 实现，~~主要是没有 C++11 建筑美荡然无存~~）：https://files.cnblogs.com/files/-Wallace-/gem.zip 挑战一小时写 T2 T3……的暴力！最后只写了 T2，原因是我过于慌张使得每 20 min 固定看错一次题：啊要求的不是方案数是结果数啊？啊 $b$ 单调不增的啊？所幸最后还是调出来了，大概是阶乘级别的，不知道 $50$ pts 有没有。搞笑的是我用了 ```std::set<std::vector<int> >``` 这种 sb 东西用来判重，然而实际上我的搜索方式根本不会重，估计有些点本来能过现在没戏了。 T3 一看就是支配树板子，题面里都有“支配点”了还能不是吗？！还有省选怎么考板题啊什么玩意。。。算了反正我不会，而暴力又不好写，这题……不要也罢！瞬间感觉我 $3.5$ 小时在 T1 上的付出血赚不亏 ~~然后 FST 了~~ 估分 $100+50+0$，比前一天能看一点，但是好像还是被吊打了，一问一个一百五，说是有手就行，那打扰了我没手（ T1 有人写平方，有人分块 $0.7 \text s$ 过了大样例，有人写什么倍增树剖主席树，一听就不知道比我的垃圾点分治高到哪里去了。不过据说有人赛时没调出来的，要么就写了三个多小时的，大概跟我一样写屎做法。Flying 的并查集做法也没调出来，默哀。T2 cly 说是区域赛原题，devinw 说赛场上 ZJU 人几分钟就发题解了，那这也太不行了。 最后发现 D2T1 可能会挂，而且非常鬼畜，详见：https://strncmp.blog.luogu.org/solution-p7518 ### Final - Day 1 :$100+0+16=116$ - Day 2 :$85+40+0=125$ 想不到吧 D1T1 官方数据水到爆炸我直接过了。据说 zk 场上指数级暴力 + 乱搞直接就过了，真是令人 ~~下饭~~ 喷饭。 但是 D2T1 挂了三个点，不出意料挂在前面的点了；D2T2 只拿了 $40$，发现把那个 sb 去重删掉就 $45$ 了，直接自闭。 ~~所以 D1T1 多水的分在 D2 挂回来了？~~ 官方数据欢乐多又多