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，也只能以运气不好为借口自我安慰了吧。

写在最后

结果出来了，我是348分，在三中高二是第一。小智的partition拼错了，丢掉了一道题，只拿了344分。

对自己很不满意，毕竟D2是一种梦游的状态。

希望省选时不会这样吧。

版权属于：Noire02

本文链接：https://noire02.moe/archives/213.html

北京第三区交通委提醒您：复制千万条，版权第一条。转载删出处，博主两行泪。