AGC001D Arrays and Palindrome

题意：对于两个数组 ，满足 。

对于一个长度为 的字符串，若其满足下列条件 :

• 前 个，接下来 个，接下来 个……都是回文串。

• 前 个，接下来 个，接下来 个……都是回文串。

那么这个字符串的各个字符一定都相等。

现在已知 是 的一个排列，求一组符合要求的 ，或指出无解。

，，时限 。

---

构造题。

首先考虑如何判定一组 是否合法。

对于一组回文要求，将需要相等的两个位置连一条无向边。若连通整个串，则各个字符一定都相等，反之则不一定。

对于某个 ，连出的边数是 的。同时注意到总边数至少是 ，所以 中若有三个及以上的奇数，则必然无解。

显然， 内部的边是不会相连的，将整个图连通需要 边相互作用。

考虑使用两个回文串交叠能产生怎样的构造：

左图是 奇串+偶串，右图是 偶串+偶串。通过这种错开一位的构造，可以使内部完全连通。（从回文周期理论看，这是自然的）

那么，最终方案就不难想到了：将 中的至多两个奇数放到一边，然后逐步错位来构造 ，如图：

（红色部分是奇串）

需要特判 的情况。