20220730NOI模拟赛--考后总结

时间安排

7:30–7:35 读题。
7:35–7:50 T1,暂时没什么思路，可能用到一些矩乘的性质，先做后面的。
7:50–8:00 T2,肉眼观测应该可以扫描线。先做后面的。
8:00–9:00 T3,有几种想法，一个是做背包，不过着时间和空间都很炸，而且没什么前途。另一种做法是考虑确定k个 $ai$ ，那么中间的部分是个类似于阶梯的东西，如果这个能求出来就好做了，但是不会快速求，只好对这玩意另外做一个DP。
9:00–10:00 T2,想要用某种数据结构对每个点存储询问感觉不可能。考虑能不能确定询问编号，发现可以离线扫描线，那么询问就变成了查询第一个后缀和为 $k$ 的数，这玩意不是很好求。想到二分，但是后缀和貌似不满足单调性，莫名想到线段树套可持久化吉司机线段树的阴间玩意，时空复杂度根本不对。
10:00–10:30 T1暴力。
10:30–12:30 T3,发现对于部分分背包常数较小，改为背包。
赛后: T3部分分和 wxq 写的一模一样，偏偏 Ta 能拿60,而我只能拿 30 ，离谱啊。

回顾&反思

T1: 没有想到临接矩阵，想到后就容易了，tarjan就可以了。转化模型这一块还是不足。部分分方面用bitset优化貌似能多拿些分，不过比赛的时候没往这上想(毕竟复杂度很紧)，这个trick还要牢牢掌握。
T2:离线和扫描线都想到了，主要困难在怎么二分，然而发现如果一个 $k$ 出现了，那么任意小于 $k$ 的非负整数一定在之前出现过，又因为我们要找的是第一个 $k$ ，所以可以变为二分最大后缀和，将对操作维建立线段树可以简单维护。还是死在了性质这一块，有些比较显然且关键的性质自己有时发现不了，这一块要加强。
T3: 想到类似阶梯的东西了，不过没想到分治。不过分治后要多项式推导，还要得出与 $k$ 有关的一个神仙结论，感觉自己比赛的时候做不出来。