杂记 - CSP2019游记 | Lucky_Glass's Blog
0%

杂记 - CSP2019游记

CSP考完过后什么都不想干……回机房写一发博客 awa(还没有退役)
懒得写一篇“退役记”,不然之后没有退役还真香然后写一个“复活记”(反正我懒……)

另外“照片墙”那边也只是最后走的时候草草地拍了几张,都没有照到学校里面,不过至少还是存下来了
#点此前往照片墙#


Tab. 水的

Part1. 总体感受

去年的题目被选手吐槽说太水了(但是还是没考好),然后今年似乎吸取教训把题出难了一点。然而去年都是dalao吐槽题水没有区分度,今年题难一些……emm

这两场考试的战略有一些不同,毕竟 Day1 的题目相对简单(除了T3);反正 Day1 就先通览题目过后挨个做,然后 Day2 就是先看了题目,看完题过后就开始先动笔画一画,画完过后就大概知道只有骗分了这些题的思路了。


Part2. Day1

Day1 的题反正是没有什么区分度的,人均 210,T3似乎比 Day2 都难,所以也没拉开什么差距。

T1 非常简单送分,而且非常善良地还把 95pt 的部分分写出来了,当提醒选手注意数据规模。

T2 难度还好,只是第三个大样例给得太水了……当时写完测过小样例,然后测第二个样例,然后就 WA 了?整个人就很懵逼,测第三个样例又过了(怀疑是不是数据给错了)但是一看第三个样例,就知道为什么能过了 —— 一条链而且链上就是 ()()()... ,毫无难度……后面调了一会发现回溯的时候栈的撤回操作没有写对 awa

T3……当时看完题就没有什么思路,然后就挂掉了,只写了个暴力 @_@ 因为 T1T2 做得比较快,T2对拍写了都还剩了比较长的时间。然后就开始想 T3 的链状……反正还是没有想出来。


Part3. Day2

Day2 基本上就是骗分了,不过还好这次思路没有偏,跟几个dalao所说的正解思路相符,只是缺一些优化。然而 Day2 基本上就是 DP 专场……考的就是各种各样的优化。

Day2T1 第一眼就是容斥,然后当时在草稿上推导的时候脑子有一点糊,没有想到 $O(n^2)$ 的DP,只想到了 $O(n^3)$ 的(其实个人觉得 T1 这个 $O(n^3)$ 的 DP 还比较好想),主要是因为没有搞清楚“判断不合法”到底需要知道哪些变量吧……然后 DP 转移就比正解多了一个 $O(n)$。

T2 直接看出来斜率优化,然后推了一波式子,感觉跟一道斜率优化版子题很像 :),然后一开始以为添加的条件限制并不难,然后就没有管。正式写代码的时候就开始想,发现直接斜率优化好像会挂……想了一会没有思路,就只写了个暴力DP,然后去做 T3。发现 T3 并不可做……把好写的部分分拿了就跑回来继续想 T2(做完T3的时候估了一下分,好像没有 400,感觉不行啊……然后就想把 T2 的 $O(n^2)$ 给做出来)。
模模糊糊感觉好像有什么单调性,打了个表发现还真有 o_o,然后果断单调队列一波。因为思路不是特别清晰,调了比较久的时间,最后还剩接近十分钟的时候,先把文件输入输出和文件名这些要命的玩意检查了,然后继续写T2,最后终于写出来过了样例……然后就没时间再对拍测试了,不知道到底得到分没有。

T3 完全没有思路,把最简单的 $O(n^2)$ 暴力和很显然的链状结构给写了,然后二叉树都没怎么想就回去写 T2 了。之后听同学说完全二叉树的结论还挺简单,不知道是不是有点亏……


静待出成绩(懒得测民间数据了)
Upd. 还是忍不住测了一下,380左右 (爆了)


Tab.不水

Upd. 回顾

Upd/1. Day1

第一天考前的期待分是 200 以上。上考场之前最后确认了一下中国剩余定理和 Lucas 定理。

第一天采取的策略是先简单的确认每道题是什么,弄懂题目意思,比如看懂每道题后,知道了 “T1是送分,T2是DP,T3是??(反正也确定了T3不是可做的)”。然后就从 T1 挨个做。

的确没有判断错,T1 直接送分。想出正解过后直接看的 100pt 的数据规模,没有管部分分。
然后对 $n\le64$ 产生了警觉,于是就用 printf("%lld",1ll<<64) 检测了一下,果然爆了。再用 unsigned long long 试了一下,还是爆了。但是在我的印象中 unsigned long long 应该是 $2^{64}-1$,作为 T1,不应该写高精度。
不一会发现运算过程中最多出现 $2^{63}$,然后就放心的用 unsigned long long 了。
考试的时候不确定 ull 的占位符,就直接 cin,还是非常保险的。

看完 T2 后当时就有一点思路,基本上10分钟左右就补出了正解,然后就开始码代码。
写完过后测过了小样例,然后大样例 Sample2 挂了,改了 20 分钟没有改出来。然后测 Sample3,发现过了?有点疑问,点开 Sample3,发现是链状……非常水,也难怪能过。不过也给了我一些启示——链状是不存在回溯的。最后检测果然是回溯出了问题,T2 花费 40min 左右完成。
因为有一点结论之类的东西,内心不踏实,就用了十多分钟写了对拍,然后做 T3,拍了好久(因为我忘了关对拍器了),没出错,也就放心了。

剩下一个多小时就搁在 T3 了(除了 10min 留给基础检查)……发现链和菊花图这种情况。一开始在想链,然后发现策略被卡了(30min),就换到菊花图,发现各种分类讨论,不可写……就回来继续做链。
最后还是没有想出来。

Upd/2. Day2

又不是没考过提高组 Day2……自动心态保护期待分不会太高,但是因为两场考试总分希望有 400,还是想再多一些分。

依然是看懂所有题,但是不同的是 —— 看完题过后先想一会,不写代码,有一些简单的思路。

其实有一点风险,就是这样简单的思路完全无法保证正确性,万一歪了就惨了……

T1 看懂过后直接看出容斥,而且知道容斥的正确方法,也知道了这应该是一个计数性DP。看了数据规模,肯定正解是 $O(n^2m)$ 的,然后跳过看T2。
一开始有一个二维DP,但是后来证明有后效性(20min),就放了。为了避免后效性,加了一维,变成 $O(n^3m)$,再看数据规模:84pt。勉勉强强,就写了这个过后就 pass 了(1h 左右),毕竟正解没有什么思路,直接放掉 16pt。

T2 一来直接看到一个斜率优化的经典式子,但是这个限制着实恶心……想了 20min,猜了一个结论,写完测出来是错的……(40min),就把这个错误结论当作大规模数据的解法(分段函数),而把非常 easy 的 $O(n^3)$ DP做了,暂时 pass(1h)。

T3 想完就没有什么思路……只知道换根 DP 暴力和链状都很简单很简单,知道正解写不出来,就想完全二叉树,还是没有思路(应该是因为对完全二叉树的重心不熟悉)。写完链和暴力(50min),还剩下 50min 左右。

计算了一下分(因为觉得目前的分数应该都能得到),发现离 400 还差一部分,看了所有题,T1T3 直接放掉,就剩下 T2 $O(n^2)$ 的做法,于是就开始猛gan这个部分分。

T1 的难度有一点判断失误,但不知道考场上如果剩下的时间去抢 12pt 能不能想出来。然后就选择了看起来更容易、且分更多的 T2 的部分分

利用一切我知道的 DP 知识(但是忘了 wqs 二分),猜了一下单调性……对我的 $O(n^3)$ DP 的最优决策点打了一个表,发现真的有单调性(剩余 40min)。
知道时间不多了,花了5min去检查代码基础、编译、文件名,然后全力推导单调队列。

结论是对的,因为已经保证之前已有分数,就直接额外新开 cpp 把 T2 代码复制过来改。

这个方法是我比较推荐的

写完过后(剩余20min左右),测大样例,调试……一直到最后2min测试大样例,过了。但是并没有自己构造数据的时间,不敢保证正确性,就再嵌套一个分段函数,保证已有得分(剩余1min以内)。

飞快地最后检查文件、编译。考试结束。


The End

Thanks for reading!

回去补文化课了……今天晚上还要考试……