题解 AT1982【[AGC001D] Arrays and Palindrome】

安利个人 blog：https://www.cnblogs.com/ET2006/ [Atcoder 题面传送门](https://atcoder.jp/contests/agc001/tasks/agc001_d) [洛谷题面传送门](https://www.luogu.com.cn/problem/AT1982) 又是道思维题，又是道把我搞自闭的题。 首先考虑对于固定的 $a_1,a_2,\dots,a_n;b_1,b_2,\dots,b_m$ 怎样判定是否合法，我们对于回文串对应的点之间连边，表示它们必须相等，这样可以形成一张图，如果该图连通那么证明这两个数组合法，反之不合法，正确性显然。 注意到对于每个 $a_i$ 会连出 $\lfloor\dfrac{a_i}{2}\rfloor$ 条边，换句话说，如果 $a_i$ 是偶数那么全部 $\dfrac{a_i}{2}$ 条边都能连，如果 $a_i$ 是奇数那么会出现一个孤立点，综上 $a$ 部分连出的边的个数为 $\dfrac{n-a\ \text{数组中奇数的个数}}{2}$，而 $b$ 数组不论你怎么排最多只能连出 $\lfloor\dfrac{n}{2}\rfloor$ 条边，故如果 $a$ 数组中奇数个数 $\geq 3$，那么最多也只能连出 $\dfrac{n-3}{2}+\dfrac{n-1}{2}=n-2<n-1$ 条边，无解。 接下来考虑怎样构造出符合要求的解，先从特殊的情况开始，如果 $m=1$，那么分两种情况：$n=1$ 那么显然 $m=1,b_1=1$ 就符合要求。如果 $n>1$，那么考虑一个“错位”的思想，分两组，一组长度为 $1$，另一组长度为 $n-1$，这样连就能解决问题了，因为这样会导致 $1$ 与 $n$ 相连，$n$ 与 $2$ 相连，$2$ 又与 $n-1$ 相连……$i$ 与 $n-i+1$ 和 $n-i$ 相连，最终 $1\sim n$ 就一定会被连成一条链了。 接下来考虑更一般的情况，考虑先重排 $a$ 数组，如果 $a$ 数组有奇数，就将奇数放在 $a$ 数组的两边（有一个就放在开头，有两个就一个放开头一个放结尾）。其次考虑这样构造 $b$ 数组，$b_1=a_1+1,b_i=a_i(i\in [2,n]),b_n=a_n-1$。这样做就对了。 为什么？其实也是用了“错位”的思想，借鉴 $n=2$ 的经验，构造 $b_1=a_1+1$ 显然可以使前 $a_1$ 个数连成一片，同时也能将第一块（$[1,a_1]$）与第二块（$[a_1+1,a_1+a_2]$）串在一起，以此类推就能将全部 $n$ 个数串在一起。还有一个问题，那就是为什么一定要把奇数放到开头或结尾，因为假设 $\exist i,a_i=b_i\equiv 1\pmod{2}$，那么 $a_i$ 与 $b_i$ 在字符串上对应的位置一定是一个两个长度为 $a_i$ 区间，并且左、右端点各相差 $1$，不妨设其为 $[l,r]$ 与 $[l+1,r+1]$，考虑对棋盘进行黑白染色，$l,l+2,l+4,\dots,l+2k,\dots$ 染黑色，$l+1,l+3,l+5,\dots,l+2k+1,\dots$ 染白色，由 $a_i\equiv 1\pmod{2}$ 可知 $l$ 与 $r$ 染色相同，故我们显然只在颜色相同的点之间连边，故黑格与白格间没有边，图也就不连通了。 所以怎么说呢？这种人类智慧思维题，我根本想不出来/kk，wtcl/wq ```cpp #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define fz(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) #define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++) #define fill0(a) memset(a,0,sizeof(a)) #define fill1(a) memset(a,-1,sizeof(a)) #define fillbig(a) memset(a,63,sizeof(a)) #define pb push_back #define ppb pop_back #define mp make_pair template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;} template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;} typedef pair<int,int> pii; typedef long long ll; namespace fastio{ #define FILE_SIZE 1<<23 char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf; inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;} inline void putc(char x){(*p3++=x);} template<typename T> void read(T &x){ x=0;char c=getchar();T neg=0; while(!isdigit(c)) neg|=!(c^'-'),c=getchar(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); if(neg) x=(~x)+1; } template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);} template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);} void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);} } int n,m,p1,p2,cnt[2],a[105]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d",&a[i]),cnt[a[i]&1]++; if(cnt[1]>=3){puts("Impossible");return 0;} if(m==1){ if(a[1]==1) printf("1\n1\n1\n"); else printf("%d\n2\n1 %d\n",a[1],a[1]-1); return 0; } sort(a+1,a+m+1,[](int x,int y){return (x&1)>(y&1);}); printf("%d ",a[1]);for(int i=3;i<=m;i++) printf("%d ",a[i]);printf("%d\n",a[2]); vector<int> ans;ans.pb(a[1]+1);for(int i=3;i<=m;i++) ans.pb(a[i]);if(a[2]!=1) ans.pb(a[2]-1); printf("%d\n",ans.size());ffe(it,ans) printf("%d ",*it);printf("\n"); return 0; } ```