题目链接
本人再次认为是一道不错的题目,可能是我菜。
判定可行解
首先假定我们已经得到了 (a) 和 (b) 这两个序列,我们如何判断是否是有解的。
从图论的角度去分解这个问题,我们设当前序列为 (c) 。
当 (c_i=c_j) 时,我们连一条 ((i,j)) 双向边,代表第 (i) 位和第 (j) 位的数字应是相同的。
很显然,这几条边把相同数字的点都连上了边,那么如果整张图中只有一个连通块时,说明都是一种数值。
那么该如何连边,在这道题中非常显然,对于回文串连边即可。
因为对于一个长度为 (Len) 的回文串,我们能够连 (⌊frac{Len}{2}⌋) 这样的边。
所以如果 (Len) 为奇数,就不能恰好连完所以的边,我们设奇数段的个数为 (p) 。
那么很显然,一共会连出来 (frac{n-p}{2}) 条边,因为要求只有一个连通块所以边数至少为 (n-1) ,可以得出 (pleq 2) 的结论。
到现在为止,我们已经判断了是否有可行解的情况,现在考虑构造方案。
(p = 0)
先从 (p=0) 也就是说 (a) 中没有奇数元素的情况进行构造。
我们发现 (a) 可以保持不动,最主要的是要把相邻组的数字和同一组不同对的数组搞成一样。
这里直接给出结论:
[B={A_1+1,A_2,A_3,cdots,A_{m-1},A_m-1}
]
注意,当 (A_m-1 =0) 的时候直接把最后一位省略即可。
(p=1) 和 (p=2)
其实我们只要构造出 (A) 那么 (B) 直接按照上述的情况构造即可。
当 (p=1) 时,我们可以把奇数的元素 (A_{odd}) 放到 (A) 的最后一个位置。
同样的,对于 (p=2) 的情况,我们把 (A_{odd}) 分别放到第一位和最后一位。
上述的思路仔细思索还是不难理解的。
具体细节可以看一下代码:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define Enter putchar('n')
#define quad putchar(' ')
const int N = 105;
int n, m, a[N], s, b[N];
signed main(void) {
std::cin >> n >> m;
for (int i = 1; i <= m; i++) std::cin >> a[i];
for (int i = 1; i <= m; i++) s += (a[i] & 1);
if (s > 2) {
std::cout << "Impossible" << std::endl;
return 0;
}
if (m == 1) {
std::cout << a[1] << std::endl;
if (a[1] == 1) {
std::cout << 1 << std::endl << 1;
return 0;
}
std::cout << 2 << std::endl;
std::cout << 1 << " " << a[1] - 1 << std::endl;
} else if (s == 0) {
for (int i = 1; i <= m; i ++) std::cout << a[i], quad; Enter;
a[1] ++; a[m] --;
if (a[m] == 0) m --;
std::cout << m << std::endl;
for (int i = 1; i <= m; i++) std::cout << a[i], quad;
Enter;
} else if (s == 1) {
std::stable_sort(a + 1, a + 1 + m, [](int p, int q) {return p % 2 < q % 2;});
for (int i = 1; i <= m; i++) std::cout << a[i], quad; Enter;
a[1] ++; a[m] --;
if (a[m] == 0) m --;
std::cout << m << std::endl;
for (int i = 1; i <= m; i++) std::cout << a[i], quad;
Enter;
} else {
int first = -1, last = -1;
for (int i = 1; i <= m; i++) {
if (a[i] % 2 == 0) continue;
if (first == -1) first = a[i];
else {last = a[i]; break;}
}
int tot = 1;
b[1] = first;
for (int i = 1; i <= m; i++)
if (a[i] % 2 == 0) b[++tot] = a[i];
b[++tot] = last;
for (int i = 1; i <= m; i++) std::cout << b[i], quad; Enter;
b[1] ++; b[m] --;
if (b[m] == 0) m --;
std::cout << m << std::endl;
for (int i = 1; i <= m; i++) std::cout << b[i], quad;
}
return 0;
}