联合省选2021游记

· · 个人记录

自己打了这么多年OI，也差不多要开始写写游记记录一下了，以后退役了好看看怀念一下。

week -3

北京省选集训，首师大附中伙食好评。

然后集训一直在打假赛，各种sb错误挂分，每场都被别人吊着打。

week -2

继续北京集训，咕了 NOI Online。

结果集训还是不太行，甚至看错题想了半天！十分拉胯。平均 rank 10 以上（

week -1

清明假期。开始最后的训练。

day 0

最后一天，EI 来了学校，说他要过体育会考！Ran（教练）啪的一下站起来了，很快啊，提议我们去操场跑圈。于是我和 LiM_817 和 EI 和教练就去跑了个一千米。迫真信息竞赛

EI 跑了 4:1x ，我跑了 3:5x（具体忘了），看来 EI 稳过体育会考！我好久没运动了果然身体素质不行了。

总之最后一天就放空自我，几乎啥东西没看。

day 1

好好睡了一觉，早早来到考场。

BJ 用 NOI Linux。 而且有一个类似 OJ 的提交框的那种程序提交平台。不用担心啥子文件夹之类的乱七八糟的。不过坏处是得在最后一秒前点提交按钮，不是 Ctrl-S 了就算交上的。对于最后一秒发现错误的选手不太友好，但之前 NOIp 用的时候我没有被坑。希望这次人没事。

发压缩包， card matrix graph。

card 读入量略大，但是所有的题都不到 20MB，应该不用打快读了，好诶。matrix 没有大样例，感觉有点毒瘤。

发密码，看题。

card 一眼看到 a_i 升序，立马想到 CSP2020 贪吃蛇，吓得我直接想线性算法，不过冷静了一下觉得小常数单log可过。

matrix 和 graph 一眼不会，先写 card

结果我究极傻逼写了个基于线段树的做法（鬼知道我咋想的），想加写加拍足足用了一个多小时快俩小时，感觉不太好。

然后开 matrix，我想到确定了最后一行最后一列就可以确定所有的，然后设最后一行为 a_i 最后一列 b_i 右下角 c 推了个式子，发现每个格子 (i,j) 就是关于 \pm a_i \pm b_j \pm c 的一个区间限制。看上去像是个差分约束，但是有三个变量，于是就懵逼了。至死不会。

于是写了个 m=2 和随机化贪心。

然后 graph。还剩一个小时多，刚开始啥都不会，写了个我也忘了是啥复杂度的暴力。写着写着突然意识到可以强连通等价于把前面的点全部删掉还强连通。立刻激动的写了个显然的 O(nm)，以为这题过了。然后冷静了一下分析了一下常数觉得不太行，但只剩下几分钟了，过了大样例，就弃疗了。

期望 100+[30,100]+80。

day1 test

测民间数据，有一个数据我 T1 WA 了几个，不过过会又听说这个数据有些地方造错了，其他数据测出来没有问题。我就当它过了吧（雾）

T2 好像我随机化贪心 n,m\leq 3 有理有据，后面的因为随机次数太多了 TLE 了，看上去能拿 50

T3 不出所料，80

民间 100(?)+50+80=230

day 2

day1 感觉发挥不太行，所以晚上一直惦记着没睡着，好像还看了个啥番一直到很晚（记忆模糊），所以第二天精神状态不太行，早上多喝了点咖啡。

刚开始那个系统一直没法登录，所以到开考前十分钟左右才看到压缩包。

gem ranklist dominator

样例大小没看出啥特别的。

发密码，看题。

一看 gem。集训的时候教练给初三同学考了一道树上路径单调栈长度查询，而且我一年前在校内模拟赛里也做过它，我估摸一下这两题四舍五入就是同一道题，感觉我校选手要全部把它过了。Ran 押题大师。

开场直接开始默写（大雾），1h 连写带拍搞定。

然后看 ranklist，一眼看出了贪心的结论，写了个 n! ，想到了个 2^nn^2m^2 状压，发现没快多少，就暂时不会了。

于是去看 dominator，由于我对支配树略有耳闻，而且去年联合省选 T3 有一个保序回归科技题，于是我坚信这道题正解一定要写我不会的支配树，所以花了一段时间想到了 O(n^2(n+q)/\omega) 加树的 75 然后写完和暴力拍上，就跑路了。此时还剩一个多小时。

然后想 ranklist，突然想到状压可以去掉一维 m，发现可过，果断写，过样例，拍上。此时还剩30分钟。

然后我就去想 dominator 了，想着想着突然发现我好像会 O(n(n+q)) 了（不需要支配树的那种），然后定睛一看发现还剩 10min，肯定写不完了，于是懊悔地躺平，打 emacs 的 tetris，然后思考我为啥当时一口咬定需要写支配树，然后发现自己 tetris 也打不好，属实是个 sb。

考场电脑不错，到最后同时拍仨程序同时再加上我玩 tetris 丝毫不卡，但是我隐隐感觉到腿下面源源不断散发出一股热量（

期望 100+100+75

day2 test

民间数据没挂分 100+100+75=275

意料之中，毕竟考场上的电脑给我辛勤的对拍了那么多组，心疼电脑 1ns。

test

民间 100+50+80+100+100+75=505

拿到了看上去强度还行的神必民间数据在 NOI Linux 下测了一下 BJ 所有人，rank 3，orz xtq，orz cys，感觉这次还行吧，但今年 NOI 的话果然还是得再多练练。感觉现在完全不熟练。

end

官方数据没挂分，不出所料进了A队，但我还是菜死了。