除了D都有简单做法了(
A
埃筛。
B
数位dp。
C
考虑这个操作等价于任意重排差分数组,于是我们考虑什么样的重排可以让答案最小。
注意到是方差,贪心地,我们一定是放一个双调的,也就是先增大然后减小,这样可以快速逼近平均值而慢速离开平均值。
然后你发现第一项和最后一项都不能动,所以我们可以从大到小枚举差分数组的一项,决策加到左边还是右边。
枚举一个平均值,于是贪心地,我们希望加到离平均值更远的那一边。平均值的枚举是\(O(nv)\),贪心是\(O(n)\),总共是\(O(n^2v)\),可以通过88pts。
要拿到100pts也很简单,只需要把差分数组中相同的合并成一个,每个都是先加一边然后轮流加,这个可以\(O(1)\)计算。变成了\(O(nv^2)\)。
然而只写了88。感觉要被乱搞干翻了?
(然而假了,你谷wa了三个点。感觉要被卡成0了?)
D
考虑倒过来做变成加点。
第一类边不管怎么样都是显然的。
考虑只有障碍和第三类边怎么做。我们用并查集维护连通块,每个连通块开一个线段树维护能走到的每个level的点是否存在,这里为了避免算重需要先按下标为第二关键字排序一遍,重新分配一个level。合并连通块的时候可以线段树合并。
加入第二类也很简单,用set维护上下左右走到哪,然后一个点可能算两次,我们每个连通块再开两排线段树,分别维护每一行和每一列的区间和,合并的时候vector启发式合并,线段树直接合并,复杂度是一个\(\log\),然而空间大概飞了。
码量预计超过5kb。
今年直接飞了。预计100+100+88+0。完蛋了。
D最后1h rush 24pts,结果没rush出来。咋回事呢?
C切了还是很爽的(然而被峰说假了?不知道,静待fst)(确实fst了,所以我是该希望数据强还是弱呢?)。但是当场也没写100pts,痛失12pts。
被爷们吊着打了/hanx
你谷100+100+76+0。看起来只可能更低了。已经退役了吗?