CSP 2020 复赛游记

坐标GD，考场纪中 复赛前打了19天正睿，天天自闭QwQ $\text{Day 0}$ 打了一天模板，晚上睡觉前才发现 欧拉筛和扩欧求逆元 不记得了，爬起来复习 $\text{Day 1}$ 早上五点半坐车出发，睡了一路 提前了半个小时在考场外面排队等，抢到了队伍最前面 进了考场，坐在考场的最角落 键盘手感极差，而且跟旁边的人都不一样 开场本来想先看一遍题，结果看到T1这么水，就写把它码了QwQ T1签到题，考了一个二进制唯一分解定理 T2需要维护一个动态数组，支持插入和查询第 $k$ 小 set 似乎是不行，手写平衡树太麻烦，就写了一个 vector + 二分插入 复杂度 $\operatorname{O}(n \log n)$，因为我已经无数次用 vector + 二分 代替平衡树了QwQ T3一看就有很多细节，而且输入很麻烦，就先去搞T4了 T4应该是我花时间最多的题了 首先写了一遍 dijkstra，后来发现有负权边，放入回收站 接着把他改成了 spfa，又因为有负环，放入回收站 然后就写了一个 dfs + 记搜，但好像不能保证正确性，放入回收站 后来把题目稍微转化了一下，好像以前做过一道类似的题 然后就写了一个70pts的 $\operatorname{O}(n^3)$ 的DP 这时只剩下了1h，而且还没对拍 现在要在T3和T4中选一个，而且要保证30min内弄完 由于特别讨厌T3这种类型的题，就选择了T4 5min内想到了正解，用的是 $\operatorname{O}(n^2 \log n)$ 线段树优化DP，并且在结束前35min过了大样例 接着随便搞了个generator，就开始大力拍T4 对拍的时候输出了一下T3的样例，而且懒得对拍前两题了 最后10min，还没有拍出错误，就把程序放好了，并运行了一下CCF防脑残的 checker.exe 估分 $100 + 100 + 0 + 100$ 学了两年多OI，前两年PJ初赛都没过，今年第一次打QwQ，感觉还挺简单的 ------- 中午去车上眯了一会，1:50 起来去考场门口排队 -------- 下午坐到了一个比较好的位置，而且键盘没那么屑了（狂喜） TG不敢乱来，就乖乖的看了一遍题 T1大模拟（吐血） T2位运算，而且好像有点猫腻？ T3感觉在正睿做过类似的（但还是不一样），但只会50pts T4毫无思路，跑了QwQ T1是模拟闰年的增强版，由于我太菜了，就选择了一天一天递推 从公元前四千多年，一直推到公园一千多年，天数大概是 $2 \cdot10^6$ 如果询问超出了我的递推范围，就按照闰年规律，就特判几下就完了 一运行，发现有时候会跟正确答案差一天，就大力静态差错了一下，最后在 3:15过了大样例，代码160行 T2 只花了5min就想出来了，感觉输入中的 饲料编号 好像没卵用？ 于是我又读了5遍题，好像真的没卵用 我发现中间有一个地方会爆 ull（去年血的教训），特意特判了一下 T3 虽然只有50pts，但要分三种情况讨论，最后写了两百多行代码 这时，又只剩45min了，就跟随了上午的套路：对拍 + 输出样例 - T1 不好拍 - T2 暴力比较麻烦 - T3 也是有一部分不好拍 于是我就对拍了T3的一部分，输出了T4的样例，最后在检查了一下 估分 $100 + 100 + 50 + 0$ 考试结束2min后，发现自己T2忘记开ull了QwQ 因为我写代码的时候都不管数据类型，然后再最后统一用 Dev 的 Replace 功能开 long long。所以就忘了/kk 所以T2不知道会扣多少，希望不会太多 $\text{Day 2}$ 出代码了，这速度i了 牛客数据： PJ：$100+100+10+100$ TG：$100+90+50+0$ 洛谷数据： PJ：$100+100+15+100$ TG：$100+90+50+5$ 并没有跟估分差太远，老开心了 据小道消息我好像是GD第51？ $\text{Day 3}$ 上洛谷问了一下 $vector$ 插入的复杂度，听说是 后面元素个数 $\times \frac{1}{100}$。有点小慌，以后再也不敢乱用 vector 了 $\text{Day 10}$ PJ出成绩了：$100+100+5+95=300$ 还好T2没卡，可以算一次乱搞采标算了 T4懒得申诉了，因为是PJ QwQ $\text{Day 11}$ TG出成绩：$100+95+50+0=245$ T4竟然只坑了五分，梅开二度 今年没有区分度的题，就只能靠代码稳定性和时间分配能力了，还是多亏了正睿的自闭之旅。 NOIP RP++