AtCoder Grand Contest 001

D. Arrays and Palindrome

如果两个字符要求相同就给它们连边，对于一个长度为 \(x\) 的回文串，\(x\) 是偶数会连 \(x/2\) 条边，奇数会连 \(x/2 - 0.5\) 条边。

\(a\) 和 \(b\) 两个序列总和为 \(2n\)，要让 \(n\) 个字符相同至少连 \(n - 1\) 条边，也就是奇数个数超过 \(2\) 时一定无解。

考虑如何构造，手玩应该会发现有一种左右横跳的构造，对于单个回文串，发现构造一个 \(x - 1/x + 1\) 的回文串就能把这个回文串串起来，\(+1/-1\) 可以用来拼接相邻两个回文串，这样能构造出 \(m = 2\) 的情况：

\(m > 2\) 可以考虑中间的串长度不变直接错位，这在偶数的情况下能达到同样的效果，但是奇数就不行了，所以直接把最多两个奇数放到序列的两端上。

E. BBQ Hard

去掉 \(i < j\) 的限制。

考虑格路计数，转换成求每对 \((i, j)\)，从 \((-a_i, -b_i)\) 到 \((a_j, b_j)\) 的方案数之和。

值域很小，\(O(V^2)\) 递推就行了。

F. Wide Swap

显然从值域入手好做，因为，交换操作变成相邻的了。（即在逆排列 \(q\) 上考虑）

然后考虑相对顺序 \(i < j\)，如果 \(|q_i - q_j| < K\)，那么 \(q_i\) 一定在 \(q_j\) 前面，相当于建立了一个 DAG 的限制关系。

在 \(q\) 上怎么贪呢，如果没有限制，我们首先希望 \(q_i = 1\) 挪到越前面越好，然后是 \(q_i = 2\)。那在 DAG 上拓扑，用优先队列维护就好了。

这个 DAG 只需要找到每个 \(q_i\) 最大的 \(j < i\) 满足 \(|q_i - q_j| < K\) 且 \(q_j > q_i\) 就好了，因为 \(q_j < q_i\) 本身就会先决策，\(< j\) 的会和 \(j\) 串起来。

线段树维护即可。