【游记】 NOI Online 2021 游记

考前成功为自己攒够了人品。(指前几天的模拟赛统统爆零)

8:30 拿到题面……还好服务器没卡。

一看三个题,都是 256MB,最后一题 2s,不开 O2 屑人吧!

然后一个一个题看:

T1 计数,没啥思路,不过这个构造方式非常的格雷码。

T2 看起来非常可做,不过粗略看过去感觉题意不太清楚。

T3 看就非常数据结构,根据 2s 可以判断大概是 (O(n log n log v))

根据前几次 NOIO 的经验,这个计数既然在第一题,那必然不是很难。于是开做,发现啥也不会。成功浪费 30min。

然后果断跳 T2 去了,细致阅读了一遍题面,参看了一下样例,感觉就 (O(n^2)) 大暴力就行了。(一开始还以为要啥 SAM 或者子序列自动机之类的)

写完 hash 之后测个样例过了,觉得不太保险,手动搞了几个大数据卡一下 hash 碰撞,跑得飞快。最后我双模数分别是 (19260817)(1145141919810817),感觉应该不会撞了。

然后面临抉择,开哪个题呢?

想都不想,肯定开 T3 呗,T1 这计数我已经完全放弃了。

这个 T3 有个异或,十分 trie 树。

于是往 trie 上面去想,依次思考了一下 (b le d)(d le b) 的部分分(过程大概是这样的),然后喜闻乐见树套树被卡了空间……

不过好像套个 CDQ 之后就能直接做了。

上手赶快敲代码,感觉自己代码能力极度退化,这玩意居然还写了一个小时……

写完之后样例过了 qwq。准备去开 T1 的,然后我的潜意识告诉我:“这种没大样例的比赛得对拍。”然后就开始对拍。

果不其然,写个暴力开始对拍,上来第一组数据就 WA 了。

不过奇怪的是只错了一组询问,而且答案只差 1。

我马上意识到是 (b=d) 的情况被算了两遍,去改了一下比较函数就过了。感觉没什么 bug 了,就把对拍挂着开 T1 了。

转眼就剩一个小时了。

我开始各种猜测 T1 的复杂度,(O(klog n)) 看起来非常的不对劲,我怀疑是 (O(log n + k^3)) 的。但我自然是想不出做法的。

于是开始搞暴力,先打了个 (log n le 20),然后写了个 (k=0) 的数位 dp。

接着就开始拆多项式,斯特林数组合数试了一遍,感觉组合数有戏。

然后继续敲 (O(k^2 log n)) 的数位 dp,好家伙,样例 WA 了。

只剩 5 分钟了,果断放弃,开始检查文件啥的。

仔细一看,发现我 (k=1) 的部分分是求的 ([0,n]) 的答案而不是 ([0,n)) 的。马上加了个特判……

我等着时间一秒一秒地过去。

坐在我旁边的 waaitg 还在疯狂地调试他的 T1,他改掉了一个错,按下清脆的 F11,测样例,很好,是对的。

他打开了提交界面,不幸的是,考试结束了。如果再早个 20 秒,他就能交上去了吧。

如果 CCF 的样例复制出来不带行号的话,一场考试总能节省 20 秒出来吧。


洛谷测了一下:15 + 100 + 100。

T1 直接给我挂傻了。

不过我可以说这是我发挥最满意的一次 CCF 组织的比赛吗。

希望傻逼题 gkd,神仙推式子 gck!!!

原文地址:https://www.cnblogs.com/imakf/p/14587485.html