显然我们有一个比较简单的构图
对于 s[1...n] 为回文串, 我们可以 1->n 连边, 2->n-1 连边以此类推 (这里的连边都是无向边)
显然如果 n 个点在同一个联通块中那么是合法的
首先我们先考虑无解情况
显然对于一张 n 个点的图, 如果边数 < n-1 那么这张图一定不连通
所以如果 a 和 b 加起来奇数值大于 2 了, 那么一定无解
所以我们需要通过构造一个 b 数组使得 a 构成的图, 同一个回文串的图连通并且和相邻的回文串连通
- #include<bits/stdc++.h>
- #define N 500005
- using namespace std;
- int n,m,tot,a[N];
- int main(){
- scanf("%d%d",&n,&m);
- for (int i=1;i<=m;i++) scanf("%d",&a[i]);
- for (int i=1;i<=m;i++) if (a[i]&1) tot++;
- if (tot>2) return puts("Impossible"),0;
- if (tot){
- bool flag=0;
- for (int i=1;i<m;i++){
- if (a[i]&1){
- if (flag) swap(a[i],a[m]);
- else flag=1,swap(a[i],a[1]);
- }
- }
- }
- if (m==1){
- if (a[1]==1){
- printf("1\n1\n1\n");
- return 0;
- }
- printf("%d\n",a[1]);printf("2\n");
- printf("1 %d\n",a[1]-1);
- return 0;
- }
- for (int i=1;i<=m;i++) printf("%d",a[i]);puts("");
- if (a[m]==1) printf("%d\n",m-1);else printf("%d\n",m);
- printf("%d\n",a[1]+1);
- for (int i=2;i<m;i++) printf("%d",a[i]);
- if (a[m]>1) printf("%d\n",a[m]-1);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2729221.html