• 周四. 8月 11th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

NOI2021 同步赛游记

admin

11月 28, 2021

比赛日前,一周的福建 NOI 集训比赛,培养了我不畏垫底的良好心态。

祝学长们能在赛场上取得好成绩。

Day 1

很早就起来了,然后听说余姚台风红色预警,比赛时间有所延迟。

于是同步赛就拖到了 10:00 开始,题目文件下载得很慢,多亏了群友帮助让我能及时看题(

T1 第一眼看上去不会,发现暴力也要打 LCA 什么的,就先默写了一堆树剖代码。

由于同步赛消息不通,我并没有打听到 T1 的链顺序为 $1-2-…-n$,于是多写了个 DFS 序。

然后链部分分就是很基础的线段树,结果我的两个部分分代码凑起来有 4.5K。

测了测大样例,发现开了 O2 后电脑的运行效率很不稳定,平均在 $0.9 sim 1.2$ 秒,有点难受。

加上了 register 和快读,发现能快一点,在 $0.8 sim 0.9$ 秒之间,赶快跑路看 T2。

我觉得 T2 中 $k
eq 2$ 时的部分分很难拿,就只对 $k=2$ 写了个爆搜,虽然比赛时想到爆搜可能会 TLE 要写状压。

但我不想改思路了,结果自己测试了下发现复杂度跑不满,极限数据也跑得很快。

翻到 T3,起初只想到当时我冬令营 T1 的 sb 绕环 3 圈做法,发现只能拿 $16$ 分。

然后又想了想,加减边用 vector 可以处理地比较方便,之后就想到了 $28$ 分做法,没有其他人想的那么麻烦。

简单说,就是从起点 $s$ 开始 DFS 到能到的点,从终点 $t$ 在边反向的图也跑一次 DFS,查一下有多少个点从起点、终点出发都能到达。

之后的事情就是查查错,卡卡常,划划水什么的,第一天比赛就这么结束了。

出来后发现很多人都知道 T1 是原题、T2 是经典题(虽然后来也发现是原题),心肺骤停。

下午在 luogu 自测,结果就是 $50+20+28=98$,和估计的一样。

T2 前 $4$ 个点跑得飞快(可能就这些点就是送分用),T1 没被卡常还行。

了解下隔壁校的几个同学,E 队队爷 chen_03 有 $70+75+36=181$,另外 18Michael 有 $188$,都好强啊。

听说今年现场有 $30$ 人 AK(暂未证实),只能感叹自己还是太弱了吧。

2021/7/27:由于某些原因,可能不会参加 7.28 日的 NOI 同步赛。

2021/7/28:今天没时间了,我中午挤了 1.5h 参加比赛。

Day 2

大概 12:20 才看到题,12:30 打开 C++ 编辑器。

先看到 T1,第一反应直接把 $2$ 进制、$16$ 进制数压成 $64$ 进制数(赛后发现很好的性质白给了……)

看到空间限制 384MB 就感觉这题卡常。

丢了个平均 $O(nm imes 4 imes 常数)$ 的暴力匹配法,预期 $20 sim 24$ 分。

调试的时候,一直有地方调不对,后来发现是每一位异或上 lastans

然后问题来了:$64$ 位二进制数 $x$ 每一位异或 $1$ 得到的是 $2^{64}-x-1$,异或 $0$ 就是 $x$。

合着说你不是把 $x$ 和 $2^{64}-x-1$ 两个数都求出对应答案,这个强制在线就消失了((( 

之后翻 T2,看到操作套操作,再外带连分数的维护直接晕倒。其它不管了,直接冲暴力,写完了就跑。

大概二三十分钟后啥都调完上交后,我只剩 $15$ 分钟。

光速浏览 T3,发现写不完,然后看见 $1 sim 2$ 号点 $n=m=1$,直接骗分: $S$ 中没 ‘R’ 输出 $1$,否则输出 $3$。

成功在 $14:52$ 上交题目。

下午听某去年集训队队爷讲 NOI2021 Day2,他也说了这是个假的强制在线。

然后听完题解自己直接懵掉。T1 询问串存在长度至少为 $16$ 且不变的连续段,T2 手玩操作序列 $a$ 后瞬间降智。

以及 T3 没打完,如果还有时间可能可以写 $28$ 或 $40$ 分做法吧。

luogu 自测成绩:$24+20+8=52$,两天 $98+52=150$,没啥 Cu 的可能了吧。

2021/7/29:沃日,Cu 线怎么才 103(去除笔试)……好吧还是有 Cu

发表评论

您的电子邮箱地址不会被公开。