Palin 题解

连续

由于取出来的数字序列 {b} 是回文的，所以当 a[p] = x 被取出时，序列 {a} 中的 \rm a[q] = a[p] = x 在何时取出其实已经确定了。依照题意，任意时刻，序列 {a} 一定是开头连续的一部分和结尾连续的一部分被取出，我们设当前序列 {a} 中区间 [1, l] \bigcup [r, 2 * n] 中的数字已经被取出。可以保证的是这两段区间内没有重复取出的数字。容易发现，当我们已经取出了 n 个数字时，[1, n] 的所有数字都被取了一遍，而最终的 {b} 序列以及操作串也已经确定了。每当一个数字 a[p] = x 在开头或是结尾被取出时，我们将 a[q] = a[p] = x 也取出。一个重要的性质是：任意时刻，所有取出的 a[q] 是连续的一段。

这个东西其实也很好理解。{b} 结尾的一段对应了序列 {a} 中间的一部分。考虑序列 {b} 的后 \rm n 个数一定是随着前 \rm n 个数被取出的，并且为了保证回文，这后 \rm n 个数一定是从后往前生成的。也就是说序列 {b} 前 \rm n 个数生成的连续性决定了他后 \rm n 个数生成的连续性，只不过是反序。

DP

我们设当前状态 (l,i,j,r) 表示 {a} 中区间 [1, l] \bigcup [i, j] \bigcup [r, 2*n] 被取出，考虑接下来我们能干什么。无外乎四种情况：

• 当 a[l+1]==a[i-1] 的时候，可以从开头取出 a[l+1] 这个元素，同时把 a[i-1] 取出；

• 当 a[l + 1] == a[j + 1] 的时候，可以从开头取出 a[l + 1] 这个元素，同时把 a[j + 1] 取出；

• 当 a[r-1]==a[i-1] 的时候，可以从结尾取出 a[r - 1] 这个元素，同时把 a[i-1] 取出；

• 当 a[r-1] == a[j + 1] 的时候，可以从结尾取出 a[r - 1] 这个元素，同时把 a[j + 1] 取出。

可以使用 BFS 进行转移。准备一个队列，在一开始找到 pos1 和 pos2 满足 a[1]=a[pos1],a[pos2]=a[2*n]，依照题意要么取开头要么取结尾。初始有两种状态，取开头的 a[1] 就是 (1,pos1,pos1,2*n+1) ，取结尾的 a[2*n] 就是 (0, pos2, pos2, 2*n)。接下来按照上述方式进行转移，只要队列不为空，就弹出旧状态，插入新状态。终止状态满足 l + 1 == i \And j + 1 == r。

由于已经取出 n 个数字的时候整个操作序列已经确定了，所以让操作序列的字典序最小等价于让取出前 n 个数字的操作序列最小，也即取出 [1,l] \bigcup [r, 2*n] 的操作序列而不用管 [i,j] 是怎么取的。所以我们总是优先地考虑取出 a[l + 1]。 那么，一旦我们找到一个终止状态，便可以保证是字典序最小的，结束转移，直接输出即可。如果搜空了队列都没有到达终止状态，那么无解。

以上是考场上的我两个小时瞪眼的结果。

DP 贪心

考虑上述 4 中转移最多只有两种是可行的，因为不可能出现 a[i-1] 同时和 a[l+1]、a[r - 1] 相等，或是 a[j + 1] 同时和 a[l+1]、a[r - 1] 相等。故 DP 的时间复杂度上限是 O(2^n)，相当于我两个小时写了一个爆搜。当时我对这个程序的认识是：“时间复杂度一定很难跑满，并且策略是正确的，可以找到解” ，也就没往下想。但是事实上这个题是线性的贪心，接下来证明在上述 4 种转移中只需要选择一种就能得到正确的操作序列。

当抉择分支出现时，也就是一种状态可以转移到两种新状态时，一共有如下两种情况：

• a[l + 1] == a[i - 1] \And a[j + 1] == a[r - 1]
• a[l + 1] == a[j + 1] \And a[i - 1] == a[r - 1]

这里我们以第一种情况为例进行讨论，第二种同理。我们只进行开头 a[l + 1] 的转移，而暂且不管 a[r - 1]，那么状态变为 (l + 1, i - 1, j, r)。接下来假如出现 a[l + 2] == a[i - 2] ，那么我们依旧进行开头的转移而不管，这样下去，直到开头不能取出，设此时的状态是 (l+k,i-k,j,r)。这个时候我们急不可耐地取出结尾，状态变为 (l+k,i-k,j+1,r-1)。考虑这个过程，我们的操作序列是 L...LR，是所有能得到状态 (l+k,i-k,j+1,r-1) 里面字典序最小的一个。

也就是说如果在一开始我们就进行结尾的转移得到 (l+1,i-1,j+1,r-1)，然后再进行后续的操作，最终的操作序列是 LRL...，而现在我们已经找到了一个更优秀的替代品 L...LR 同样也能够得到最终的状态，那么结尾的转移便是完全无用的了。贪心得证。当且仅当开头无法转移时，我们才进行结尾的转移。

这就是一个大贪心，时间复杂度 O(n)。（虽然但是，我考场上并没有想出来，而是拿剩下的 30min 写了一个 T2 的爆搜并最终取得了 0 分的好成绩。

实现起来也很简单，队列的部分不用变，一旦我们找到一个合法转移，continue 掉就好了，这样可以保证线性。

输出

接下来考虑如何输出操作序列。我是开了一个结构体：

struct Op{
    int l, r, i, j, tp1, tp2, pre;
}P[10000010];