不会构造/kk

· · 题解

a. [AGC001D] Arrays and Palindrome（5）

  • 对两个数列 (a_1,a_2,\dots,a_n),(b_1,b_2,\dots,b_m) 称为相配的当且仅当：
    • 对任意满足「条件」的长度为 s 的序列 c 总有全部元素相等。
    • 条件：c 满足前 a_1 个元素回文，接下来 a_2 个元素回文，…，接下来 a_n 个元素回文。且前 b_1 个元素回文，接下来 b_2 个元素回文，…，接下来 b_m 个元素回文。
    • 给定一个打乱的 a，你可以任意排列 a，并且任意给出一组相配的 a,b。或者说明无解。

首先一个长度为 n 的回文可以提供 [\dfrac n2] 条相等信息。我们需要判断全部数相等至少需要 n-1 条相等信息，所以说最多只有两个奇数。

观察一种结构，比如当 n 为偶数时，c[1,n],c[2,n+1] 都是回文的情况下， 观察下图可以得到 c[1,n+1] 全部相等：

两个接口点可以把所有这种结构都串起来，比如：

我们根据这个得到启发：先把所有奇数放两边，我们对每个偶数 a_i，搞一个恰好比 a_i 后一格的回文这样子就可以让中部全部相等了。

对于两边的奇数处理是简单的，留给读者。

submission