CSP2020 J/S 游记

2020-11-13 22:24:03


CSP-J

早上 8:00 到考场,忘记了一个叫做座位号的东西。。。

还好签到表上有。。。


8:30 开题

T1 智障题,秒了。

T2 读完题:草怎么考平衡树,再往下一翻数据范围:值域 $600$。。。秒了。

T3 ???好像不太可做???先放着。。。

T4 又是一道智障题,秒了。

先出去洗了把脸,回来一看时间 $9:00$,十分舒适。

回过来看 T3 才发现修改之间互不影响。。。又感觉跟那个什么位运算二叉树(自己瞎起的)有点关系,想了想发现挺好做的。rush 了一波代码, $9:40$ 过大样例。

总感觉这个 T3 跟 NOI2020 D2T2 有某种奇怪的相似/emm

花了 $10min$ 写了 T4 对拍。但是 T3 $gen$ 不会写,感觉挺烦的,于是就肉眼查错,也没查出啥。。。

对拍挂着,然后高兴地玩起了 Windows 自带小游戏。

监考老师还过来问我:“你做完了?”

期望得分 $100*4=400$。

民间数据测出来也是 $400$。


中午就待在考场边上没回家,吃了点巨好吃的东西,心情平淡。与 zghtyarecrenj 神在 QQ 上聊了一会儿,他竟然不会 T4???

小睡了一会儿,不久就到时间了。


CSP-S

拿了一大堆的食物进考场,全考场好像就我带了那么多。

14:30 开题

T1 读完题,向出题人全家致以最诚挚的问候之后开始肝代码。

我当时想到的就是二分,也写了二分。好像没多少人是用二分做的?

肝完代码,过了各个样例,手造了许多组毒瘤数据,还手动二分出 1582.10.4 的数据。稍微改了几个细节,感觉挺虚的。一看时间 15:40。完了完了来不及了,赶紧开下一题。

T2 智障题,秒了,结果没判 $cnt=64$。。。

T3 一开始以为是 ds 题,有亿点不会。

T4 连题都读不懂,当时就觉得自己完蛋了,要暴力分滚粗了。

于是吃了许多饼干,去洗了把脸,回来先肝 T3。

感觉这个全局乘别有用意,然后就联系到了你咕第二个线段树板子的 lazytag 下传方法。求乘法的贡献很简单,随便 dp 一下就好了。开始想加法的贡献,转化成了求每一个加法操作每一次执行到之前所有执行到的乘法操作的乘积之和。发现用之前那个 dp 做个后缀和再 dp 一次就好了。

于是高高兴兴地写完,高高兴兴地过了小样例,结果测大样例的时候爆栈了(我一开始写的 dfs 版本)。我用各种方法将栈开大,结果无济于事。还好才 16:20,不慌。于是 rush 出了一个 topo 版本,16:35 过了大样例。

心态突然巨好,想着 T4 拿点暴力分就行了。又吃了一大堆饼干。一看 $n=3$,分类讨论一下就行了,还有 $20$ 分。写到一半发现可以写个 $n=10$ 的暴搜。有 $40$ 分了!!!写着写着发现这好像可以做 $n=10^5$!!!有 $70$ 分了!!!

然后我就用 $set$ 模拟一遍,并做了一个贪心,结果在大样例 WA 了。百思不得其解,后来发现是一条蛇可以知道后面的蛇不敢吃他,自己变成最小的也没关系。于是我就做了一个 $dp$ 高兴地过了大样例,觉得自己做法挺真的。

此时我认为后面的 $30$ 分是神仙数据结构,不会,弃了。

考后才知道是蚯蚓。

期望 $100+100+100+70=370$。

民间数据测出来都是 $[360,365]$。


J 组题比去年好多了,也难一些。

S 组比去年简单一些,个人感觉题目不错(除了 T1)。

(这是一个没有新意的结尾)