日记

昨天晚上睡得实在是太晚了，然后中午玩爹 5 弘文过头了，直接睡了一下午。

Serval and Colorful Array (Easy Version)# Link to

感觉这题不值 2600。虽然我还是没做出来

我们考虑一个字串怎么来。显然最优的情况是中间的一个数不动，然后两旁的挪过来。我们枚举每个可能的中间的数 $a_{pos}$，然后对于 $\forall i \in [1,k]$，$O(n)$ 处理 $l_i,r_i$ 分别表示左边离 $pos$ 最近的 $i$ 离 $pos$ 多远，右边离 $pos$ 最近的 $i$ 离 $pos$ 多远。现在的问题就是，如何选择使得 $\frac{k}{2}$ 个 $l_i$ 和 $\frac{k}{2}$ 个 $r_i$ 加起来最小。我们先钦定都选左边的，答案就是 $\sum\limits_{i = 1}^{k}l_i$，再记录一个 $c_i = r_i - l_i$，我们将 $c$ 从小到大排序，最终的答案就是 $\sum\limits_{i = 1}^{k}l_i + \sum\limits_{i = 1}^{\frac{k}{2}}c_i$。别忘了减掉多算的 $\sum\limits_{i = 1}^{k}|i - \lceil\frac{k}{2}\rceil|$。

后日谈 # Link to 后日谈

做又臭又长的世界任务，刚刚被新地图震撼，一看锚点数量直接原地爆炸。

不管了，做什么世界任务，做题！