【AFO笔记】CSP-2019

By shy

那曾经美好的时光,

是我永远沉醉的梦想。

那奔腾燃烧的岁月

——永生难忘。

有时候我想,生命是一条奔腾不息的大河,你永远无法赶上。

有些遗憾,有些不甘,但从来都无可奈何。


在此之前,我想先谈谈别的东西。

也许到现在我才隐隐约约意识到已经是高中了吧,可我的学习状态大概还没有完全转变过来——这个过程很艰难,很痛苦。

几个月来我发现我依旧陷入与作业的斗争中,并且越陷越深。

也许是我还没有领悟到方法吧,也许是我还不够用心吧。

但是生活变化的太快了,让我真的感到困惑。

我是怀着这样的心情进入高中生活的。


也许是在那样的情况下,让我发自内心的承认的话,一定程度上我将信竞当成的一种逃避的工具——可以远离作业、考试(当然上课认真一向是我的基本原则)的工具。

我可以如此地坦白这点,但这并不代表我对信竞没有了热情。事实上,也许困惑是从学习开始转移到信竞上的——我究竟该如何向前。

去纪中集训了那么多次,当我看到那些巨佬的时候我的心情是复杂的——没有人不想成为他们,但事实是如此高不可攀——讲座听不懂,题目不会写。

我发现真的只有在比赛的时候我才能完全地发挥我的水平,但也仅仅就是触及到暴力的极限而已。我可以毫不谦逊地说基本上该拿到的暴力分我不会丢一分。然而并没有用,或许我能够比身边的人好一点点,但这离我真正的目标太远了,太远了。

每一天我不得不从那短的可怜的题解中绞尽脑汁去理解它的含义——我不得不承认我犯了一个大错,如果能再来一次,我一定会去找学长问solution,就算他讲的真的我听不懂。

但是当时我真的不敢,一是感到卑微,整个屋子的人听讲解都听懂了,就我还一知半解;二是我总是希望能够独立想出这道题,我太相信自己了。直到一个小时,两个小时过后,还没有理解思路,接着就是精神崩溃。事实上,也许想了不到半个小时,我就已经绝望了,接着就是一下午的颓废。现在看来,我所谓的“自尊”也许真的不重要吧,也许放下它,我就算不能有新的突破,也可以有多一点的收获吧。

但是生活永远不可能重来。或许,在这种学习状态下,我无论做什么,都是徒劳吧。这不是一个简单的问题,而是一连串的问题所引发的。我真正需要的,应该是全方面的调整吧。


你不知道该如何面对,

可你已经无路可退。

你要坚持到最后一刻

——为了让生活继续。

说一些比赛的事情吧。

Day1

开考后我大致看了一遍所有题目,今年的题目很长,非常长,废话和细节特多。

看完之后我把显然是水题的第一题手动模拟了一下,推了点规律,写了个递归切了。题目数据大,要开unsigned long long,然而当时忘记怎么读入了,于是写了一个读优,写完想起来读入好像是%llu(事实上没那么多事,cin读就行了),也懒得改,就直接过了,上了个厕所,此时正好过去一小时。


第二题是一颗括号树,统计树上的合法括号子串数。

我先写了n=200的dfs暴力,拿了20分再说,然后开始推性质。

推了大概二十分钟,终于得出了一个我现在都想不起来的做法,但是它需要保存一个栈记录当前的括号串,不巧的是这个栈的修改操作非常难还原(反正当时没想出来),我心一横就在dfs函数里直接开栈。

算了一下空间可能要n^2,最差只能过50%,10^5的链上数据爆炸概率极高。

测了一下样例,前两个都过了,但是第三个爆栈了,不知道怎么开大系统栈,干脆不测了(考完后发现这个样例特臭,其实没什么测的必要),反正pdf上写着开评测开大系统栈,心里默默祈祷今年这题CCF出的数据和去年普及T4一样水(事实上去年普及T4的大样例我也没过)。为了防止爆炸特地将n<=200的数据改成了暴力写法,想着再不济也有20分,心底踏实了点,继续肝第三题。


肝到第三题时时间只剩下50分钟了,比我预计的少了一点儿。

第三题是树上数。心里默默想着CCF是不是有毒,一天考2颗树

题目给的样例没有样例解释,我自信的想了一个贪心删边的做法,然后测了一下发现样例一FAKE了,一看题目,边居然要全删!

b乎一句话非常符合我当时的心情:“如果把这个全删换成选删,我这道题将秒杀,但是换不得。”

然后剩下十五分钟,好在平时全排列的暴力没少打,我直接丢了一个next_permutation,混上我的瞎搞做法,拿了10分跑路,还剩下了5分钟检查。


然后就是开花的Day2

第一题看到最后,看到那个熟悉的

998244353,我心里就有种骂街的冲动。

 

第一题的数据表,3/4的格子都是暴力,然后加起来只有……32。

经过一小时的艰苦思索,我终于不得不承认,这道题我连基本的DP都推不出来。

看着时间一分一秒的流过,我几乎怀疑了,我究竟是不是在考CSP,是不是我在做梦?

我知道历年的Day2第一题一般也是水题,我反反复复地翻看三道题,但没有发现一点水题的痕迹。我只能承认我真的写不出来,拿了32分继续写第二题。

第二题的数据范围看完我更加无语了,第一题取模第二题高精是想闹哪样?好在我也不需要考虑这些问题了,我写了一个n^3复杂度,36分的记搜,感觉写不出什么更好的了,就开始写第三题。

第三题是树的重心。为了响应国家生态文明建设,CCF举办了CSP2019树学竞赛。

考前复习了树的直径,树的DFS序,数据结构这一些东西,偏偏就是没有复习到树的重心,这就十分难受。没有办法,我只能拿了n^3暴力的20分。

于是乎Day2没有切掉任何一题,全部都只写了暴力。


最后成绩是100+100+10+32+36+25=303

其实考试时我觉得自己的策略算是十分完美了,毕竟求稳拿个省一还是挺重要的。

Day1第一题水题没话讲;第二题能A算是出乎我的意料,我本来只打算拿50的,谁知道CCF真的是拿脚造树的数据,两年都让我水过去了,也算是运气不错;第三题在洛谷它黑了,黑了……

Day2只打了暴力,看到b乎上一群大佬T1有64的,T2写n log n的,其实挺可惜的,但是技不如人就是技不如人吧。对我自己来说,最遗憾的应该是考前没有复习到树的重心(后来发现原来在书的前半部分,就在DFS序的后面),白丢了15分。

除此之外,比赛也没什么好后悔的了。工夫还是要花在平时最重要啊……


今年的比赛结束了,期末也快到了。这条路,继不继续,也依然是摆在我面前的一个难题。

但是这一切都不重要,

重要的是,曾经走过的这段时光,会让我们更加坚强。

我不会忘记,因为这是我永远的故乡。

——END.

发表评论

电子邮件地址不会被公开。 必填项已用*标注