用心守护自己的存在

NOI2020-我的第一次全国竞赛经历

2020-08-22 19:45:07


今年我参加了 NOI2020。这是我第一次参加国赛,是一次可贵的经历。

总体评价:吸取了 WC 和 APIO 的教训,不断努力着让自己发挥出真正的实力。然而还是很糟糕。

Day 0

笔试。

开考之后才知道是用这个简陋在线测评网站考。考前自我感觉准备很充分,小黄鸭和 ouuan 的背笔试软件都用了,而且正确率 100%。

然而看到题目还是觉得好像超纲了(事实证明的确超纲了)。最终还是选错了多选题 47,原因是换了一种考法,原题是开考前能不能登陆系统翻阅试卷,答案否,这次多选开考前不能做什么。

听说刷过 uoj 的老哥都刷到了这道题,说明还是背笔试的时候要把题面背清楚,不能只背答案。

Day 1

模拟赛...正式赛。

或许是考前大量模拟赛的缘故,并未有多紧张。

WC,APIO。模拟赛。考钱教练反复叮嘱比赛策略的问题,zjc 分享了作为前辈的经验。

我努力着调整,反复告诫自己应做的事。

但是还是失败了。击败我的是老对手:时间。

前半小时,先把三道题都读一遍,思考一会。发现第三题是大毒瘤数据结构,第二题大致想出了个容斥暴力,大概 24~40 分。第一题看起来非常可做非常常规,所以最先做。

在草稿纸上写下了状态转移方程,看到 $T=10^9$,尝试如何改写成矩阵。(不幸或者幸运的是我把倍增也可以做 $10^9$ 忘了。)发现看起来非常矩阵又整不出来,开始“胡思乱想”,并分析矩阵究竟能不能做。甚至有想到“三维”的矩阵,当然没搞出来。我很清楚这种矩阵应当不会出现,或者至少它会“扁平化”。

后来我开始对每个 $w$ 考虑,因为 $w$ 很小。随后惊讶地发现仅考虑每一个 $w$,完全可以改写成矩阵乘向量形式。

so?我于是“发明”了矩阵套矩阵,并且花了十五分钟和半张草稿纸证明(其实是为了说服自己,因为如果敲出来发现不行更浪费时间)了它具有结合律可以快速幂。

敲完暴力敲矩阵套矩阵。代码很难写。

过了一刻钟我忽然发现这东西等价于分块矩阵,所以显然结合律成立。...

推翻重写。不幸的是由于过度追求正解,环的十分犯了非常明显的错误。 $k=0$ 的情况过了,说明应当是正解。然而剩下的 35 分大约是写挂了。我尝试调,因为它显然是正确的。但是没有成功。

此时时间大约只剩下一小时多了。我的本意确实是“写一题,打两题暴力”,而且我确实想出来了,也写出来了,但它挂了。

惨。

匆忙地写完T3暴力写T2,然而挂了,零分。

得知别人T2都写了几十分,T3都有时间写个主席树。心里有点难过,在寝室走了很久哈密顿回路。

查分的时候看到T1挂了环的十分,稍微有点惊讶。感谢T3出题人心情好, $O(n^2m)$ 的暴力额外送了我 12 分。另外出题人完全没用这个 T1 的思路,真 T1 做法我是当时很难想到的。

Day 2

有了 Day 1 的失败经验,我打算更换比赛策略。多拿到暴力分 $\rightarrow$ 一定要先做暴力!

还是先读一遍题目。看到 T2 题面时伸颈,侧目,惊叹,以为妙绝。看到 T3 觉得不会。

不幸地,全都卡住了,甚至部分分都没点思路。写了 T2 送的 16 分。

后来 T1 写了个贪心。当时的思路是完全偏离的,和正解不搭边,但是贪心确实是对的。拿了 35 分。

T3 整个没写。区区 4 档部分分,一点暴力分都没。这让我想到一些恐怖的模拟赛。

考完出来听说别人 T1 至少 70 分,重要的是思路对了。T2 都写了四十几分的“暴力”。心里还是很难受。

总结

Day 1 这个策略呢,是对还是不对?暴力与正解的取舍一直很难,尤其是当正解非常正确就是调不出来,为此却错失了 10+40 分,没有拿到银。如果真的调出来了就是 45 分,也是银。但是我现在只有铜。

Day 2 真的是能力不足了。处理新事物的能力还略低。

这不由得让我想到 zjc 的话:这一年里主要提升的不是做多难的题,而是更快地打完暴力想正解。我从各位大佬身上也看到了自己写代码速度过于慢。而慢有一点是思路有时不够清晰。

在接下来的一年里,我该做些什么?或许是把鸽了一年的题写完,无论它多简单。或许是打很多的 CF 提升思维和代码速度,虽然有点晚。每写一道题都先把思路清晰地写下来。不管怎么样,更大幅度地提升码力,包括速度,是解决暴力与正解的取舍问题的最优解。