[CSP-S 2021] 回文

原题传送门：P7915 [CSP-S 2021] 回文 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

kk

根据题意，第一次从a序列中取数字，要么拿最左边的，要么拿最右边的。这里以先拿最左边的为例，反之亦然。

例如样例中的数据4 1 2 4 5 3 1 2 3 5，先取出左边的4，放入b序列的第一个位置也就是b1中。

这时候，因为最终期望的b序列是回文序列，而b1被放置了a1，也就是4，于是b序列的最后一个数字也是4。

题目云云：1,2,…,n 分别各出现恰好 2 次。所以有且仅有一个不同于a1（例子中是4）的am使得am=a1。那么，这个am就会被放到b2n（b序列的最后一个）。

由于am是最后一个被取到的，所以在取am之前必须依次将am左右两边的的数字从外向内依次取出。

易知，依次取出数字可以用栈。于是将原序列中am的左右两边分开（不包括已经被取出的a1）：栈x1 2和 栈y5 3 1 2 3 5。因为栈x在am左边，元素是从左往右拿，所以栈顶在最左侧；同理，栈y的栈顶在最右侧。

再回过来看a1。取出a1后，剩下可能取到的数字应在所有剩下数字中的开头与末尾（剩下数字指的是去除了a1和am后的序列），也就是a2与an（请先假定am不是a2也不是an）。倒过来思考，看向am。如果最后一个被取出的是am，那么倒数第二个被拿走的数字一定在am的相邻左边或右边，即a_m-1或a_m+1；也有可能我下面只取左边或只取右边，那么倒数第二个拿的就是a2或an。

而要组成回文，就要确保第二个拿的与倒数第二个拿的数字相同。再列出以下两个栈：

a2->a3->...->a_m-1 ； an->a_n-1->...a_m+1。

所以有以下几种情况：

• a2=a_m+1
• a2=a_m-1
• an=a_m+1
• an=a_m-1

当只存在一种情况时，把这两个相等的数字删除。显而易见，最终输出的答案应该分为正序和倒序的。对于从栈顶删除的，在答案正序的部分+L(从x栈删除)或R(从y栈删除)；对于从栈底删除的，在答案的倒序部分+ L(从x栈删除)或R(从y栈删除) 。这里不建议在操作的时候就将倒序部分转成顺序，而应该在最后，最终答案为正序+倒序的反转（也就是在操作的时候使倒序记录保持倒序，这样效率高）。

如果不存在上述四种情况之一，则表示无解；如有多种情况都同时满足，先选择位于x栈顶的数字，这样字典序最小。

最后，先对取a1进行讨论，若取a1的无解，再取an，同样操作。若还是无解，输出-1。