联合省选 2021 游记

发布于 2021-04-11  4.41k 次阅读


在省选前一周才知道有资格参加省选(NOIP 刚好过线)。没做多少准备,省选知识点也才掌握了一点,可以说今年只是去玩玩吧,没有拿高分的希望。

因为实力不够,没啥好写的,就随便写点流水账。

Day -7 ~ -1

几乎每天都是:8:00~12:30 省选模拟赛,下午讲评,晚上订正。

每天用尽全力基本也只能拿些暴力分,手一滑就容易爆零垫底。每天几个小时的考试时间内大部分时间都在尝试想正解,但是一些比较巧的地方就总是想不到,之后就在与正解毫无关系的方向上做了大量思考,最终自然写不出正解。每道题基本也就只能拿到暴力分,跟那些写了几分钟就开始摸鱼的老哥一般来说是一个分数。

感觉实力还是差很多。

Day 0

学军紫金港校区。

上午就做了些考前的准备,稍微看了一两道题。下午出发,傍晚就到酒店。

我感觉酒店比前几次考试住的都要好。入住的时候似乎听前台说之前也有来打省选的学校来入住。

Day 1

吃早饭的时候发现和我们住一个酒店的竟然是绍一中,还没进赛场就感受到了极大的压力。

进去后我发现我这次的考场竟然就是我 CSP 的时候来的那个,监考官似乎也是同一批。

开卷,T1 看起来似乎可做,T2、T3 似乎都不大可做的样子。

那我想着先冲 T1 正解。最开始想着二分,排序后枚举左端点,然后二分最小的右端点以使得将区间外的硬币翻到反面后答案合法。

后来发现这不能同时兼顾单调性和合法答案。当然赛后听别人说似乎也有二分答案的做法,但是我这边想了一个双指针的做法。就是将所有硬币的正面和反面全部单独存储,共 $2 \times n$ 个数。将这些数从小到大排序后,枚举左端点 $l \in [1,2 \times n]$,同时固定一个最小的右端点 $r$ 使得 $l \sim r$ 中出现过所有硬币的某一面,且在区间内仅出现过反面的硬币的数量不超过 $m$。随着 $l$ 的增加,$r$ 显然单调不递减。双指针维护即可。

写完 T1 之后脑子可能有点抽风,觉得 T2、T3 的暴力可能不大好写。然后决定冲 T3 的正解,然而我花了两个半小时广度优先搜索了所有感觉可能的方法都没有接近它的正解,然后后面两题就没有分了。

出门后和几个同学交流了一下感觉我 T1 的做法应该是正确的。

Day 2

出门前分析了一下,从 CSP 到 NOIP 到联合省选,总体感觉就是题目在增加思维量,对算法的需求反而没有那么高了。所以今天的题大概也主要是思维题。

开卷,感觉都不大好做。挨个尝试思考每一题的正解但是都没想出啥比较可行的解法。

先是写了 T1 的 $25$ 分暴力模拟,然后 T2 写了 $O(n!)$ 的深搜 $60$ 分。回头想前两题的更高分数的做法但是不大想得出来,就开始想 T3。在尝试千万种方法后还是没有想出来,到后来感觉思维效率就不大高了,竟然没有想出来暴力怎么写,然后 T3 就没有写代码了。

期望 $100+85$ 分,算是跟我这个彩笔的真实实力相符吧,明年继续努力。


赛后总结


我缓慢吐出一串啊吧啊吧并不再想说话