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\) 串起来。
线段树维护即可。
标签:AtCoder,DAG,奇数,Contest,构造,001,条边,考虑,回文 From: https://www.cnblogs.com/zlxFTH/p/18173520