【游记】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$ %，搞了个七级…

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

总结

咕咕咕