====== Contest Info ======

date: 2020-07-18 12:00~17:00

[[https://codeforces.com/group/azDPdoF24f/contest/288496|2020-2021 BUAA ICPC Team Supplementary Training 01]]

[[https://codeforces.com/gym/100886|2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest]]

====== Solutions ======

===== A. Three Servers =====

**题目大意**：3 台机器，我们要分配 $n$ 个任务给机器，每个任务分一个机器即可，占用该机器 $t_i$ 个单位的时间。3 个机器各自被占用的总时间中，我们需要让最大和最小的差尽可能小。问方案。

**题解**：

考虑贪心地去构造，会发现总有办法能限制答案在 $t_i$ 的最大值以内。因此在最优方案中，三台机器各自被占用的总的时间中的最大值不会超过 $t_i$ 的和除以 $3$ 加 $t_i$ 的最大值。

想 DP 记方案？没门，内存不够。其他的队伍有用 bitset 先记一下可行性，然后隔着记录或者想办法再把转移拿回来。

我比较菜，想了一下我一个一个加，那么假装我加的过程中，最大和最小的差不会太大。那么 DP 的状态就是记录现在插第 $i$ 个、最大减最小的值 $u$、次大减次小的值 $v$。然后假装最大和最小的差是在某个范围内，强行 DP。甚至记录了一大摞东西。

队友表示可以 shuffle 一下，正常地插总有办法卡我，但是我随机刷一下他就卡不住了。然后把 DP 记得东西改用 short 存，就卡过去了。

===== B. Game on Bipartite Graph =====

**题目大意**：

**题解**：

===== C. Black and White Board =====

**题目大意**：

**题解**：

===== D. Catenary =====

**题目大意**：

现有 $n$ 个质量均匀分布的棒子，头在 (0, 0) 点挂着，尾在 (L, 0) 点挂着，然后让整条链自然下垂，求每个点自然下垂稳定之后的位置。

**题解**：

不会奇奇怪怪的东西，我只知道自然下垂时，必然总体的重力势能是最小的。

记长度单位为米，棒子每米的质量为 $m_0$，重力势能为 $g$。

记 $\alpha_i \in [0, \pi]$ 为第 $i$ 个棒子和重力方向的夹角。写出来每个点的坐标，写一下重力势能，限制一下最后一个点的坐标为 $(L, 0)$，用拉格朗日乘数法，我们需要最小化：
$$
P\left(\vec{\alpha}, \lambda'_1, \lambda'_2\right) = \left(\sum_{i=1}^n{-m_0 l_i g \left(\frac{1}{2} l_i \cos{\alpha_i} + \sum_{j<i}{l_j \cos{\alpha_j}} \right)}\right) + \lambda'_1 \left(\left(\sum_{i=1}^n{l_i \sin{\alpha_i}}\right) - L\right) + \lambda'_2 \left(\sum_{i=1}^n{l_i \cos{\alpha_i}}\right)
$$
相当于最小化：
$$
F\left(\vec{\alpha}, \lambda_1, \lambda_2\right) = \left(\sum_{i=1}^n{-l_i \left(\frac{1}{2} l_i \cos{\alpha_i} + \sum_{j<i}{l_j \cos{\alpha_j}} \right)}\right) + \lambda_1 \left(\left(\sum_{i=1}^n{l_i \sin{\alpha_i}}\right) - L\right) + \lambda_2 \left(\sum_{i=1}^n{l_i \cos{\alpha_i}}\right)
$$
偏导：
$$
\begin{array}{rcl}
\frac{\partial F}{\partial \alpha_i} &=& \frac{1}{2} l_i^2 \sin{\alpha_i} + \sum_{j > i}{l_j l_i \sin{\alpha_i}} + \lambda_1 l_i \cos{\alpha_i} - \lambda_2 l_i \sin{\alpha_i} \\
&=& l_i \sin{\alpha_i} \left(\frac{1}{2} l_i + \sum_{j > i}{l_j}\right) + \lambda_1 l_i \cos{\alpha_i} - \lambda_2 l_i \sin{\alpha_i}
\end{array}
$$
$$
\frac{\partial F}{\partial \lambda_1} = \left(\sum_{i=1}^n{l_i \sin{\alpha_i}}\right) - L \\
\frac{\partial F}{\partial \lambda_2} = \sum_{i=1}^n{l_i \cos{\alpha_i}}
$$

目标是让偏导都为 $0$，但容易想到实际上偏导均为 $0$ 应该是有两个解。另外一个是取最大值，那种情况下必然 $\alpha_1 > \frac{\pi}{2}$。所以我们限制一下 $\alpha_1 \in [0, \frac{\pi}{2}]$。

考虑一下 $\alpha_{i} > \alpha_{i+1}$，容易发现如果我们将第 $i$ 个棒子的起点和第 $i+1$ 个棒子的终点用线段连起来，会发现两个棒子都在这个线段的上方，但是我们如果让两个棒子根据这个线段对称一下，就能得到重力势能最小的解。因此在最小化重力势能的情况下 $\alpha_{i} \le \alpha_{i+1}$。

记 $x_i$ 为：
$$
x_i = \frac{1}{2} l_i + \sum_{j > i}{l_j}
$$
$x_i$ 的差分是两个棒子长度和的一半，所以 $x_i$ 单调递减。

我们先令 $\frac{\partial F}{\partial \alpha_i} = 0$，容易发现只要前两个角度不同，就可以直接解出 $\lambda_1$ 和 $\lambda_2$。

假设 $\alpha_1 < \alpha_2$ （即 $\alpha_1 \ne \alpha_2$），有：
$$
\lambda_1 = \frac{\left|\begin{array}{ccc}
-x_1 \sin{\alpha_1} & -\sin{\alpha_1} \\
-x_2 \sin{\alpha_2} & -\sin{\alpha_2} \\
\end{array}\right|}
{\left|\begin{array}{ccc}
\cos{\alpha_1} & -\sin{\alpha_1} \\
\cos{\alpha_2} & -\sin{\alpha_2} \\
\end{array}\right|}
= \frac{\sin{\alpha_1}\sin{\alpha_2} \left(x_1 - x_2\right)}{\sin{(\alpha_1 - \alpha_2)}}
$$
$$
\lambda_2 = \frac{\left|\begin{array}{ccc}
\cos{\alpha_1} & -x_1 \sin{\alpha_1} \\
\cos{\alpha_2} & -x_2 \sin{\alpha_2} \\
\end{array}\right|}
{\left|\begin{array}{ccc}
\cos{\alpha_1} & -\sin{\alpha_1} \\
\cos{\alpha_2} & -\sin{\alpha_2} \\
\end{array}\right|}
= \frac{x_1 \sin{\alpha_1} \cos{\alpha_2} - x_2 \cos{\alpha_1} \sin{\alpha_2}}{\sin{(\alpha_1 - \alpha_2)}}
$$

利用 $\frac{\partial F}{\partial \alpha_i} = 0$，可以解得 $\alpha_i$ 是以 $-\lambda_1$ 为对边、以 $x_i - \lambda_2$ 为临边的直角三角形中的角，可以用 atan2 来解。因为 $x_i$ 是单调递减的，所以这样直接解出来的角度也是单调递增的。

到现在我已经分析的是头昏眼花，所以接下来的只能猜一下了。想象一下，如果 $\alpha_1$ 固定了，那么随着 $\alpha_2$ 的变化，我们通过上面的方式计算一下最后一个点的坐标，这个点划过的轨迹必然是一个连续、光滑的曲线，我们需要一个可以三分的目标函数，这个目标函数越小，就表明最终一个点越接近 $(L, 0)$。

最后就只能各种距离函数都试一下了 XwX，不过确实轨迹上的曲率很难确定，而且轨迹是光滑的，因此像切比雪夫距离、曼哈顿距离之类的，在确定的距离下图形不是光滑的距离函数会比较适合。

最后发现三分第一个角套三分第二个角，最小化最终一个点到 $(L, 0)$ 的切比雪夫距离能获得正确的解，晚安。

===== E. Evacuation Plan =====

**题目大意**：

**题解**：

===== F. Empty Vessels =====

**题目大意**：

**题解**：

===== G. Maximum Product =====

**题目大意**：

**题解**：

===== H. Biathlon 2.0 =====

**题目大意**：

**题解**：

===== I. Archaeological Research =====

**题目大意**：现在有一个长度为 $n$ 的序列，知道从某个位置开始，到另外某个位置上会出现一个新的值。要你恢复出来字典序最小的序列。

**题解**：

不考虑字典序最小，$1, 2, 3, \ldots$ 就是符合条件的答案，因此绝对有解。

显然，对于第 $i$ 个元素，如果表示它是从 $l_j$ 开始的一个新的值，那么它取没有出现在这些值中的最小值即可。（我一开始想成最大的，表示 max，队友听，mex，好呀）

离线没修改的区间 mex，记当前我们处理到了第 $i$ 个元素，记录一下元素值为 $key$，在 $i$ 之前、离 $i$ 最近的出现的位置 $value$。想求的是 $l_j$ 到 $i$ 之间，没有出现过的最小的元素值，考虑从小到大枚举这个元素值，一旦遇到一个元素值最近出现的位置比 $l_j$ 小，那就是它了。

所以用线段树维护一下元素值在相应区间中，最近出现的位置的最小值即可。查询的过程也就是看左子树是不是有符合条件、即区间内没有出现过的元素值，没有就走右子树。

===== J. Sockets =====

**题目大意**：

**题解**：

===== K. Toll Roads =====

**题目大意**：

**题解**：