• 周日. 11月 27th, 2022

5G编程聚合网

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

热门标签

NOI2021退役记

admin

11月 28, 2021

Day -2

报到日。由于疫情 + 台风提前来了。

Day -1

由于对台风的担心,咕咕F提前笔试+试机。大概 AH 队人均 AK 笔试。关于机器配置:i5-10400 八线程处理器(可能阉了两个核),32 位系统这为我被卡常埋下了伏笔

Day 0

颓、不热、打蚊子。

顺手打了个 generals.io 的世界前 50 的号,昵称是 syksykCCC。暗示 syk 未来必进队?

稍微复习了几个字符串板子,还有好多板子懒得复习了。

Day 1

担心 Day1 突然断电,咕咕F一如既往,推迟比赛时间 1h。直到 8:50 才入考场。

9:00 开考,开始读三题。

t1 轻重链,t2 什么神必交点计数题,t3 什么神必图论,但 (kle 2) 感觉不太难。

此时已经 9:20 了,开始开 t1。关于本人也不是啥巨大刷题量的选手,而且数据结构比较菜,这个 SDOI201* 的题没做过。操作 1 看起来很像 LCT,但操作 2 很难查询,而且我 LCT 忘了怎么写于是感觉这题在诈骗。根据 LCT 中的结论:轻重链 切换均摊为 (mathcal O(nlog n)),直接暴力切换也没啥问题。现在问题就是操作 2 的查询。结合以上我胡了一个 树剖 + set 的写法。

迷迷糊糊地在 10:30 左右写完,此题细节极多,完全不知道我在写啥。调试到 11:00 左右依次过大样例。此时已经过去 2h。

接下来为了保住 100 pts,我选择了对拍,又花了 30min。于是对拍在后台进行,一直挂到比赛结束也没出事。

11:30 开始开 t2。这个 偶数-奇数 就很有灵性。卧槽这 A 的分有不少,仔细思考发现 75 pts 都符合 A 的定义,于是先做 A,即 (forall i:n_iequiv N)(N) 是常数。不难发现每层独立,只要把每一层的 偶数-奇数 乘起来即可,问题变成了 (k=2) 的情况。其实就是与合法排列的逆序对个数相关。接下来我认为大部分情况下 奇数=偶数,打开大样例一看,FAKE!

再想一想,这个奇偶就是 ((-1)^{{m sgn}(P)})。这不是行列式吗!

直接冲代码,直接过掉了所有 A 的大样例!此时时间已经到了 12:00。毛估估一下我现在手上有 175 pts,按理说接下来要开 t3,结果心里痒痒的,因为 t2 还有 25pts。当时发现 (n_1=n_k),猜测是不是所有临接矩阵全部乘起来求 (det),又花了 10min 冲了一份代码,一开始由于没设置矩阵长宽挂了,调完以后一波过了所有大样例。当时我感觉起飞了!事后冷静分析感觉今年 Day1 可能和去年 Day1 相似,两道送分。

还剩下 1.5h。看起来 t3 很简单可我感觉是诈骗,会是一道不可做题(事实上是一道水题)。先看看 (n,qle 10^3),暴力;再看看 (m=n-1),推一推发现肯定是 外向树,观察 (k=0) 实际上就是简单判一判,又看 (k=1)(k=2),感觉是一个巨大讨论(当时没啥时间就讨论了 (k=1));最后看了看图的情况,结合题目给的性质发现有些东西会成为 竞赛图,显然只要保留最长链即可,最后又变成了外向树。时间不多了就开始冲代码,28pts 暴力写完结果没过。调了许久后来发现题目看错了:我以为是求 (max),结果求的是所有能访问到的点。不过问题不大,改完差不多就对了。稍微讨论了 (k=1) 的情形,此时还剩下 15min,随手写了个 (k=0) 的树,没样例于是手造了一组过了。感觉图的 (k=0) 好像也还好,花了最后 5min 冲了一下结果没过样例。算了不管了交上代码跑路。

估分 100+100+36=236,实际 100+85+28=213。这什么 sb T2 还卡常,我没写循环展开就 T 了,还有这 T3 的树好像写挂了?!后来问了 syak 和 hongak 发现思路没错。发现 scz 的 srf 和 csl 都 AK 了,这就是神仙吗?

听 srf 说 t3 可以做 (sum kle 10^5),直接上虚树就好了。/xia 我怎么就没想到呢?

问了一圈好多人上了 200+。yy 210+,qty 250+ 等等。听题时听说 ABCDE 里 30+ 人 AK,突然间有点灰心。又听说 jxd 线 240+,感觉还有希望。

问了一圈发现我是 AH 除 asdfz 外最高分,心里有些高兴;但看到几位 strong OIer 很可能拿 Au 却 Day1 失利感到十分惋惜。感觉 Day1 随机筛人?

winty 高斯消元写挂了,t2 直接爆炸了;czy 平常模拟赛天天 rk1,害怕 t1 卡常结果卡了卡常把代码卡挂了,也爆炸了。太遗憾了。

Day 2

(实际上的 Day 1.5)

上午颓,下午 NOI 嘉年华,有许多“随机”项目(暗示整场 NOI2021 是运气大赛?

玩保龄球的地上一条条“红线”(这球掉色很严重哈);颠球时关于地板 (mu=0);这投骰子人均 (E()单次()=6),除了我差点 3 个 4;飞镖飞空了 2 个,这随便扔只要命中率 80%+ 就 win 了?投壶人人无限 replay(

最后我得分垫底了 /kk

神仙 syak 得分 80+ 拿了个 Au 盘。羡慕 /se

人均领一盒榨菜。咕咕F你这也太不吉利了,骂选手又炸又菜。

晚上继续颓,睡觉~

Day 3

(实际上的 Day 2)

准时开赛了。上来看完了 3 题。

感觉去年 Day2 非常难,理所当然地认为今年也很难(事实上是因为我 t1 不会

3 题读完后死磕 t1(万一像去年一样就 win 了)。

这 t1 实际上就是对所有 (B_j) 判断是否存在 (A_i),满足 ({m pop\_count}(A_ioplus B_j)leq k_j)。题目中满足 (kle 15),感觉没啥用。强制在线(实际上是个假的强制在线)

它的读入使用 generator 生成的,看起来很随机,但 (B) 不一定。这一点让我放弃了“随机化算法”,一直试图找一种保证正确的做法,可能跟 FWT 有点关系?于是我无了(

到了 10:00 毫无思路。先写 (n,mle 2 imes 10^4) 的暴力吧。完了!怎么暴力过不掉?怎么用 bitset 的暴力过不掉?于是我把读入顺序 整体 reverse,发现还不对。完了!此时折腾到了 10:30,我改了 114514 次读入顺序还是不对,怀疑 gen 有锅。算了先开 t2 吧。

t2 一看就是个神必数据结构题。那个迭代求解的式子是个啥意思?最后发现得到的分式实际上是一个数列相邻两项的比值。数列形如 (f_n=a_nf_{n-1}+f_{n-2})(a_n) 跟连续的 WE 的个数相关。但还有些细节,比如说开头和结尾的组合有四种,这四种生成的的数列各有特点。那实际上就是对着 (a) 数列维护矩阵即可?关键就是怎么维护 (a) 数列?这好像还牵扯到序列的切割和合并?这怎么这么麻烦?至少有胜过无,我开始 rush 此题。此题要 fhq-treap,我许久没写感觉很生疏,写到了 11:40 还没写完。

我冷静下来,仔细思考到底要不要这么麻烦。这个 (f_n=a_nf_{n-1}+f_{n-2}),是不是也可以理解成一个东西被加上 (a_n)(f_{n-1})?那岂不是不需要维护 (a),只需要维护 WE 序列即可?矩阵可以简单搞成上三角和下三角 (2 imes 2) 矩阵。发现三种操作都是 treap 经典操作,先尝试维护好序列吧。

时间来到了 12:30,距离结束还有 30min。我利用大样例和 srand 来检查代码有没有问题。庆幸的是 treap 写对了。还剩下 20min,我开始着手检查矩阵的情况。矩阵没问题以后就剩下答案了。还剩下 10min,我想不清楚要用什么初始向量来乘,根据头和尾分了四大类依次讨论。终于讨论对了,过了样例 1、2。但就是过不了 3、4、5。

还剩 5min。这怎么不对?

这 tm 怎么不对!

我 Day2 要爆零了!

手动看了我的输出和 code3.ans。发现 code3.ans 没约分?!不会大样例错了吧!举手大声喊来了监考,他给我解释分子分母互质不代表模意义下互质,反过来也一样。卧槽?不会要手写分数或者啥的吧?我此时陷入了绝望。怀着侥幸心里把 d=gcd(a,b) 改成了 d=1,一把过了所有大样例!

可我担心数据不够强,不过想了想可能这个求 gcd 就是诈骗。没时间看 t1 了,就交了 t1 和 t2 的代码跑路。

回宿舍时没啥心情,Au 必无,肯定只能 Ag 了,就看看能不能保住前 100。后来发现所有人都会乱搞 t1,全天下都有 100+ 甚至 150+,zbl。

预计 0+100+0,实际 0+90+0。只要跟矩阵相关都要被卡常。

md 我没把 16 进制到 2 进制给 reverse,挂在这里了。

最后含笔试 403,拿了 Ag。Au 线达到了 498 的高度。

srf 显然进队了,yy 靠 Day2 也翻进队了,orz!

csl 怎么忘了提交 t2?痛失 jxd,太遗憾了…

lxh Day1 也大爆炸,Day2 依靠 195pts 强势翻到了 rk 70+;winty 和 hongak 也依靠 Day2 翻了我。最后我校三选手斩获三块 Ag。syak 也拿到了 Ag,奶高二 syak 必 Au!

晚上听了讲题,听了高校宣讲。回去跟 hongak 和 syak 玩了许多儿时玩的小游戏,通宵到 2 点才睡。

Day 4

NOI 闭幕式,发牌,拿奖,听故事,鼓掌!

蒙古上单!枪击计划!huáng kóng 先生!dzd:有两个人起到了 关键作用,一个,是···;一个,是 dzd!85% 的选手拿不到奖牌!

王宏:今年的题目,题意简明模型经典,考察选手的 基本功涵盖了多方面知识点,有 树(shú)链(liàn)剖分 行列式 鸽笼原理 平衡树 状态压缩 平衡思想,难度 有所降低,题目 相对合理,能够 有效区分 选手。

(这 tm 绝对是最屑的一年,又是原题又是板子题又是乱搞题

最后 AH 1 Au,8 Ag,2 Cu。比去年略好一些吧。

心语

心情许久才能平息。渴望今年题目能有不少思维题(我挺擅长),少些套路板子题,不要碰乱搞题(对乱搞十分没底),或者像去年 Day2 一样。可惜并没有。

一直不愿学习 whk 的我,曾经无数次妄想依靠 OI 摆脱这一切,终究还是要听从命运的安排。虽然没能达成一直以来的心愿,但那一块银牌,却也沉甸甸的,也算是对努力许久的我的回报吧。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注