CSP-S 2019 滚粗记

初赛没过,谢谢大家对我的关注与支持

Day -Unknown

终于开始停课搞竞赛了,然后被同学们锤爆了......

Day -3

回作业培粹蹭了次秋游,美其名曰“放松心态”,于是又被同学们给围殴了。不过听到了机房巨佬 $zxyhymzg$、$Mentos$_$Cola$ 的歌声 不亏不亏

Day -1

才想起来写游记这个事情,就草草把之前的事写了一下。

随便看了一下过去 $5$ 年里 $NOIP$ 的真题,应该还是有点用的 虽然它死了

然而上午教练给我们考了一套神仙题,什么贪心+二分+构造、神仙数学、还有个什么 $set$ 启发式合并......不是说好的信心赛嘛,人家都是“临阵磨枪”,合着我们是“临阵折枪”呗

Day 0

疯狂水板子题,把几乎所有简单的板子都写了一边,还开展了机房模板竞速大赛(误,那些什么 $splay$ 啊仙人掌啊什么的就没打 反正也忘光了,还花了 $1h$+ 记 $vim$ 的配置。

好多同学给我们加油,莫名有点慌张。初中最后一次联赛,希望不留遗憾吧。

Day 1

早上跟作业培粹的车去了湖大,今年的场地不一样了,听说机子跑得飞快 感觉要T

惊奇地发现同机房有一堆巨佬都在一个考场,心情舒适 然而有挡板

一进去赶紧配一下 $vim$,幸好还背了 $vimrc$

今年是自行提交代码,发现电脑并进不去,没网。本来说要换电脑,想起边上都是神犇,不能浪费了这么优秀的位置,就自己重启了一下,惊奇地发现就有网了 美滋滋

开考之后,看第一题,先写了个模拟的暴力 我也不晓得为什么要写,然后开始搞正解,很快就能发现这个东西在区间的左边和右边增减性是有规律的,具体来说就是左边先 $0$ 后 $1$,右边先 $1$ 后 $0$。搞了个递归就过了前面的小样例。

然而最后一个大样例 $WA$ 掉了,调了好久才发现,左移那里本来要写 $ull$ 的,然而忘记了。发现不太保险,就随便写了个快速幂溜了。

看 $T2$,一眼树形$DP$,就随便设了个状态,就令$dp[i]$为从根到 $i$ 的所有答案,还搞了个数组$ed[i]$记录正好以$i$结尾的个数,貌似就能过了。

后来拿了个栈去维护路径上的括号,脑子有点糊,没想清楚,就把栈直接传在 $DFS$ 里,随便搞了一下就过了前面的样例。

然而大样例又挂了,发现好像是爆栈了还是$MLE$了之类的。发现大样例正好是条链,链又不需要回溯,就另写了一个专门给链的$DFS$,就把几个样例凑过去了,估计还是会挂一些点。

然后给$T3$留了$1h$,本来以为像去年第三题一样贼多部分分,就准备多拿一点 我不会告诉你去年我那题没打,觉得好像可做。

然而挂了,一分没得。

开始安享晚年

$Day 1$估分:

预估:$100 + 50 + 10 = 160$

自测:$100 + 80 + 0 = 180$

成绩:$100 + 100 + 0 = 200$

Day 1.5

回家之后心情低落,感觉不仅去不了营,连一等都不一定有,整个人都不好了。

$but$ 我还是玩了超久的游戏,并没有缓解

于是差点失眠了(误

Day 2

感觉一等已经无望了,但还是特别紧张来着。

在车上各位神犇们还在奶算法来着,什么$FFT$啊$Splay$啊都来了,心情复杂。

一进考场,发现昨天的代码还在电脑上,就又检查了一下 虽然没用,发现并没有出奇奇怪怪的错误。

果然电脑又挂了,还是没网。又重启了一下,又好了 (误

开考之后,第一题就把我雷到了。发现是一个神奇的计数题,应该是$DP$没跑了,就随便设了一下状态,发现并不可行。就又换了一种思路,拿所有的方案数减去非法的方案数。手推了一下发现好像不太可做 数学不好,好像是个$O(n^4m)$的东西,还贼难写,就滚了。此时已经 $1h$。

感觉$T2$还正常些,首先肯定有$a^2+b^2<(a+b)^2$,就拆得越散越优。看到$\Sigma$和平方,就想着是个什么斜率优化题,正解$O(n)$的样子吧,就(又)准备设状态推式子。

发现并推不出,好像只能搞个复杂度爆炸的算法来着,就重新设状态。

后来好像搞出来个什么一维的方程:设$dp[i]$为以$i$结尾的一段的长度的最小值。发现好像可做。想想就可以发现有一个方程:
$dp[i]=min(sum[i]-sum[j+1])(dp[j] \le sum[i] - sum[j+1])$。
发现它是$O(n^2)$的,可以过大概 $60$分了。

然后就赶紧写了一波,把能过了样例都过了。开始想优化。

发现对于一个位置,它只会找前面离它最近的可行位置更新,就想可不可以单调队列之类的,后来脑子糊了,想不太清楚,就滚了。

$T3$ 也比较神奇,就打了个 $O(n^2)$ 的暴力,还想了想能不能拿其他的部分分。发现好像链的也可做的样子,就随便搞了一下,把链的丢到一个数组里面去,然后枚举断开的位置,取两边中点即可,很好写的样子。

本来还想看看另外一个部分分拿不拿得到的来着,然而发现并拿不到,滚回去看$T1$。

$T1$还是没什么思路,就去上了个厕所,$but$并没有用,不会做的还是不会做......没得办法,最后$30min$赶了个暴搜,貌似可以稍微拿一点分。

$Day 2$估分:

预估:$30 + 60 + 50 = 140$

自测:$32 + 88(???) + 40=160$

成绩:$32 + 64 + 40 = 136$

Day 3

文化生活精彩纷呈 (误

Day 16

终于发成绩了鸭

然而我 $D2T2$ 果然爆回 $64$

共计:$100 + 100 + 0 + 32 + 64 + 40 = 336$

虽然是初中生,但是冬令营还是别想了吧

退役退役,文化你好

Day Unknown

$CCF$ 终于把一等名单公布了

没拿到一等 退役了 谢谢各位对我的支持

踩线一等(误

听说全国 $Rank1$ 有一位是初三的同学是嘛,恐怖如斯

还是和全国顶尖水准差了很多,还要继续努力 ~~

一定要变得更强才阔以

Day ......

哇我这分数竟然还蹭进了全国前 $10$ %,搞了个七级......

在你谷还成功白剽到一个蓝钩钩,美滋滋

总结

咕咕咕

已有 2 条评论
  1. 福雷 福雷

    dalao请接受我的膜拜

添加新评论