题解 AT1982【[AGC001D] Arrays and Palindrome】

· · 题解

安利个人 blog：https://www.cnblogs.com/ET2006/

Atcoder 题面传送门

洛谷题面传送门

又是道思维题，又是道把我搞自闭的题。

首先考虑对于固定的 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

#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;
}