[AGC001D] Arrays and Palindrome 题解
一道比较神秘的构造题。
思路
考虑如何通过回文串的性质将所有字符连接起来。
容易发现本题需要使用通过回文串类似连边的方式将所有字符变为一整个连通块。
考虑三种情况。
-
偶数连偶数
前面的偶数将最后一个字符与后面的偶数前 $len-1$ 个字符组成一个回文串。
-
偶数连奇数
前面的偶数将最后一个字符与后面的奇数的所有字符组成一个回文串，至于奇数在前的情况是一样的。
-
奇数连奇数
用连偶数的方式即可。
讨论这三种情况后，容易发现一个序列中有且仅能有不超过 $2$ 个奇数。
并且需要把他们放在一头一尾。
接着就比较好构造了。
Code
AC 记录。