CSP-2019总结

前言

CSP（不是NOIP）在一周前结束了，对于这次CSP，感慨万分，也写下这篇总结

意义

这次CSP既是我第一次参加CSP也是最后一次能从CSP中获得实际效益（明年还有一次娱乐场），对于CSP一试就感受到题型的不同（侧重真正的OI了很多），不过还好一试考了90+，过考试还是没有问题的，然后二试于我而言如果发挥失误很大也就意味着与4年多来学的OI告别，所以在考试中还是挺小心的

正文

day1

day1进入学车地下车库的那一刻，感觉有些有趣，赛场入口（地下车库入口）布置的非常别致，然后在学车地下车库考，感觉还是非常新奇

然鹅，不一会儿，就能感受到环境的恶劣了——厕所，竟然是移动厕所（即没有冲水的，卫生环境令人体验极差）

t1格雷码，感觉非常良心，看到基本就会了，但是发现有些细节需要注意，然后15min就写完了

t2括号树，依旧非常良心，看到之后就知道是树上dp题，先推了一个两方的dp，然后发现转移非常有性质，直接开全局桶就可以 O ( n ) \mathcal O(n) O(n)了

然后看t3树上的数，一看以为是简单题，马上写了个做法，过了样例，却未过大样例，冷静了一下发现情况未考虑对，由于幻想阿克（事实上naive了），所以到比赛结束都没有打暴力（一直以为很快就能想到正解），然后比赛的分数就变为最低为0的随机分数了

感觉day1有些着急了，所以T3的分数并不令人满意，出来发现大家都写了暴力，所以感到暴力没写有些可惜

day2

day2的题目相对day1更有思维难度

t1Emiya 家今天的饭，这题有点绕，没想到容斥就不好做，一开始我并不会，后来慢慢推出来了，想到了生成函数，又看到998244353，然后就觉得能用NTT维护生成函数，写完NTT后发现写挂了，于是非常慌，就冷静了一下，发现可以dp维护生成函数，然后就可以写出复杂度 O ( n 2 m ) \mathcal O(n^2m) O(n2m)的做法了，最后t1总共花了1h30min

t2划分，一看到就觉得和去年day2t2非常相似，是思维题，后来冷静了一下，想了几个贪心的做法，然后就找到了良好的性质——最优后缀，然后发现最优后缀可以用单调队列优化（刚好能过），然后就开始写了，然而在写恶心的高精度（差评）的时候写挂了一点点、调了一会儿，就用了将近两个小时

t3树的重心，写到它的时候留给我的时间已经不多了（20min），于是赶紧rush了一个两方暴力，原本还打了一个链的暴力，但是链忘记清空了，所以就没拿到这15分，t3以40分收尾，事实上t3暴力分有75，感觉很亏，不过也没办法了

总结

本次csp感觉体验并不是很好，出了4题，却比不上哪些全打暴力的人，不过分数还算一般般吧，不至于说是大翻车，就这样了

之后的比赛还会参加，希望能有更好的状态吧