A. Desorting
题目的核心操作就是选定一个位置 \(i\)，使得：
- 对于所有 \(j\le i\)，\(a_j\leftarrow a_j+1\)
- 对于所有 \(j>i\)，\(a_j\leftarrow a_j-1\)
这样一来，操作后 \(a_{i+1}-a_i\) 的值就会 \(-2\)
因为 \(a_{i+1}-a_i<0\) 时，也意味着 \(a_i>a_{i+1}\)，所以就达到了要求
那么题目就变成寻找一对相邻的数，使得这两者差最小，然后就可以 \(O(1)\) 求解了
B. Fibonaccharsis
根据题目的解释，一个“类斐波那契数列”\(f\) 保证：
- \(f_i=f_{i-1}+f_{i-2}\ (i\ge 3)\)
那就设 \(f_1=x,f_2=y\)，把 \(i\ge 3\) 的 \(f_i\) 展开一下（记原斐波那契数列为 \(fib\)）：
\[f_3=x+y\\ f_4=f_2+f_3=y+x+y=x+2y\\ f_5=f_3+f_4=x+y+x+2y=2x+3y\\ f_6=f_4+f_5=x+2y+2x+3y=3x+5y\\ f_7=f_5+f_6=2x+3y+3x+5y=5x+8y\\ \cdots\\ f_n=fib_{n-2}x+fib_{n-1}y \]然后枚举 \(x\) 求解即可
C. Natarsis' Set
假设这些数字按递增顺序排列在一条直线上
在某一天之前看看每个数字 \(x\)，如果当天它没有被删除，那么它占据了什么新的位置，它之前的位置对它有什么影响？
显然，如果 \(x\) 位于 \(a_i\) 和 \(a_{i+1}\) 之间，它将移动到 \(x-i\) 的新位置，因为在它之前的 \(i\) 个位置已被删除
按照这个规律反向模拟一下就可以求出答案
D. Imbalanced Arrays
首先 我们发现可以从 \((n,-n)\)、\((n-1,-n+1)\)、\(\cdots\)、\((1,-1)\) 每对中选出一个数字来解决问题
其次，我们可以知道 \(a_i>a_j\) 意味着 \(b_i>b_j\)
对于数组 \(b\) 中绝对值最大的数 \(b_i\)，我们可以知道 若 \(b_i<0\) 则 \(a_i=0\)，若 \(b_i>0\) 则 \(a_i=n\) ，而且对于任何 \(y\) 和 \(z\)，我们都不可能有 \(a_y=0\)，\(a_z=n\)，因为这意味着 \(b_y+b_z\) 既是正数又是负数。因此，检验能否确定数组 \(b\) 中绝对值最大的元素的必要条件和充分条件是（数组 \(a\) 中存在等于 \(0\) 的元素） 或者 （数组 \(a\) 中存在等于 \(n\) 的元素）
我们可以在一开始就对数组 \(a\) 进行排序，我们只需要检查前端和末端，看看我们的关键条件是否成立
E. Ina of the Mountain
首先有一个经典问题就是
每次可以选择一个区间让区间中所有数字加上 \(1\)，问至少操作多少次才能让序列 \(a\) 变为 \(b\)
这个问题的解法是构造原序列的差分序列，每次操作等价于任意指定差分序列中的两个位置，让前一个位置加 \(1\)，后一个位置减 \(1\)，目标是让差分序列相等
本题类似，只不过问题转变到了模意义下，每次操作选择一段减去 \(1\)，要求序列中每个数字都变成 \(0\)
我们计算出原序列的差分序列 \(b\)（模意义），此时差分序列中的所有数都是正数
对于每个位置我们可以让其取值 \(b_i\)（正数），或者 \(b_i-k\)（负数），我们要求最终的序列必须满足任意前缀和都不低于 \(0\)（因为在差分序列上操作时 \(-1\) 操作在更前的位置），最终的目标是要求取值 \(b_i\)（正数）的所有数之和最小
继续探究，我们发现每个数字 \(b_i\) 变成 \(b_i-k\) 后会让前缀和减去 \(k\)，所有当前缀和为 \(s\) 时，我们最多可以取其中 \(\lfloor\frac{s}{k}\rfloor\) 个数变为 \(b_i-k\)
考虑如下的反悔贪心，对于前 \(i\) 个位置，不妨设我们已经维护了当前选了哪些位置变为 \(b_i-k\)
目前到了第 \(i+1\) 个位置，如果 \(\lfloor\frac{s}{k}\rfloor\) 变大，那么我们可以直接选择当前的 \(b_i\) 变为 \(b_i-k\)
否则我们到之前已经选的数中看看没有小于当前的 \(b_i\) 的数，如果有就替换掉
不难看出选择的数越在后面越好，所以以上的操作一定能得到前 \(i+1\) 个位置的最优答案
可以证明该算法正确
F. Miriany and Matchstick
考虑 DP，令 \(f_{i,c,j}\) 表示，填了第二行的前 \(i\) 个位置，\(i\) 处的字符是 A / B，填有不同字符的相邻位置是否能有 \(j\) 对，转移时间复杂度 \(O(n^2)\) 或 \(O(\frac{n^2}{w})\)
打个表，发现 \(\forall i\in [1,n],c\in[0,1]\)，满足 \(f_{i,c,0},f_{i,c,1},\cdots\) 构成的 0/1 串中，所有 \(1\) 几乎构成一个连续段，中间缺至多一个位置（比如 000101110000101110），那么三元组 \((p,l,r) \) 即可表示一个状态，其中 \(p\) 表示缺的位置（特别的，若不缺则 \(p=−1\)），\([l,r]\) 表示最左 / 最右侧 \(1\) 的位置
转移需要分讨四种情况，时间复杂度线性
标签：887,题解,位置,差分,数组,序列,操作,Div,我们 From： https://www.cnblogs.com/cantorsort2919/p/17598881.html