2021全国统一省选游记

# 游尼玛记 算了还是写点东西吧。 ### Day -28 大概是四周前吧，我得知可以参加全国省选。NOIP 考 140 分以上的人都可以参加，~~压线进~~。 本来是打算每天晚上玩一个小时游戏的，被迫把它改成了 OI 时间。~~傻逼省选，毁我青春~~。 ### Day -21 只剩两周了，看题的频率更高了。（~~就是看题，不是刷题，我已经很久没有提交过任何一道题的代码了~~）随便找了几道最近几年的省选题（算不上弱省省选），竟然都有点想法，做出来的题还挺多的，~~甚至觉得自己进队有戏~~。 然后同一周，手感就突然变差了，看一道题不会一道题。本来是找紫题做做，结果后面就开始挑蓝题。~~我把这种现象归结于当天的 rp~~，但愿省选那天也能保持之前的状态。 周末去参加了北京队的省选集训。第一天的题还比较简单，第一题简单的倍增/树剖处理树上信息，第二题有点思考难度的组合 dp，第三题就是纯数据结构题了。第二天是邓神出题，~~都不会，考nm~~。%%%dmy 排名还不错。如果省选排名也是二十多的话，~~氪金也是可行的~~。 ### Day -14 周围也参加省选的人都停课去机房了，我还没去，~~反正上课也可以摸鱼~~。每天都会做几道题吧，有时候也会去 OI-wiki 上看点知识点。 周末是集训的第二周。第一天是大神hzk出题，第二天是 EI。个人觉得 EI 的题良心一点，最后一题太妙了。除此之外每天还有一个另外的讲座，第一天是非传统题，第二天是啥不重要，~~听不懂~~。 ### Day -7 这周有清明节假期，没到现场集训，题目倒是发下来了。 ### Day 0 省选的周末，也是这学期作业最多的一个周末。草。 ### Day 1 考试前 今天发生了贼有意思的事情。因为之前的集训九点才开始，我还以为省选也是九点开始。从家到考场大概 15 分钟，我本来想早一点到，~~顺便看看网有没有开~~，八点就走了。到那儿之后，门前的保安先让我戴口罩，然后问我有没有带一个防疫的承诺书什么的。 啥？ 然后保安后面的监考员递给我一张纸让我签字，就放我进去了。后来才知道，我之前没看过考试安排，根本不知道要带这个东西，幸亏带了身份证，否则真完了。关于为什么我没看过考试安排，~~这也是一个很长的故事~~。 进楼之后，从楼梯上下来一个监考员，对我说：“你是不是参加省选的？都开始了，还这么墨迹？” 啊？？？！ 赶紧看了一眼考试时间表。八点发题，八点半开考。现在是八点二十五。 好家伙，我赶紧飞奔到四层。进考场了，还差点把手机带进去，被监考员及时制止了；又把之前的草稿纸带进去，被没收然后警告了；打开电脑，下意识地打开 Guide 打头文件，又被警告了。~~今天怎么回事？！~~ 这就是省选第一天的故事。经历了这么多之后才看到题。~~比我经历更曲折的，欢迎在评论区留言~~。 ### Day 1 考试 打开题面的时候，已经可以开始编程了。$\text{T1}$ 是[卡牌游戏](https://www.luogu.com.cn/problem/P7514)，$\text{T2}$ 是[矩阵游戏](https://www.luogu.com.cn/problem/P7515)，$\text{T3}$ 是[图函数](https://www.luogu.com.cn/problem/P7516)。 这次的题面真就极短。先看 $\text{T1}$。题面是给定长度为 $n$ 的序列 $a,b$，对于每个下标 $i(1\le i\le n)$ 可以取 $a_i$ 或者 $b_i$，$b$ 只能取恰好 $k$ 个元素，求选取的 $n$ 个数极差的最小值。 看到极差，很快就想到钦定极值来做。令选取的数的最大值为 $M$，那么显然会有一个左端点 $m$ 作为最小值，使得 $m$ 不能再大了。注意到 $M$ 增长的时候 $m$ 是单调不减的，用一个双指针维护就可以了。没用基数排序，时间复杂度瓶颈在排序上，$O(n\log n)$。调了一会，最后发现~~没排序~~。半个小时就过了大样例。 再看 $\text{T2}$，题面很简洁，~~有点论文题的感觉了~~。注意到如果没有限制条件的话，可以钦定第一行第一列的数，然后就可以唯一地推出所有格子的数值。当将一个数 $+1$ 时，会发现它在的一行/一列会交替地 $+1$ 和 $-1$。这样特别像差分约束，但会出现类似 $x_i+x_j$ 的范围，而我只会 $x_i-x_j$。后来就没再继续想，打了个 $n,m\le 3$、$\min(n,m)\le 2$ 的情况。期望得分 $50$。 $\text{T3}$ 一下子就把我震住了，想了好久没啥思路。大概过了半个小时，突然发现可以换一种角度一起统计答案！对于两个点 $u,v$，如果它们能对答案做出贡献，那么一定不会经过编号比 $\min(u,v)$ 还要小的结点。考虑计算 $u,v$ 之间路径的边权最小值的最大值 $t$，那么它们就对 $h(G_{t-1}),...,h(G_1)$ 以及 $h(G)$ 有贡献。这个可以用类 $\text{Dijkstra}$ 的 $\text{BFS}$ 来算出，时间复杂度 $O(nm\log m)$，大概是 $44$ 分很稳，$80$ 分够呛。就按 $44$ 算吧。 最后的最高得分是 $100+50+44=194$。 ### Day 1 考后 首师大的饭还是那么好吃。~~吃饭的时候一直在斗地主~~ 后来到公共教室查看提交代码，很多人都说自己 $\text{T1}$ 没拍然后挂了，~~我也没敢拍~~。 发现 $\text{T2}$ 差分约束就是正解，只需要让一些值取反就可以了。QAQ ### Day 2 考试 第一天的得分还是超乎我的想象的。主要经验是心态极佳，第二天也要有这样的状态。这天八点之前我就进考场了，~~吸取昨天的经验~~。八点过后系统还没开放，一直等到了八点二十左右。 打开题面，$\text{T1}$ 是[宝石](https://www.luogu.com.cn/problem/P7518)，$\text{T2}$ 是[滚榜](https://www.luogu.com.cn/problem/P7519)，$\text{T3}$ 是[支配](https://www.luogu.com.cn/problem/P7520)。 $\text{T1}$ 一看就是数据结构题。想到先求 $\text{LCA}$，然后把查询分为 $u\to \text{LCA}$ 和 $\text{LCA}\to v$ 的过程。第一个过程可以用倍增求出最多可以取到哪一个宝石，后面就需要维护从一个固定的宝石开始能取多少。开始觉得贼简单，写了大概一百多行代码才发现自己想错了。一直没有看其它的题，时间一直拖到了十点半，才有一些想法。具体是每个点维护一个指针，指向父节点中第一个编号小于自己的点。然后可以用一个主席树 $O(\log m)$ 求出每个点到根节点的路径第一个 $P_i$ 的位置，然后就发现可以二分。时间复杂度 $O(n\log n\log m)$，最大的样例跑到了 $2$ 秒多。再加上 $\text{O2}$ 优化差不多。 $\text{T2}$ 和 $\text{T3}$ 时间都不多了。$\text{T3}$ 打了一个 $n\le 10$ 和 $m=n-1$ 的暴力，期望得分 $25$；$\text{T2}$ 写了一个 $O(n!)$ 的 $\text{DFS}$，期望得分 $60$。 最后的最佳得分是 $100+60+25=185$。 ### Day 2 考后 突！然！发！现！我 $\text{D1T2}$ 的 $n,m\le 3$ 部分分写错了！这样就挂到 $30$ 分了。555 ~~发现了一个新的小游戏：旋转大师~~ ### 总结 第一次参加 $\text{NOI}$ 省选，个人认为比 $\text{NOIP}2020$ 考的要好。总体来讲，正是那些之前认为根本不可能拿高分的比赛，最后能拿到出乎意料的分数；而那些目标很高的考试，反倒考得不好。我甚至觉得，去年的 $\text{CSP2019}$ 我考的比今年的 $\text{NOIP}$ 要好。**心态是很重要的，考前可以对自己有很高的目标，但不能被它打乱节奏。** 我自己有一个体会，就是在给别人讲题的时候，思考速度会变得很快。于是我在考场上就会上演“双重人格”——自己跟自己对话，~~这样做题可能会快一点~~。 知识点运用还是不熟练。之后需要更加注意每个算法的各种应用。再有就是思考能力的提升，~~这靠玄学~~。 回归初心，我入 OI 也许就是希望自己能够操纵电脑干一些大事情，或者是用于解决个人甚至社会的问题。我们都说，不忘初心，**取得竞赛的成就虽是梦想，但不是孤注一掷。** 在继续走下去的路上，希望我一直会记住这一点。 ## 总分 1. **赛后预估得分**：$100+50+44+100+60+25=379$ 2. **民间数据估分**：$90+40+48+85+60+10=333$ 3. **实际得分**：$100+50+44+100+60+10=364$