NOIP2024 游记

Day -2

下午 SDFZ 举办了活动，但我没去，可恶。

Day -1

怎么有人 NOIP 前一天还在考 whk 啊。

Day 0

考场在福州三中，机房十分拥挤。忽然发现 Frc 登不上去，遂汇报监考，换了台机子，直接畅享 3 连座位。但是怎么还有人电脑坏了啊，3 连座位没了，早知道迟点汇报。

发压缩包密码，猜测题目顺序是 edit-assign-traverse-query（猜对了）。

提前两分钟开考。扫了一眼 T1 发现不是很妙，只知道交换相邻两位等价于任意排序。想了一下，求出每个长度大于 1 的区间内 0/1 的个数，然后贪心就可以了。

过去 5 分钟，开始狂写，写了 127 行，但一遍就过了样例，刚好 8:58，用了半小时。

继续 T2，发现 n,v 极大，卡住了。手玩了半小时，什么都没看出来，然后去装水，装完还是没想出来。过了 1 小时又去上厕所，上完厕所发现可以相邻两个数分别处理，然后乘起来。于是就做出来了，WC 好闪，拜谢 WC。转眼已经 11 点了，好可怕。

看 T3，手玩了一下菊花图情况，发现怎么弄都没过样例，于是放弃，直接输出 1 跑路。

看 T4，一眼 RMQ 可以做到 O(n\log n+qn)，但是由于我是口胡选手，不会 O(1) 求 LCA，甚至连倍增 LCA 都是现场手玩 5 分钟玩出来的。然后 ST 表也是现场手玩出来的，测了一下，感觉没有问题，想正解。然而，我的 ST 表是这样写的：

for(int j=1;j<=20;j++)
    for(int i=1;i<=n;i++){
        lca[j][i]=fnd(lca[j-1][i],lca[j-1][min(i+(1<<j-1),n-(1<<j-1)+1)]);
    }
}

我原本是特判的，后来唐了，手贱给它改成这样了。这样会访问负数下标，属于 UB，导致我 T4 随机挂分。并且赛时通过了所有大样例，在这里提醒大家：牢记板子，不要乱写。

正解想不出来，结束。估分 100+100+4+[0,32]=[204,236]，怎么有可能比 CSP-S 还高啊。

Update：分数 236，没有挂分！