| rank | solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 19 | 6 | ! | O | . | O | O | O | O | . | ! | Ø |
A
UnSolved by Forsaken.
B
Solved by Henry.
在两棵字典树上贪心地往下跑，能跑 00 或者 11 就往下跑。
注意，最后的结果要排一下序，防止块间存在问题。
D
Solved by Forsaken.
绝对值函数将整个值域分成 n+1 段，分别解出答案即可。
E
Solved by Henry.
枚举每个位置，搜索排列。
F
Solved by XLor.
贴个 exkmp。
G
Solved by Henry.
f(n)=f(n−1)+f(n−3)，在讨论一下首尾的情况即可。
H
UnSolved by Forsaken.
J
UpSolved by XLor
首先，搞出每个数的限制范围区间，显然出现在第 i 次操作的数，右端点为 n+i−1，否则为 2n。再考虑左端点，对于每个数，最小值操作比其大的会有影响，最大值操作比其小的会有影响，单调栈维护，二分出限制的左端点。
然后，贪心，从左到右考虑每个位置，如果当前位置对于某个数必选，那么选上，如果有多个数必选，则无解，否则选出可选的中最小的。
贪心的做法字典序一定最小，因此正确性只需要证明每个位置能够放数字，考虑一组可能解的数组，其前 k−1 和当前算法的运行结果一致，可以证明在有限次交换调整操作后，可以使得第 k 位满足。