省选&GDOI 2023 游记

· · 个人记录

真正的游记,游玩就完事了

同时也是退役记

考点:广州大学附属中学大学城校区

Day1

8:27~8:35

pdf密码解半天解不出来,才知道那个 pdf 密码是要先解外面再解里面的,我是小丑。

发现标题是“NOI 2022 省选”,笑裂了,不愧是愚人节比赛。

8:35~9:00

直接开冲 T3。

推出了 m=0 且为链状的......6 分,没事蚊子肉再小也是肉,先打吧。

当各部门之间的关系是链状时,容易得知对一个很牛逼的员工而言,应尽量放在最靠前那个部门(毕竟最后一个部门可以收所有员工,可以放最后考虑)。

那,把所有员工根据初始部门顺序,用 vector 存下,从前往后扫所有部门,把以该部门作为初始部门的员工全扔在一个大根堆里头,取出堆头,累加答案就完事了。

然后就想了一下小数据,感觉像树形 DP,但是又推不出了,连贪心都不会,再去想有性质 AB 的 6 分,猜测是用线段树维护动态各部门贡献值的区间最小值,在加员工时跟 [v, n] 中贡献最小值做比较。

但是,五个月没打线段树了,没有快速码出的信心,先放着吧。

此时估分:0+0+6=6

9:00~9:30

看 T2

不会。

尝试爆搜。

不会。

完蛋。

此时估分:0+0+6=6

T1 一眼看上去挺可做的样子?先去 T1 。

9:30~10:15

把题意模拟了一遍。

...发现是真无脑题。分开双向做,差分一下好像就完事了?

差分过程中发现有 bug,比如

1 2     3 4

这样子的话用差分会连在一起,但实际上不是。

叹息了一瞬就想出了解决方案,分两次讨论,比如向右时,把所有 r_i 减去 1,计算答案时再加回去。

1 1     3 3

这样就不会假了!

一遍打完,忐忑不安地测 4 个样例,全过!

吾等菜鸡居然在省选考场上秒切一题?好激动。(虽然我知道那是人尽切之的签到题啦)

此时估分:100+0+6=106

10:15~10:30

祈祷 T1 过+上了个厕所。

10:30~11:30

码 T3 线段树

最后发现假了。自己把自己 hack 掉了。

但是我不理解的是,为什么样例 9 整整跑了 108s???复杂度没问题啊?

算了不管了。

11:30~12:00

发现 T2T3 连爆搜都不会。

T2 写了当 k=0n 是质数时答案为 1,否则输出 3

相信 CCF 的随机数据(雾)

12:00~12:57

检查了文件,肉眼检查代码有没有错,然后罚坐,直到比赛结束。

罚坐途中发现 pdf 开头写的是“NOI 省选2022

考试时间:“2023年4月1日 8:30~2022年4月1日 13:00”

xswl,时间穿梭。不亏是愚人节比赛。

比赛结束前 30 min,监考员:“不要写恶意语言啊”。

考场一阵欢笑。

比赛结束前 1 min,教授进来:“检查一下代码里面有没有恶意语言吧”

看得出来是真的怕(

Day 1 结束

考场估分:100+0+6=106

云斗学院:100+5+6=111

???云斗学院 T2特判质数后直接输出 3 有 5 分。震撼。

应该没挂(毕竟就只有可怜的这点分了!)

(upd:可恶,Day2没时间写游记,好像拿了60多分来着)