Wolverine 的博客

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++


2020-11-08 20:29:30 in 未分类