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} 是卡牌游戏，\text{T2} 是矩阵游戏，\text{T3} 是图函数。

这次的题面真就极短。先看 \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。

最后的最高得分是 $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

  1. 民间数据估分：90+40+48+85+60+10=333

  2. 实际得分：100+50+44+100+60+10=364