考前一天
感觉没什么好复习的,随随便便看看模板就过了,感觉会考图论,一个猜想,不一定对。考试当天上午
坐在机房,闲的心里发慌,开始过模板,突然发现整个机房就我一个 (不会的都会更高级的算法)不会st表(还在倍增lca)急急忙忙去过,理解了半天还是不敢保证考场会打,人一下子就慌了,距离中午吃饭还有2h,冷静下来看图论(CCF一定要考啊),隔壁的巨佬在用网络流写dp,蒟蒻不懂联赛看网络流干啥。回过头来过了一下tarjan,仔细想了一下去年有移球游戏 ,今年肯定有毒瘤题,于是溜过去看平衡树,痛苦地挣扎了两小时,勉勉强强调过了。上午就这么过了,今天主场作战,csp-s rp ++考试
进考场前路遇几位外校的巨佬,赶紧膜拜,众所周知,考前膜巨佬有益于rp++。
进考场了,熟悉的系统,熟悉的键盘(还是这么难用),完全不熟悉的考题,大概扫了一眼,T1大概有点贪心的意思,毕竟每个飞机能停在那个廊桥是定死的,但想了想,还是先看看后面的题,T2肯定是区间dp(模拟赛有道相似的),仔细看了看发现这道题细节巨多,自己掂量掂量自己的码力水平,觉得还是不行,自己推了一下式子,但过不了大样例,回过头来重新看了看题,才发现S在A的左右两边时必须又要括号,当时人都傻了,这是已经开考45min了。出去上了个厕所,回来准备看T3。
T3乍一看,真的认为是道数学题(5e5的数据范围,完全想不到什么数据结构)认真读了读,发现T1更可做,还是先看一下T4,又是很长的题面,联想了一下去年的贪吃蛇 ,一想到现在我一道题都没做出来,背后一凉,赶紧去看T1。
怎么说呢?还是数学学的太差了(其实是没怎么没用过STL模板库),推导了一下,发现每一个廊桥停的上一个飞机的起飞时间和下一个飞机降落时间都成严格上升。想了想 $$f(n) = \sum_{i=1}^{n-1}{f(i)} + g(n)$$
其中f指能停的飞机数,g指在n号机场能停的飞机数。意味着只要在log(n)的时间复杂度内查询出这架飞机停在哪,用线段树维护区间和即可。自己兴奋的打完,一测样例:没过,然后极其痛苦的查了30min后,才发现是lower_bound炸掉了,点开lower_bound才发现ta就是帮我写了个二分,仔细思考了一下如何在随时修改的无序序列中快速查询出第一个比大的值。一敲脑袋,发现自己完全不会只能硬枚举,复杂度为$O(n^2 -n\log n)$希望CCF的数据水一点,别把我卡掉。
已经考了2h,开始码T3,仔细分析了一下发现当第一个出去的数确定了以后,后面每一个出去的数就确定了,开始疯狂码贪心,然后打了1h发现自己无法确定中间加数时的顺序(后来问了大佬才知道,其实可以确定,打的也没有问题,就是自己太弱了,没想到),在激烈的思想斗争之后,还是决定打暴力拿40分跑路,打了暴力就走了。
在自己语文能力的限制下,自己还是没从第四题的题面中挖出点什么,总感觉大纲里的考点一个也匹配不上,果断放弃继续打第二题,结果还是没打完。
崩了呀,还是自己平时没复习好,平时除了部分数据结构题什么也不想做,看来后续做题思路要改改了估分: $(60-70) + 0 + 40 + 0$实测 $85 + 0 + 12$(差了8分tg1=)考后
第四题原来真的可以用网络流吗,这玩意不是不考吗(早上看网络流的巨佬就A掉了),第三题暴力写挂了,第一题民间数据倒还没卡掉(希望CCF也没卡掉)
接下来该多看看数学题了,再不看就AFO了(可能已经AFO了)(数据结构,图论都没怎么考(除了该死的超了刚的网络流))