CSP-S 2019游记

写在前面 & Day0

高一开学开始学的OI,一直感觉高二的NOIP离自己很遥远,回想起之前还能和学长请教那些网络流和高级数据结构,如今我已经到了高二,变成了需要解答高一学弟疑问的学长。高二的联赛就意味着一些同学的退役,能留下来冲刺省队的只有一部分。

我也不能说我一定可以进入省队,但是毕竟有这个愿望。于是,目标就这样定下来了。联赛如果达不到400分的话就退役。因为假如不到400,省选的容错率就特别低。与其再努力半个学期冲省选然后落得失败,不如早日投入到文化课中。总之,就以400分为目标,放手一搏吧。

周五,给高一的同学讲了讲去年NOIP的场面以及一些可能会耽误考试或者影响心情的事情,说了点经验和注意事项,让他们放开打,反正高二还有一次机会。

去试机,军工的校园特别大,温度已经来到了零下15度以下,走得很冷。来到试机的机房,简单配了下Emacs,打了个Splay区间反转热热身。还行,键盘很顺手,不想去年的键盘,backspace特别短,总按不到。

老师说最后一天让我们玩玩游戏啥的放松放松,但是我怕自己太颓,就一边看境界的彼方一边打了一遍KDT三维偏序一遍LCT模板,反正那番看过,边打边看没啥影响挺轻松的。高一问了一些之前模拟赛的题,挨个答了一遍。在食堂吃完晚饭又打了一个点左右就回家了,寻思早点睡,比赛状态能好点。

回到家还是有一些焦虑的。虽然那些LCT,KDT,Dinic什么的都在心中烂熟,但还是免不了担心看到简单题一时想偏蒙住。

Day1

外面温度逐渐逼近零下20度,冻得脸难受。

来到考场,配置Emacs,等待发题。

8:35拿到题,先扫一遍三道题。我去,T1题面就这么长,但是T1不可能难。看完题,想了几分钟怎么写,写了个返回string的递归,带着文件读写测了大样例,没锅,大概9:00左右。这题本来就是个小模拟,也没法写暴力对拍,估计也出不了什么差错,就这么过了吧。

接下来看T2,大体看了一遍。开始往差分和主席树上想,再看一遍感觉应该是一边在树上走路,一边用树状数组之类的维护写什么。在纸上简单模拟了下样例,发现拿一个数组存以$u$为底端的,左括号-右括号=$i$的链的个数就OK了。大约10:00左右打完,没过样例。看时间还挺充裕,输出变量调了一段时间,大样例都过了。写了个$n^3$的暴力,写了个生成器,跑$n = 100$的数据。Linux的对拍弄了半天才弄明白,写了个对拍程序,一样输出YES,不一样输出NO然后退出。开始跑对拍,拍了大约5000组数据,没NO过,这道题就告一段落。一看时间,已经快11点了,看来T3不可能有时间推正解了,打打部分分吧。

样例给的还不错,有链和菊花图。脑补了一个贪心思路,从$1$循环到$n$,找这个数字可以到达的编号最小的点,然后一路断边挪过去。这题肯定不这么简单,但是链应该差不多。拿着样例试了半天,怎么看怎么不对劲。后来发现,输入输出的是数字所在的节点编号而不是节点上的数字。改过来,手摸过了。打完链和爆搜不过样例,各种出锅,当时心情就已经有点急躁。没办法,还得老老实实输出过程变量。大约11:45左右调出来。然后推菊花图。推完菊花图手摸过了样例写了一点发现已经11:55了,只能选择放弃。也没有时间拿爆搜拍链了,心里有点没底,暂且算拿了35分吧。

最后10分钟,带着文件读写拿三个代码跑了样例,感觉235应该是个大众分,Day1算是没有大失误吧。

出了考场,问了几个同学,基本都在200上下,问题出在各个地方。txz打了链没时间写爆搜,225,zxs想出链没写完,210,意外的是退役了一个学期的wsc竟然写了235分。在师附训练的初四的hxx想出T3得$n^3$写法,要是写过去应该50分到手,但是写挂了。gqs写了235分。

高一好像普遍在100上下。T1有人不会。T2会的只有xza,具体写的怎么样我也不知道。反正他们高二还有一次机会,高一拿个二三等的奖状就很有面儿了。

看来Day1题目感觉整体偏难,不然像txz、zxs、gqs这些大佬不可能和我这种小蒟蒻分数差不多,高一也不至于都在吐槽比之前做的真题要难。

到五楼认证代码,ftp一直出锅,最后把压缩包换成文件夹,还是没法拷到桌面上。直接打开看,只能用IE看,没有乱码,是自己写的,应该没啥问题了。

出军工,坐上公交车,人不多,坐在上面就睡着了。心里担心的还是自己T3没拍过的链。万一10分小数据点里有链,我的程序会跑链的解法,要是链锅了有可能T3一分都拿不到。

最终不出意外的话Day1 100+100+35=235分

Day2

坐在机器前心如止水,既然是Day2,暴力分拿全就好。

发题,扫一遍三道题,What dick stuff? ——先看暴力吧。

T1,用我刚刚N5水平的日语联系前后文读出Emiya显然是卫宫(读出这有啥用),$m = 3$和$m = 2$占$64$分,$n$还贼小,诱人的暴力分,直接无脑$n ^ 2$和$n ^ 4$暴力动规,拍过$n = 3$的大样例,看眼表花了不到1h,赶紧进入下一题。

T2,竟然考高精?还好高精就一个点,不会也罢。——那前面的分怎么搞啊?复杂度显然要求是$O(n)$的,题里肯定有某种单调性,看出来之后就可以套斜率优化/单调队列/单调栈/双指针,但是还是看不出来。不管了,写个$n ^ 3$暴力区间动规,看数据应该是$32$分。这题先放着。

T3,$n ^ 2$的暴力和链的$O(n)$白给,先收入囊中。完全二叉树如果没有猜错的话,两个树的重心就是正常画出二叉树后两棵树的根,大的那棵树还可能多一个没被切的那半边的根,也就是根的其中一个儿子。尝试着写了下,可能有点慌,写了半天判度和$size$都没判出来原树的根是谁,然后也不知道怎么转化成堆式存储。去趟厕所冷静冷静,厕所里一股烟味,不想多呆,转念一想,D2T3拿$55$分也罢,说不定前面还有我能拿的暴力分。

剩的时间还有将近1h,反回来看T1。显然正解的大体思路应该是把全部方案搞出来,然后对每个菜品斥掉它为众数且超过一半的方案数,因为超过一半的众数只能有一个。但是设计了半天状态,草纸上划拉了半天,还是想不出怎么动规。算了,看T2。T2的单调性找了半天也找不出来,对大的数据点写了个随缘贪心,就是从左往右扫,$\geq$上一个就切。然后再扫一遍,如果能分给上一段仍合法就分出去。反正俩小样例全能过,能骗多少分就看造化了。

最后检查了下文件,带着文件又跑了一遍样例,发现T2打麻烦了,并且复杂度还更劣,是$n ^ 2 \times \sum a$,应该是$24$分。不改了,考试最后十分钟改代码凶多吉少,盘算一遍$100+100+35+64+24+55=378$,冲省选没啥希望了。今年也就这样了,回去好好学文化课。

出考场,合影,抱着自闭的心态和同学交流交流,发现自己D1T1开的不是ULL而是LL,可能死成80分,D1T3链的贪心不对,并且可能让10分的爆搜也得不到,最坏可能0分,所以我的分数应该是333到378之间波动,最大可能是350左右。想到去年SuperJvRuo学长因为多测没清空打了360退役了,我感觉我这次也会退役。

gqs和hxx全都400往上,我更自闭了。

事有峰回路转。

问了下来参加CSP当娱乐赛的高三大佬,说这次题太难了,350在全省高一高二当中可能是前十。附中的老师也说,HL的省一分数线可能会到200分以下。

算了不管了,周一还要上学。

Day3

上午的文化课听得还挺投入的,可能是一场绝望的CSP浇灭了自己浮躁的心态。中午来到机房,程序已经下发,在东师的OJ、洛谷、csp.ac三个OJ上测了民间数据,两个348分,一个343分。晚上吃完饭遇见partychicken学长问了下,这分冲省选应该没啥大问题了。

zxs的D2算是翻盘了,洛谷上测总分408,尖刀班的大佬就是不一样。

高二几个兄弟几家欢喜几家愁,不在赘述。

高一具体情况也未从得知。

只能静候成绩与排名下发了。

没啥遗憾的,只能说自己太“偏科”了,遇到dp只会最朴素的dp。专攻数据结构的我,在CSP遇到4个dp,也只能以运气不好为借口自我安慰了吧。