• 周四. 5月 30th, 2024

5G编程聚合网

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

热门标签

NOI2021 游记

admin

11月 28, 2021

Day -2

报道日。到报道处领了一波东西并在签名墙上留下了最大的名字之后就去了宿舍。上午收拾了一波东西,然后突然得知同寝室的一个老哥去过南京,被隔离了,于是三人寝->两人寝。晚上去串了串门就睡觉了。

(不硬性要求睡觉时间好评)

Day -1

由于报道日提前了一天所以今天没有安排,在床上躺了一天

Day 0

上午睡大觉,然后中午的时候开始有消息说下午要笔试。然后某交流群里面消息疯传但都没有可靠来源。后来吃完午饭教练过来确定了下午 2:30 要考笔试并发了密码条。然后下午两点半就进场,三点开始笔试。笔试之后就是试机环节,试着打了一波去年的 D1T1 结果没打出来十分自闭。

出来之后才知道可以看成绩,于是又回去看了一趟,然后得知 asd_a 由于看题过于仔细失了一分,而自己却混到了一个 100。

之后把 DEV 改成 gedit 的模式试着复现了一波去年的 D1T1 结果打了五个小时才过。

心态一点都不稳健.jpg。

Day 0.5

休息一天。复现了一波去年的 D1T2 和 D2T1,然后奶了一波 NOI 不会考 log 数据结构于是没复习。看了一遍字符串就睡觉了。本来打算看一遍 tarjan 板子,但是感觉睡觉比较重要就放下了。

Day 1

一试。进考场之前听到旁边老哥在讨论 LGV 引理,然后奶了一波「这东西怎么可能考」。

什么叫国际毒奶啊

然后进考场开题。通读了一遍感觉 T1 是 LCT 状物,T2 是行列式,T3 是支配树状物,于是先开 T2。大致刚了一个小时就发觉这其实等价于 LGV 引理,于是写了一个行列式板子就过了所有样例。

然后回去看 T1,树链剖分之后感觉可以对每条重链搞一个 ODT 维护一下可以做 (mathcal O(nlog^2)),然后就开始写。写了一个小时发现根本不需要 ODT,可以直接线段树区间染色维护,然后又写了一个小时就过了样例。

剩下的时间就在看 T3,然后分析了一波性质发现其实就是缩点之后是一棵外向树,然后想着 T3 可能是防 AK 并且有两道题已经够了就放弃了 (k=2) 的分,去讨论了 (k=0)(k=1)。大概还有十分钟的时候过了样例,后面就在到处检查。

出考场之后发现大家都没写 T2,而 T3 我如果不讨论而是直接建虚树就能过掉。

下午复评发现自己 T2 行列式板子写挂变成 55,T3 只有 48。

预估 100+100+64=264

实际 100+55+48=203

巨大多挂分.jpg

Day 1.5

该复习的都复习完了,于是睡大觉。

Day 2

大概知道自己银定了,金没了所以心态十分放松。

进考场之后通读题面,感觉 T1 是神秘 Trie 题,T2 是平衡树题,T3 是指数级算法给指数除个 2。三道都不怎么会于是先开 T1。大概看了一个小时编出来一个随机化算法,大概就是随机选 20 组 16 个点,然后钦定当前的询问串在当前组的十六个点都是没有更改的,然后大力做匹配。写出来之后发现常数太大只能过 84。这时候大概过去了两个半小时。

分析了一波 T2 发现最后的序列可以变成矩阵乘法,然后只需要维护 W 和 E 的连续段,发现巨大多难写于是打了 50 分暴力就去看 T3。按照样例解释模拟了一个能过 (nleq 16) 的 28 分暴力,之后就没什么时间了。

出来一问发现大家考得都不怎么彳亍。我金可能又有了.jpg

预估 84+50+28=162

实际 84+40+20=144

最后总分 447,金牌线 498。

如果两天都不挂分我金就有了.jpg


总结:技不如人,甘拜下风。

发表回复

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