已改 ABCD，E 太难写了 /tuu
A
题意：给定 $a, b, c$ 三个数，操作一次可以对一个数 +1，问多少次操作后能变为一个等差数列。
考虑如果 $2b > a + c$，显然只能提升 $c$ 来达成，否则提升 $b$ 是更优秀的选择。处理一下边界即可。
B
题意：给定 $a, b, c$ 三个长度为 $n$ 序列，要求任意序列内重排吗，使得满足 $a_i < b_i < c_i$ 的 $i$ 尽量多。求最大值。$n\leq 10 ^ 5$。
贪心即可，取最小的 $b_i > a_i$，然后又取最小的 $c_i > b_i$，没有就直接退出。
时间复杂度 $O(n\log n)$。
C
题意：给定一个数，他是好的当且仅当十进制下所有数都是 1、2、3 中的一个。给定 $n$，问 $n$ 最少可以由多少个好的数加起来构成。$T(T\leq 1000)$ 组数据，$n\leq 10 ^ {18}$。
场上 yy 的，好像和题解做法不太像。
假设我们先不考虑进位问题，那么对于每一位来说，都有一个取数个数的范围，也就是 $[\lceil\dfrac x3\rceil, x]$。如果这些区间交不为空，那么就取其中的最小值。容易发现不进位合法时一定是最小的情况。
下面考虑一下进位的问题。注意到我们一旦要从上一位偷一个 1 过来，到这里变成了 10，这样的话，这个取数个数的范围至少都是 4 了，这样就可以和前面的有交了。
直接暴力递归计算即可，时间复杂度应该是 $O(\log ^ 2 n)$ 的，反正很快就是了。
1 | LL solve(LL n) |
D
题意：将一个序列 $a$ 拆成两个序列 $b, c$ 的和，$b$ 不减，$c$ 不增，问这 $2n$ 个数绝对值的最小值。$n\leq 2\times 10 ^ 5$。
首先我们考虑假设已经知道了 $b_1, c_1$，如何按序构造出后面的项。
如果 $a_i \geq a_{i - 1}$，则 $c_i$ 不变，$b_i$ 增加，否则 $b_i$ 不变，$c_i$ 减少。
容易发现这样构造一定是最优的，因为如果 $a_i\geq a_{i - 1}$，让 $b_i$ 增加，$c_i$ 减少，这样肯定不会使绝对值变小，所以不优。
那么我们现在发现 $b_1, c_1$ 确定的时候我们可以找到一个合法的解。如果我们把 $b_1$ 看作变量并把 $b_1 = 0$ 带入计算得到 $b, c$，那么这就是一个 $2n$ 个绝对值相加的函数，具体的，就是 $\sum_{i = 1} ^ n |x + b_i| + |-x + c_i|$。
赛时 sb 了，我用一个 std::map 维护斜率和截距的实时变化。其实直接找到中位数做一做就好了。这就放一个赛时代码。
1 | using LL = __int128_t; |