短路

By matthew99

算法一

直接暴力 dfs，复杂度指数级，期望得分 10 分。

算法二

用最短路算法，复杂度 $O(n^2\log n)$，根据实现情况可以获得 10 至 30 分。

算法三

猜想只能往右或者往下走，然后做一个 $O(n^2)$ 的 DP，可以获得 30 分。正确性证明参见算法五。

算法四

在算法三的基础上进行对称性优化或者使用滚动数组，可以获得 50 分。

算法五

我们考虑假设我们要从左上角走到从外到内第 $i$ 层任意一个中继器上，那么我们最少需要多少代价呢？显然我们一共最少走 $2i-2$ 步走到 $(i,i)$ 上。其中，第 $1$ 层到第 $i-1$ 层每层都必须经过至少一个中继器，除了这 $i-1$ 步，还要再走恰好 $i-1$ 步。

我们发现剩下来的 $i-1$ 步至少要走的是 $1$ 到 $i-1$ 层的前缀最小值之和，为什么呢？考虑一条走到第 $x$ 层某个给定位置且只到过前 $x$ 层的最短路径，那么该路径的最后一步要么是从第 $x-1$ 层走下来，要么是在第 $x$ 层又逗留了一次。如果是后者，我们总是可以把这最后一步挪到前面去走，相当于对于某个 $k$ 在第 $k$ 层先走了这一步，然后把这一步之后的路径平移一下而不影响平移的这段路径的总时间，这样代价变化就是第 $x$ 层的 $a$ 与第 $k$ 层的 $a$ 的差值。这样我们就推出，如果第 $x$ 层的 $a$ 不是前缀最小值，那么肯定不是最短路径。因此，最短路径肯定不会在不是前缀最小值的层停留超过 $1$ 次，于是这条最短路就是把所有的前缀最小值所在的层的最左上角的点用 L 型的曲线连起来的路径。

那么假设我们走到的最深的一层是第 $x$ 层，首先第 $x$ 层不是前缀最小值的话那么一定不是最短的。如果是前缀最小值，那么最短路径就是先走到第 $x$ 层左上角，再绕一圈绕到第 $x$ 层右下角，再走出去（代价和走过来是一样的）。

这样，我们暴力枚举 $x$，走到第 $x$ 层的代价可以在线计算，然后每次更新答案即可。

时间复杂度 $O(n)$，期望得分 100 分。

同样的我们也证明了算法三的正确性。

怎样，是不是一个超级送分大水题呢？

天路

By zhj, vfleaking，题解 By vfleaking

什么鬼？

嘿嘿嘿……vfk 又来出题玩玩了。事情是这样的，我和 zhj 发现了一个好玩的 idea，然而我并不知道怎么套个优雅的模型。这时 zhj 拯救了世界，于是就出出来了。

哎说实在的过去的一年给 CCF 出题有点心累，在自家 UOJ 上出题各方面还是爽多了2333……

依稀记得 NOI2016 讲题时我兀自地讲讲讲，台下纠结分数线的梦想们并没有多少热情听。后来当我看到分数线公布以及签约的现场有点百感交集，感觉给 CCF 出一次题的事情多，责任也好重……在 UOJ 上自己随便出出出题至少不会直接影响选手痛失金牌。

但愿我出的萌萌哒题目们都能让大家有所启发吧。

谜之声：怎么近似算法都出到 OI 里啊？这真 NOIP 难度？

咳咳客官别急，往下看。敢承诺这个近似算法非常 NOIP 向，并不是那种数学大不等式乱搞证 bound 型。

算法一

对于 1 号测试点，$n\le 100,a_i\le 100$。

大暴力！

你会使用 for 循环吗？

时间复杂度 $O(n{V}^2)$，可以获得 10 分。（其中 $V$ 为权值范围）

算法二

对于 1,2,3 号测试点，$n\le 100$。

权值范围好大啊……

不要慌，你可以先枚举 $k$，然后枚举 Nokia1050 是在哪一段时间连续拦截了 $k$ 次攻击嘛……该区间中高度的最小值和最大值作为高度区间。

你会使用 for 循环吗？

时间复杂度 $O(n^3)$，可以获得 30 分。

算法三

对于 4,5 号测试点，$n\le 1000$。

在算法二基础上，把每次扫一遍求最小值最大值改为 for 的时候乱维护维护就行了……

（而且 $O(n^3)$ 常数好就过了呢）

（感觉在 CCF 系列比赛这样送分会被选手喷的……hhh）

时间复杂度 $O(n^2)$，可以获得 50 分。

算法四

对于 6,7 号测试点，$n\le {10}^5$。

诶数据随机？

同学们你想到了什么！随机数据的前缀最小值只会变化 $O(\log n)$ 次对吧！

所以当我们固定左端点移动右端点时，区间内最大值与最小值至多只会变化 $O(\log n)$ 次。

拿个单调栈维护一下……每次给对应的长度区间更新答案。

脑抽选手可以使用线段树，但其实由于答案单调，所以可以变成给一个长度的后缀更新更新，于是就能 $O(n\log n)$ 的复杂度了。

可以获得 70 分。

算法五

还是数据随机的情况，观察数据我们注意到如果区间长度够长，那么答案就非常接近${10}^6$。

所以我们设一个几百左右的值 $l$，然后处理小于 $l$ 时的答案，剩下来的输出 ${10}^6$ 即可。

同样可以获得 70 分。

算法六

好了好了所以之前的部分分跟近似算法都没什么关系……

这题应该怎么近似呢？你想，要是直接把权值除以一个大常数，做完之后再乘回来，看上去好像很近似！但是冷静冷静就会发现这样做出来是个绝对误差的，如果碰到 $$233333-233332=1$$ 这种就 GG 了。

所以……相对误差，看上去很没头绪。

来来来先把近似算法扔进垃圾桶，来想想如果要你求出准确解，你可以怎么做。

一个思路是，我们应该是枚举一个 $k$ 然后某种方式维护一下，但这个看上去就很没办法改造为近似算法。

诶，那如果告诉你一个常数 $c$，我们来把答案 $c_k$ 划一划范围好像很兹瓷啊……那 $c_k\ge c$ 可做吗？

……好像是可做的诶，因为最终的答案肯定是单调递增的，所以范围肯定是一段连续的 $k$。我们可以两个指针再开两个栈乱扫扫，左端点往后挪一挪，右端点也往后挪一挪……就能把 $k$ 的范围求出来了。

嗯很好，于是我们就可以每次找找 $c$，划分 $k$ 的范围。当范围足够小的时候，就可以把这一段的 $k$ 都用同一个数近似了。

事实上，你只需要取： $${1.05}^0,{1.05}^1,{1.05}^2,{1.05}^3,\dots$$ 就可以啦！每一段里面随便找个数当答案一定不会超过相对误差的容许范围。

现在还差一个想题时的直觉 —— 就是需要划分的段很少……只要注意到其实段数是 $O(\log V)$ 级别的……23333333……别看人家 $1.05$ 小，但人家也是个指数函数。

中间找到 $k$ 的范围只需要 $O(n)$ 时间乱扫，所以总时间复杂度是 $O(n\log V)$。如果把 $5\mathrm{\%}$ 当做变量 $ϵ$，那么时间复杂度就可以写为 $$O(n{\log }_{1+ϵ}V)=O(n\log V/\log (1+ϵ))=O({ϵ}^{-1}n\log V).$$

这个算法其实说明，所有 $f(i)$ 随 $i$ 递增且有个算法告诉我 $f(i)\ge k$ 的第一个 $i$ 在哪里的话，都可以套这个近似算法！（然并卵）

噔噔！这题就做完了！相信比赛时很多选手都轻松 AC 啦～

（为什么一道水题的题解我能写这么长）

套路

By matthew99

算法一

枚举区间，再枚举区间内两个数统计这个区间的答案，再求出整个问题的答案。时间复杂度 $O(n^4)$，期望得分 7 分。

算法二

用 $\mathrm{ans}[l,r]$ 表示区间 $[l,r]$ 的答案，很容易发现 $\mathrm{ans}$ 可以由如下递推式算出： $$\mathrm{ans}[l,r]=\{\begin{array}{ll}|a_l-a_{l+1}|& r-l=1,\\ min\{|a_l-a_r|,\mathrm{ans}[l+1,r],\mathrm{ans}[l,r-1]\}& r-l>1.\end{array}$$

时间复杂度降为$O(n^2)$，期望得分20分。

算法三：

注意到如果 $m\le 1000$，那么根据鸽巢原理，长度超过 $m$ 的区间肯定有两个相同特征值相同的跳蚤，因此答案是 $0$，所以我们处理长度小于 $m$ 的区间即可。

时间复杂度为 $O(nm)$，期望得分 27 分，结合算法二可以获得 40 分。

算法四：

使用任何一种时间复杂度为 $O(n\sqrt{m+n}(\log m+\log n))$ 的算法（请注意大O符号的意思），即可获得至少 $70$ 分。由于这些算法过于复杂且与标算没有太大关系（或者是标算强行多写了一个 $\log$），故不再赘述。

算法五：

我们考虑如果区间长度是 $x$，那么最小差不超过 $\frac{m}{x-1}$。

设一个常数 $S$。

如果 $x\le S$，则用类似算法三的方法，可以做到 $O(nS)$。

如果 $x>S$，那么最小差不会超过 $\frac{m}{S-1}$。我们扫描一遍序列，考虑当前位置作为右端点，用 $r_x$ 表示权值为 $x$ 的数最后出现的位置，然后每次新加入一个数 $z$ 之后，对于所有 $|z-y|\le \frac{m}{S-1}$，利用 $r_y$ 进行计算更新答案，然后 $r_z$ 即可。时间复杂度为 $O(n\frac{m}{S})$。

设 $S=O(\sqrt{m})$，则总时间复杂度为 $O(n\sqrt{m})$，可以获得 100 分。

这是不是 UOJ 历史上最水的C呢，相信大家 AK 得非常的爽，作为出题人之一看到大家 AK 我也感到非常荣幸。

UPD：好像打脸了。