noip2021题解及游记

/fn

Posted by ShanLunjiaJian's Blog on November 20, 2021

除了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。看起来只可能更低了。已经退役了吗?