CCF-CSP2021复赛题解(转载整理)2

背景
有需要看我前一篇题解的​​​​​​点这里
废话不多说，赶紧开始!
3.回文
//本题借鉴了一下别人的算法
令s1=L
找出与 a1​ 的唯一一个位置，记作p，则序列被划分为两段，a[2...p-1]和a[p+1...2n]。
可以将这两段分别看成两个栈：栈 T1​：a[2...p-1]的栈顶为22，栈底为p−1。
栈T2​：a[p+1...2n]的栈顶为2n，栈底为p+1。
则问题转化为每次可以取走这两个栈之一的栈顶，令最终得到的串是回文串。
自然，只有存在某个数x，既在栈顶，又在栈底才能取走。否则无解。可以分类讨论一下：如果数x在栈Ti​ 的栈顶和栈Ti​ 的栈底，可以先取走Ti​ 栈顶，当另一个栈取空后，再取空Ti​，这样的方案显然是合法的。如果数x在栈Ti​ 栈顶和栈 T3-i的栈底，可以先取走Ti​ 栈顶，当Ti​ 被取空后，再取空T3−i​，显然也是合法的。
这样就可以从两个栈中直接消除掉数x的影响，归纳构造方案。由于要求字典序最小，所以可以每次优先取T1​的栈顶。如果过程中找不到可以取的栈顶，则无解。

CCF-CSP2021复赛题解(转载整理)2最先出现在Python成神之路。