C
这不是我们港城莞校赛的题吗。
令 C 填 A 或 B 中的任何一种并最小化最后剩下的数的个数。奇偶位反转，显然和原串双射所以不重不漏，删相邻不同转为删相邻相同，容易发现，只要两种数没有只剩一种就一定能操作，所以能操作的最大次数等于两张数中数量较少的数的个数。所以 C 只要能把两边补齐，就一定能删空，这是充要的，能补齐的条件是三角形不等式。
考虑计数，统计不合法的方案，枚举 A 和 B 中数量较多的元素的个数，显然应该在 \([\frac n 2+1,n]\) 中，剩下的位置怎么填都非法，于是直接乘上 \(2^k\) 即可。
D
考虑画出 alice 和 bob 移动过程的折线图，其中 \(x\) 轴是距离，\(y\) 轴是时间。假设我们已经确定了这个排列，那么 alice 可以追上 bob 当且仅当两条折线有交点。所以将 bob 的折线向下平移到一个最靠下的位置使两折线依然有交，设折线此时和 \(x\) 轴的交点为 \((p,0)\)，那么答案就是 \(\frac p n\)。
假设已经确定了 \(p\) 所在的木棍和这个木棍后面的木棍集合，那么我们考虑怎么摆放他们使得 \(p\) 最靠后。在追上前，我们应该多放 \(a_i<b_i\) 的木棍让 alice 快速前进，所以 \(a_i<b_i\) 的木棍总是应该放在 \(a_i\ge b_i\) 的木棍前面。由于不能继续往下平移，走完所有 \(a_i<b_i\) 的木棍后两人应该恰好相遇。
我们考虑一条路径 \(C\)：它从 bob 的出发点出发，沿着 bob 的折线一直走，直到第一次相遇，接着沿着 alice 的路径一直走直到走完全程。容易发现 \(p\) 所在的木棍后的每一条木棍，走完它会让 \(C\) 的 \(y\) 坐标抬升 \(\max(a_i,b_i)\)，我们希望 \(C\) 抬升地尽量快使 \(p\) 的位置尽量靠后，于是我们总是会选 \(\max(a_i,b_i)\) 最大的若干木棍拼在 \(p\) 所在的木棍后面。
枚举 \(p\) 所在的木棍并预处理后缀和即可二分算出答案。
E
考虑把 \(a\) 划分成两个序列 \(p,q\)，满足 \(\forall i,a_i=p_i+q_i\)，钦定 \(p\) 只用第一种操作消成 \(0\)，\(q\) 只用第二种操作消成 \(0\)，那么我们要付出的代价是满足 \(p_i>p_{i+1}\) 的下降位置 \(i\) 的个数加上满足 \(q_j<q_{j+1}\) 的上升位置 \(j\) 的个数。
考虑进行 dp，设 \(f_{i,j}\) 表示已经对前 \(i\) 个位置决策了如何划分，其中 \(q_i=j\) 的最小代价。有转移
考虑对这个式子进行优化。有一个观察是 \(f_{i,j}\le f_{i,j+1}\)，这是因为对于一个固定的 \(k\)，更小的 \(j\) 两个条件都更难满足了。还有一个观察是 \(f_{i,a_i}\le f_{i,0}+2\)，这是因为对于固定的 \(k\)，不同的 \(j\) 产生的贡献至多差 \(2\)。
于是我们可以维护每个 \(i\) 的三段等值区间，类似第一个观察，我们可以发现只会从每个等值区间的右端点转移，于是朴素二分出这三个区间的端点就可以做到 \(\mathrm O(n\log V)\)。
考虑优化到线性。设 \(p_1\) 为最大的 \(f_{i,j}=f_{i,0}\) 的 \(j\)，设 \(p_2\) 为最大的 \(f_{i,j}=f_{i,0}+1\) 的 \(j\)，设 \(D=f_{i,0}\)，进行一些分类讨论：
- 如果 \(a_i\ge a_{i-1}\)，那么 \(f_{i,j}\) 一定可以无代价地从 \(f_{i,j-1}\) 转移，于是 \(p_1\) 不变，\(p_2\) 只要不等于 \(a_{i-1}\) 就不变。否则考虑 \(f_{i,(a_{i-1},a_i]}\) 应如何取值，根据前面的观察，我们只需要考虑 \(f_{i-1,p_1}\) 的贡献，稍微推一下式子就可以知道 \(p_2\) 会变成 \(\max(a_i-a_{i-1}+p_1,p_2)\)。
- 否则 \(a_i<a_{i-1}\)，容易发现 \(p_1\) 会变成 \(a_i-a_{i-1}+p_1\)，同时 \(p_2\) 会变成 \(\max(p_1,a_i-a_{i-1}+p_2)\)，这种情况下 \(p_1\) 可能为负数，我们需要让 \(D\leftarrow D+1\)，并且更新一下指针。容易证明需要更新指针时 \(f\) 数组的等值连续段个数为 \(2\)。
F
考虑先进行操作 1 再往操作序列里面插入操作 2。
我们不妨设棋子 A 的坐标始终小于棋子 B 的坐标，将移动过程看成平面上的若干个点 \((x,y)\)，其中 \(x\le y\)。如果有一次操作使得原本 \(x<y\) 的局面变成了 \(x=y\) 的局面，那么我们一定无法分辨出使用了操作 1 还是操作 2，由于题目区分的不是操作序列而是移动点集，所以我们需要避免在这里算重。不妨钦定填入操作 1 的过程中，除了初始的点 \((0,0)\) 之外不存在 \(x=y\) 的点，这样不会对相对困难的插入操作 2 的过程带来过多限制。
不管你怎么执行操作 2，显然 B 的坐标是不会改变的。于是填入的操作 1 需要满足，恰好执行了 \(B\) 次增加棋子 B 的坐标的操作。不妨枚举 \(k\) 表示增加了 \(k\) 次 A 的坐标，那么我们要统计的，就是从 \((0,0)\) 开始，除了初始点以外不能碰到 \(y=x\) 这条直线，到达 \((k,B)\) 的游走方案数。这是经典反射容斥。
接着，我们考虑怎么插入操作 2。令 \(d_i\) 表示只考虑操作 1，做完第 \(i\) 步操作后，A 和 B 两点的距离。我们发现第 \(i\) 次操作 1 后面可以插入操作 2 当且仅当，不存在 \(j>i\) 满足 \(d_j<d_i\)。否则会产生无效操作。进一步地，我们发现存在 \(j>i\) 满足 \(d_j=d_i\) 的方案也需要被视为不合法，原因依然是无法区分操作 1 和操作 2。
我们惊奇地发现，由于最终的 \(d=B-k\)，初始的 \(d=0\)，且每次操作只会让 \(d\) 变动 \(\pm 1\)，于是所有的后缀严格最小值个数恰为 \(B-k+1\) 个，但是并不是所有位置都能直接插 2，需要满足 \(d_i\le A-k\) 才可以，否则 A 的总移动量就大于 \(A\) 了，不合法。所以总共的合法插入位置个数是 \(A-k+1\) 个。在这些位置后面填入若干操作 2 的方案数是隔板。于是对于一个确定的 \(k\)，可以 \(\mathrm O(1)\) 算出答案，枚举所有的 \(k\) 就可以线性求解。