Alex_Wei 的博客

Alex_Wei 的博客

Welcome~

CSP-S 2020 游记

posted on 2020-11-07 23:59:15 | under 游记 |

以前没有写游记的习惯(主要是写出来的文字太烂),就让这次 CSP-S 2020 成为起点吧。

坐标 JS NJ。

Day -?

QQ 显示异地登录,于是把密码改成了 iakcsp2020(

Day -5 ~ -4

CF 连炸两场直接 IM(Div.1C 害人),心态爆炸直接导致接下来一周都没有碰键盘,同时也预示一周后 CSP 爆炸(确信

Day -3 ~ -1

沉迷 whk 无法自拔。

Day 0

下周二期中考,所以绝大部分精力都放在了 whk 上面,回到家后才想起来第二天有 CSP(雾

不过化学真的好有意思啊(雾

(update on day 4:期中考试化学炸了,淦)

晚上打了几(零)个板子,发现连 dijkstra 都不会打了,顿时感觉要凉。

九点收到了 ycx(@chenxia25)& syx(@Sunny_Sun)的祝福,他们俩老好人了/qq

Day 1

抱着 “反正才初三影响不大,随便玩玩” 的心态,早上还是在搞 whk(

八点又收到了 @Isaunoya 的祝福 /qq


吃过午饭 12:30 出发去南航,背包里装了一大堆 whk 复习资料(

路上在复习英语 grammar points(单选 25 分啊,雾)看着看着就睡着了(

小堵一会儿,13:20 到了南航西大门口,一眼看见 ycx & tzc(@ET2006)& syx & lyc(@LTb_),相互假了一会后进了南航。


带了手机可惜没拍照。久别重逢总是令人感慨万千:第一次来这儿参加 NOIP-pj 2018 的时候还是个小不点()

太阳特别晒。我那一群同学就在太阳底下傻站着聊天(((

csy 竟然和我在同一个考场,%%%。

后来发现周围的人都带了零食,只有我是一瓶水,馋啊(

进门的时候每人发了一个参(xuan)赛(chuan)手册,听说不给带进考场 ycx 直接给扔掉了(

csy:应该会有一个 998244353(泄露试题实锤了,引恐禁三,雾)。

我:盲猜会考高精(ycx:都 0202 年了怎么可能还考高精)

《假 如 T 2 算 高 精》


13:50 准时进了考场,好评。

进考场的时候刷了一遍金属探测仪,后来监考人员提醒手机要关机,不放心回去检查又刷了一遍金属探测仪。

发现没拿水杯又刷了一遍金属探测仪()

试机的时候打了个快读板子和一些宏定义,希望能省点时间。

等待试题下发的时间心情比较轻松,就像是当做一场小 test(确实也是),没有去年很紧张的那种感觉(可能是实力增加了?),看来做足心理准备,保持风(sui)轻(bian)云(wan)淡(wan)的心态确实挺重要。


14:26 提前四分钟下发试题好评()

点开 pdf:这也太丑了吧( 没有 LaTex 看得很不习惯。

扫了一眼 TimeLimit:1s,1s,2s,2s,没有 O2。

然后看 T1:???

大模拟,然后开始写,写到一半发现只保证答案在 $10^9$ 以内。然后估摸着这作为一个坑点,大样例应该会在 int 范围以内,点开一看,果然,应该能坑掉不少人?

写着写着时间就过了 30min,测了一下样例,WA。

一看这情况不对劲啊,不会栽在 T1 手上吧,不会吧不会吧?

debug 好一会才发现 “只要年份是 4 的倍数就是闰年” 这句话适用于所有 1582 前的年份(我以为是公元前)。淦,还要分情况讨论,出题人 ****。

调着调着时间就过了 1h,15:40 的时候终于调过了样例和大样例。

想到接下来三题都还没看,感觉有点慌。


T2 一眼题,想了想极端数据( $n,m,c,k=0,0,1,64$)发现这是要用高精的亚子?(内心狂喜:这绝对坑掉一大批人,拉低分数线,就有更大概率 1=)

码到一半发现空间可能会炸,又看了看题面发现 $a_i,q_i$ 互不相同。

这不就简单了嘛,连 $a_i$ 的数组都不需要开,空间复杂度瞬间降为 $\log$(实际上可以做到线性,不过没啥区别)

15min 码完高精程序,小样例大样例一遍过,爽啦。

(出考场后发现可以特判 $ans=2^{64}$ 的情况,剩下来直接 $((2^{bit}-1)\oplus n)+1$ 就行)

(upd:大概 $2^{bit-1}-n+2^{bit-1}$ 就够了/fad)

(upd:我在考场写的是 $O(nk)$ 的,想了下可以做到时间 $O(n+m)$ 空间 $O(1)$)

感觉没啥问题,懒得打对拍,直接丢掉看 T3。


16:00

看到题目描述没有任何字符感到很惊讶,以为是什么奇奇怪怪的题目。

认真读一遍题:函数调用?建图!没有递归?有向无环图!单加多乘?数据结构!

等等。。。有向无环图怎么上数据结构。。。有向无环图上 DP!

想 T3 的时候总感觉和正解特别接近,又仿佛是那么遥远。。。

一番苦思冥想,终于搞出了正解。

然后就是码码码,码到大概 16:50 过了两个小样例,但是大样例死活过不去。

使用干瞪眼法 debug 无果,期间一度怀疑是不是假掉了。。。

最后还是决定 d(ui)p(ai),17:20 拍上,第一组小数据( $n,m,q=20$)就挂掉了 /fad

缩小数据范围后( $n,m,q=5$)第一组数据又挂掉了,离谱。

又看了 10min,终于发现是计算贡献的时候,函数编号和数据编号弄混了。。。改掉就能过大样例了。

fatal mistake!浪费了 40min 啊 QAQ。

(后来听说 T3 大样例很水,不过和暴力 + 随机数据拍上的我丝毫不慌,雾)


想着 300 分 1= 大概稳了就没打算再认真搞。

先用 15min 检查了一下文件,确保没有问题之后才开的 T4。

17:45。

$n=3$ 简直是在送分,5min 不到 20 分到手。

接下来 $n=10$ 好像也很好拿,不过想到了贪心 + set 解法 $O(n\log n)$ 就直接 rush。

码完后 18:20,发现能过小样例但是大样例会相差 1,难受,估计也 debug 不出来就弃掉了,剩下 80pts 随缘拿分。

18:28 检查完,18:30 准时收卷。

估分 100+100+100+20=320。

这次签字确认比去年不知道快到哪里去了,好评。

但是一开始把编号和机位号弄混掉了,找不到在哪签字(雾


出了考场和 ycx & tzc 交流了一下,发现他们估分也是 320,大众分 320?

他们是 100+100+50+70,原来 T4 这么水的吗?难受。

后来说 T2 会炸 ull 他们全部傻眼(((不过应该也就 5 pts

回到家想自测但是一直没有数据,大概九点的时候 ycx 发来消息:315。

遂要了网站前去自测,评测的时候手都在抖。

民间数据没有挂分!hooray!比去年还高了 9 pts(

Day 2 & 总结

不说遗憾那是假的,毕竟 T4 的 70pts 那么好拿。

自今年九月以来,进入初三,学校的压力顿时大了很多,很大一部分时间都分给了 whk,只是借 CF 吊着一口气。

在这样的情况下,能比周围大部分同学高,运气成分确实功不可没。

诚然,如果再给 1h 说不定能 AK 比赛,但是能够避开 T1,T2 的大坑,找出 T3 的 bug,已经是非常幸运了。

upd:

洛谷民间数据:100+100+100+20=320。

没有掉坑,没有对拍,没有挂分,这得归功于一年来打的五六十场 CF 啊(

ycx T4 $a$ 数组没还原挂成 15pts 了,惨惨。

tzc 好像 T2 挂成 75pts 了?

csy 370,%%%

如果一个人碰上了 $5\%$ 的好运,他又有什么资格不去感激这 $5\%$,而是遗憾没有那 $1\%$ 的运气?

题解

T1(julian):

模拟就行,就不放代码了,没啥意义。

T2(zoo):

动物园

T3(call):

函数调用

赶紧复习 whk 去了,溜了溜了。

求赞 QAQ