Slope

题面

考场

首先读了下题，题意是找出斜率最接近 $\large\frac{P}{Q}$ 过两点直线的斜率·。

那么直接看一下一条直线的斜率和 $\large \frac{P}{Q}$ 的差是什么：

$\Large \Delta=|\frac{P}{Q}-\frac{y_1-y_2}{x_1-x_2}|=|\frac{P(x_1-x_2)-Q(y_1-y_2)}{Q(x_1-x_2)}|=\frac 1 Q|\frac{(Px_1-Qy_1)-(Px_2-Qy_2)}{x_1-x_2}|.$

当我们转化成这样的时候，就发现分子上的部分括号内的只与某一个点有关.

那么对于每一个点，就可以记 $\large w_i=Px_1-Qy_1$ ，那么这里的 $\Delta$ 在忽略前面的常数之后就相当于：

$\Large \Delta = |\frac{w_1-w_2}{x_1-x_2}|.$

这个式子的形式也可以看作是过两个点的直线的斜率了。我们问题就转化成求过两点的直线的斜率的绝对值最小。

这个问题就好求了，直接将所有点按照 $w_i$ 排序，然后只需要考虑每个点后面的那个和它相邻的点统计答案即可。

为什么呢？首先他前面的点跟他统计过一次答案了，所以只需要统计后面的。那么为什么在排序之后答案是最优的呢？考虑点 $i$，那么记它和 $i+1$ 连成的直线的斜率是 $k$ （不妨设两点间斜率均大于零），那么如果 $j$ 和 $i$ 有更优的答案，我们发现 $i+1$ 和 $j$ 会更优，证明如下：（其实画图很好理解）

不妨设 $i:(0,~~0),~~ i+1:(x_1,y_1), ~j:(x_2, ~y_2).$ 那么有：
$\Large\frac{y_1}{x_1}>\frac{y_2}{x_2}\\\therefore y_1x_2>x_1y_2\\\therefore y_1x_2-x_1y_1>x_1y_2-x_1y_1\\\therefore (x_2-x_1)y_1>(y_2-y_1)x_1\\\therefore \Large\frac{y_1}{x_1}>\frac{y_2-y_1}{x_2-x_1}$
得证。

程序就记一下如果相等取 $k$ 的 $\min$ 就好了。

出分：$100pt.$

$code:$ https://paste.ubuntu.com/p/MVB39949PK/

Min

题面

考场

第一次讲课讲 $DP$ 的时候好像说过很多种这一类题，那么考虑一个朴素的 $DP.$

$f_i$ 表示最后一个区间以 $i$ 结尾的答案，那么转移就枚举最后一个区间左端点即可。具体就是：

$\Large f_i=\max\limits_{j=0}^{i-1}f_j+F(\min\limits_{k=j+1}^{i} a_k).$

然后就是区间最小值了， $ST$ 表即可。

对于那个特殊条件，对于样例稍加改动看了看函数值，发现这个时候只有当前一个数能自成一段时转移，否则跟前面合并。

出分：$20pt.$ 暴力挂了。不知道为什么。

正解

因为只需要求之前的，并且右端点严格递增的区间最小值，因此可以用一个单调线性数据结构维护，考虑到没有对长度的限制，所以用单调栈维护就好。每一次只要维护一个位置的关键字即可。那么我们考虑答案在哪里。

首先答案如果是在栈上面维护的点之外的地方，那么肯定可以在它靠右的最近的一个点上有不劣的答案。那么我们只需要在关键点上更新信息就好。那么我们可以考虑维护每两个相邻关键点中间的区间中的 $f$ 值，而在不断弹出栈顶的时候可以一起记下他们的 $f$ 来继承他们的贡献。因为我们设的 $f$ 是一个前缀的答案，所以可以直接用栈顶来更新当前的 $f_i$，需要注意的是这个点单独成一个区间也需要考虑。

那么写起来就较为容易了。整体而言不算是很难的 $dp$ 优化，但是细节很多了。

$code:$ https://paste.ubuntu.com/p/wGNYdXZg65/

Swap

题面

考场

是一道有趣的题目，一开始的想法是找逆序对然后直接暴力交换，开始写的时候发现不好写。。

然后随便糊了一个特别慢的东西。就交了。

出分：$0pt.$

其实逆序对是可以搞的啊，只要把$B$ 关于 $A$ 类似离散化一下就好了啊。。没想到吧。

正解

神奇的做法。

首先他说的交换好像很玄学，所以只需要考虑两两交换即可。~~那你说什么最大最小值。。~~

那么因为是两两交换，所以交换是可逆的，因此可以通过把 $A,~B$ 变成有序的，再把变换 $B$ 的序列反过来即可。

现在要求的就是多少次交换之后能够让整个变得有序了。什么排序算法呢？冒泡，快排，归并，堆？

快排的交换好像无法实现，堆就不说了。那考虑归并排序。

分治就普通分治就好，关键是怎么合并。假设我们已经有了两个有序的序列，现在就是要把它们合成一个。

出题人的想法很神奇。我们先让问题好描述一点。对于两个有序序列 $A,B$ 需要让他们通过交换操作变得有序。这里大概借用快排的思想，就是用一个基准数 $x$。找出一个 $x$ 之后，在 $A$ 中找出所有的比它大的序列，拎出来，$B$ 中比它小的序列，拎出来。然后我们发现问题又分半：$A$ 的剩下部分和 $B$ 拿出来的部分都 $<x$ ，剩下两部分都 $>x$ 。但是还有问题：他们不挨着。那么交换就上场了，我们可以通过首尾的交换把 $A,B$ 拿出来的部分分别反转，然后再整个翻转他们两个大区间，（通过选首尾的区间慢慢向中间选，具体可以画图。）这样两部分相互分开了，而内部就连在一起了，这样两边再分治下去，最后再连起来，就是一个有序的序列了。

复杂度呢？因为每一次合并的复杂度也需要分治，每一次翻转是 $O(n)$ 所以单次合并是 $O(n\log n)$ ，所以总复杂度是 $O(n\log^2n)$ 的。对于 $4096$ 的数据 $345678$ 就够了。

$code:$