CSP-S2019初赛游记

考得不好,不过(86.5)分应该勉强能进。


比赛前

比赛前的一个星期是有点慌,因为初赛是必须要复习的。初赛和复赛很不一样,复赛可以得一等奖,初赛不一定能考得很好。
最恶心的当然是那些计算机的“常识”……
所以我将绝大部分的时间花在背各种概念,像TCP/IP协议这样的。
还花了些时间复习排列组合,重新推了各种公式。
甚至连自然数幂和都复习了一遍。

去到了三鑫,比赛之前到处游玩。
三鑫的环境使人好压抑啊……我很庆幸自己初中在纪中。


比赛时

自然是从头做起。前面的题目基本上没有难度,而且计算机的常识也没有几题(所以我白复习了)?也没有什么需要用点脑子的排列组合的题。

然后就是读程序。
这个读程序跟以前不一样,因为现在的读程序真的不好强行模拟,一定要理解程序的意思。

第一个程序害得我花了好久才懂得它的意思,大概就是:将整个数列变成若干段连续不下降子序列,如果(i)在子序列尾,则([i+1,j])区间内小于等于(a_i),而且(j)最大;否则(j=i)

第二个程序特别简单,一看就懂。就是计算一个树中的不同路径条数(也就是(C_n^2))。然而当时自己脑补了一个路径压缩,于是挂了一道选择题;并且,题目实际上没有保证数据是合法的(一棵树),导致可能会有两个点本身就在同一个连通块中,于是我又错了一道判断题……
好憋屈啊……

然后第三个程序就让我很懵逼了。我只能强行模拟出程序大概怎么执行,但是无法理解出它的意思。
无奈之下,我只能硬刚。
首先第一个判断题是显然的,不解释……
然后就是第二个,刚了半天,刚不出来(接着去做了完善程序题)。
回来之后,第三个判断题举出了反例。
发现第四个判断题似乎很好证,好像是对的(然而实际上我错了……去掉“(+1)”就是对的),然后在这个基础上,推出了第二问是对的。
(于是两问都错了……)
接着是选择题。第一道选择题感觉是(0),当时感觉这显然是对的(实际上字符串长度不能为(0),不然怎么读入啊)
第二道选择题搞不出来(实际上是时间不够),凭直觉感觉(12)是对的,然后就选了。

接着是完善程序。第一个程序完全没有难度,随随便便就能(AK)了(还有,我总是想吐槽NOIPCSP-J/S的完善程序的时间复杂度。如果是我做的话,肯定会用个堆存所有满足条件的点)
第二题一开始没有看懂,心里有点急,因为距离结束已经不远了。然而这时,我自己推了个简单的DP式子,发现这个式子是可以状压的(我太菜了……我才发现它状压的方法)
于是我就比较顺利地填完前面四空,然后在最后一个空的时候,我就感觉到有点奇怪了。(D)选项后面的win应该改为win&1才对啊!
但是我还是选了这项,因为别的更不靠谱……
然而我在比赛之后才发现,原来winbool类型……
(话说其实这题可以打矩阵乘法的……但我就懒得吐槽了,毕竟CSP-J/S考状压就已经是一大进步)


比赛后

刚出来就是各种对答案,第二道读程序的两个傻逼错误搞得我心态崩了……
应该是有涂卡的缘故,成绩晚上就出来了。开始时成绩和估分不太一样,申诉了之后就改过来了。
只有(86.5)分……心态崩了
对于第三道读程序,现在我大概搞懂了它的意思。
(j)是后面第一个满足(pre_{i-1}<suf_j+1)(j),这也意味着(pre_{i-1}geq suf_{j-1}+1)
如果满足这个条件,(t)就是(s_{0..i-1}+s_{j-1..slen-1})的子串。
相当于去掉(s_{i..j-2})之后还是(t)的母串。
(ans)是去掉的子串的最长长度

一句话总结:我菜炸了

原文地址:https://www.cnblogs.com/jz-597/p/11715316.html