联合省选 2021 游记

· · 个人记录

今年我初三，来保龄了。

Day -2

今天上午没有考试，就准备自己做一做题。上午跟着论文做了几个网络流的题目，感觉挺神仙的。下午做了一下去年联合省选的前两题（怎么现在才做），希望今年考场上能够来一道类似 D1T2 的题目，当然前提是我见过类似的套路；D1T1 现在 \texttt {WA on line 40000}，不知道什么时候能够调出来，希望今年考场上不要有这种题。

七点左右的时候找到了错误：删除的时候把所有的温度相同的人都删了。但是现在只有 60 分，深刻地感受到了去年大常数选手的痛苦，然后开始卡常。

大概在八点四十的时候想到了一个好的方法卡过去了。

然后就开始看 D2T2，因为不知道倒建 Trie 的 trick，一直想到的只有 \mathcal O (n \log n \log v) 的辣鸡做法，然后去问了一下塔老师和仙人长就知道了，遂写了一发，但是没有调出来。

Day -1

早上来现在感觉挺好的，把昨天写的 D2T2 调出来了，原来我着急写代码会犯这么多 zz 错误。今天是最后一场模拟赛，希望能考得好一点。

今天预测分数：15 + 35 + 30 = 80。

实际分数：0 + 0 + 42 = 42。

无语。。。希望省选能够少犯一点 zz 错误吧 /kk

下午补了一下题。T1 好像是天天爱跑步的套路？T2 好像是制作菜品的套路？可惜我都没有做过 /kk

于是补完题之后晚上就把制作菜品想了一下，发现会了那个结论其实挺简单的。

Day 0

今天早上起来把制作菜品的代码写了，然后就准备把去年省选剩下的两道题补完。

发现这个 D2T1 其实挺水的，就是卡空间，不过解决方法也很简单。

D2T3 感觉有一点难度，但是前后两部分割裂的比较明显，多项式的部分我也没想出来，并且时间复杂度是想了一会儿才知道正确的。

然后颓了一会儿就开始打板子。

下午教练突然说要去试机，于是就去了，然后面到了 \texttt{\color{black}{K}\color{red}arry5307}，感觉很强。试机打了个 \exp 一遍过了，又打了个最小费用最大流但是没有调出来。

晚上好像时间不太够了，就搞了几个不太熟练的板子打。

Day 1

到的比较早，昨天晚上睡得早所以精神比较好。

快到的时候看到了车上的卡老师，到了之后就看到了 \texttt{\color{black}{a}\color{red}{fter\_the\_end}} ，于是和他谈笑风生。然后卡老师就过来找我签名，能在卡老师的书上留下我的名字也是一种荣幸吧。

然后就进考场。坐到座位上先打头和拍，然后打了 \rm NTT 和 \rm SAM（打两个十级的干什么？）就发密码了，然后就看题。

T1 看了一眼感觉比较可做，T2 看了一眼也感觉比较可做，T3 刚开始没太看懂，就先做前两题。

T1 刚开始看到 a_i 按照升序给出就开始往这方面想，然而并不能想出什么东西，于是就开始想枚举最大值，对于每个最大值求答案，然后就想到把所有牌按照正反面的最大值从小到大排序，然后钦定一个后缀为较小那一面，紧接的为较大那一面，以为不太确定所以先简单写了一个暴力，然后发现小样例调了调过了，第一个大样例也一遍过了，就觉得有点慌。再看一遍自己的代码，发现自己竟然有一个 i 和 j 写反了？这也能过大样例？？？？？看来这个样例跟没有一样。然后发现我的答案是分三部分求的，我枚举的是第三部分，前两个部分分别可以用树状数组二分和 ST 表优化，于是就把这两个东西写了，小样例一遍过了但是大样例一直 \texttt{WA}。后面看了十几分钟才看见有一个小于等于没打等号，改完之后两个大样例都过了，就开始拍。

刚开始我写的数据生成器是随机生成的，拍了几万组没有问题，但是我后来一想，把它改成了一个 2n 的排列，好家伙，第一组就给我 \texttt{WA} 了。于是我又一直各种改，最后好像能过拍了，就去看 T2，这个时候已经差不多十点多了，要抓紧时间。

刚看发现难点在于保证 a 的范围，没什么思路，于是去看部分分，先看的 m = 2。发现其实可以令第二列的数都为 0，因为没有影响，然后这一档分就会了。于是猜想有没有类似的结论，推了一下，还真有，所以这就是一个类似于差分约束的东西了。但是我早就忘记差分约束怎么写了啊。。。简单推了一下又想起来了，就开始写。写到一半发现没有那么简单，并且好像细节挺多的，还多测，宁是不会开 \texttt{Subtask} 吗？

这个时候看一眼拍：什么鬼哦，二十几万组又给我报错？又看了一下，发现是一个小细节错了，改了之后继续拍。

然后发现 T2 不会写了，就准备先把 T3 的暴力写了。琢磨了一会儿样例发现一个点也可以算作一个路径，就写了个 \mathcal O (n^5) 的暴力跑路。

但是这个时候已经十一点半了，我不能保证自己能把 T2 写出来，于是先把 T2 的第一档分随机化搞了一下，第二档分写了一下就继续写。但是很遗憾，还是没有调出来。

预计得分：[0, 100] + [30, 50] + 15 = [45, 165]。

出考场后感觉 T1 的做法五花八门，而且主流的做法是双指针，于是感觉自己不太稳。中午回来就水群、颓废。

好像人均 200+，就挺恐怖的，还听说 huhao lk djq 阿克了？那他们太强了。

下午看代码，突然发现自己 T2 有 30 分没写 puts("YES");，哈哈，白给 30 分。

很烦，下午什么也不想干，就一直在颓废。希望明天能考好一点。

晚上发现自己 T1 的树状数组完全是多余的，感觉自己好 sb 啊。

算了反正今年就是来玩玩的，不可能进队了，除非明天有奇迹。

Day2

来得比昨天晚了一点，然后第一个进了考场。还是打了头、拍和 \rm NTT, SAM，再次没有一点用。

发题发的很早。一看题面：没有非传统题，比较正常。T1 看起来比较可做，T2 数数题，T3 又是看起来很繁琐的题目。先看 T1 没什么思路，于是先看 T2。

刚开始把题目看成了存在多少个合法的 b 序列，震惊数数题居然没有模数？？？在那里想了好久才看到求的是最终排名的数量，于是立马发现 60 分是送的。之后考虑能不能状压什么的，但是思考无果，遂回去看 T1。

发现 T1 怎么想都想不出来。先把暴力写了做拍用，然后想怎么优化暴力。感觉把所有和树有关的东西都想了一边全部无果。

然后就去看第三题，把暴力打了。

然后就一直在三题时间反复横跳，感觉这里浪费了很多时间，实际上只是对 T2 的搜索做了一个无用的优化。

然后想一下第一题链的部分分，想到了一个类似于弹飞绵羊的分块做法，权衡了一下决定先把这个写了。但是写的过程中我逐渐发现这个东西的实现难度还不小，并且我发现自己不会 vector 的 lower_bound 了，于是又手写了一个。但是这个时候剩下的时间已经不多了，于是赶快加紧写代码，在 12:56 左右写完了，匆匆检查了文件就离场了。

出来以后发现大家都至少会 100 + 60 + 40，那我不是没了啊。

然后回去拍了一下 T1，发现挂了，那我人没了啊。

总结

总体来说不太满意。首先 \rm Day\ 1 是最大的失误，T1 写假了、T2 犯了 zz 错误。\rm Day\ 2 又没什么亮眼的表现，所以就只能垫底了 /kk

那就明年再来吧。我只有两个明年了，\rm CSP, NOIP, HNOI，再走一遍这条路时，我就已经是高中生了。

加油吧。