欸批唉哦2026

Coffins · 2026-05-10 00:31:10 · 生活·游记

最后一次 NOI 前的最后一次比赛

Day -1

到达宾馆，室友是lyz，啥也没干一直疯狂摆摆摆。

Day 0

由于要吃饭，没有办法翘课在宾馆蠕动了。

LN 集体画猜。

讲课好多神秘科技，nzb，原地爽睡。

只有何大哥的课全听下来了。

开幕式发现肚子的丢失，但是刷新了了杜小德，绷不住了。

节目很牛，这就是京爷吗，吓哭了。

晚上回去发现什么板子都没打，敲了下 SA，点双，NTT，FWT。

23:00 就闭灯了，结果还是玩小手机到 23:30 才睡。

Day 1

被迫早起，嗓子疼，感觉有点爆。

依旧有点时间就集体画猜，绷不住了。

准备开题，结果设备有问题，集体延时了 10min。

感觉有点困，在桌子上趴了一会，结果一睁眼就是 9:13 了，无敌了，希望没有伏笔。

开题，阅读 A,B,C，分别是计数，交互，数据结构。

看了看 C 好像不是很好搞的样子，但是 O(nq) 40 分，链还有 8 分，决定先扔了。

看 A，想了半天好像延迟钦定一下子就好了，于是编细节，仔细想了想好像差不多 O(n^4) 那样，写写写，然后发现其实要 O(n^{10000})，还不太好写，决定先放一放。

此时已经过去了 1h+，会了 0 非平凡分。

被迫看最不喜欢的交互，结果完全没思路，爆爆爆。

想了想 sub2，感觉很有启发啊，于是发现可以把 1 到 W 全扔进去，此时这 W+1 个数就相当于对 1,2,...,W+1 的一个后缀做减一得到的结果，考虑每次选两个位置求他们的和，会发现只会是原来的和减去 0/1/2，于是就可以根据这个三分了，有 70pts。

现在只剩 sub3，发现应该要二分，想到把 1,1,2,...,2^{29} 加进去，但是这样还需要找要查询数的位置，不过发现倒着做可以让两部分之和不超过 30 次，于是就做完了，此时 0+100+0，过去了 2h。

感觉应该猛冲 A 了，于是先把 C 的 40 写了，8 分有空再写。

又看了看 A，先把特殊性质敲了，然后发现好像在逆排列做上复杂度很对，于是冲刺。

写写写，发现还是 O(n^{10000})，不管了能过 n\le50 也行，猛冲。

此时还有 2.5 h，优势在我。

写了一万年搞出来一坨，过样例了，一测零蛋，爆。

于是开始瞪眼大法，瞪出来 inf 个错误，然而还是 WA，只能对拍了。

还有 1.5h，优势在我（？

发现 O(2^nn^2) 暴力调不对，日你哥啊破防了。

终于对了，拍拍拍，拍出来了，发现有一个地方组合数两维写反了，一交还是 WA。

我已急哭，拍出来一组 n=10，手动模拟了半天模拟了个滚木出来，那咋办。

没招了，继续捋了一遍思路，发现有个组合数没有乘，难道说有救了？

没有救，还是 WA，爆爆爆。

哦好像乘错东西了，改了一下，终于通过了 n\le50，此时还有 20 min。

思考了一下瓶颈可以二维前缀和优化掉，于是通过了 n\le150，此时还有 10 min。

精细分析发现复杂度是 O(n^4) 的，不过有一个地方可以拆出来，就变成 O(n^3) 的了，但是时间不够了，爆。