NOIWC 梦游记

· · 生活·游记

来到重庆了，嗨嗨嗨。

去吃了顿辣的，还不错，毛肚yyds

下午去试机了，NOI有钱呀，i9+13900k RTX4090！

带个耳机下了个原神，感觉不错。linux系统里玩原神，第一次好吧。

day1

起来了，差点迟到，提前10分钟才到达考场好吧。

第一题一眼题，是 tarjan 老爷子2021发布的论文 O(e^{n \log \log \pi}) 直接秒了， jtq 说直接 O (n\log n) 直接维护就行，紫菜了。

40min 调完 T1 还算不错。

开 T2 ，NOIWC 还挺简单，第二题是可持久化动态仙人掌上 LCA 由于需要分解质因数，所以打个 Pollard-Rho 直接水过了，可调了 1h 多，菜呀……

T3 直接打个暴力用可持久化线段树套普通树状数组，做拓扑排序，MLE 只拿了 73pts 紫菜 \times2。

结果因为昨天吃的不太好，脑子没把 T3 正解想出来 紫菜 \times3。

day2

这回长记性了，提前 1h 到考场了。

开 T1，用特殊选点构造二维凸包，写了个对拍，发现大寄，概率只能拿到 75pts 于是上了个厕所，想到可以优化到，枚举两个点，再来做就能拿到 83pts 剩下的会超时。

通过某点特殊性质可以相当扩展欧几里得，让后搞到min25杜教筛，轻松水过。

第二题速放弃。

开 T3 通过线段树维护斐波那契额数列，在对值按题意求斯特林数轻松水过

回头看第二题，用初中的数学知识求出错排使用 Lyndon 拿到 48pts 紫菜 \times4。

总分 100+100+73+100+48+100=521pts 紫菜 \times5。

拿到 9 个徽章太帅了！！！！！！！！