题解 AT1982 【Arrays and Palindrome】

CYJian · 2019-12-16 19:53:57 · 题解

AGC001D

一道构造题。。

首先很容易发现，如果我们把回文的对应相等的关系当成连边，我们就相当于希望这个东西连成一个联通块。首先不难发现，我们每次连的边数是 \sum_{i=1}^{M} \left\lfloor \frac{a_i}{2} \right \rfloor 的。如果给出的 a_i 中存在三个及以上的奇数，那么就一定不可能了。因为每有两个奇数，连出来的边数就会减少 1。连成一个联通块至少要是一棵树才行。

那么怎么构造呢？

我们先从特殊的情况考虑：M=1 的时候，我们发现，只需要令 a_1=N ，b_1=1，b_2=N-1 就行了。

然后我们考虑这样构造：首先将所有奇数分别放在开头结尾，然后这样构成 a 数列；

再让开头 +1，结尾 -1，就能构造出来合法的序列了。

不难发现，这样构造，会让中间的边正好错开，前后两个的边也是错开的，边数恰为 n-1，正好构成一棵树。

代码很简单，就不贴了。