题解 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,这样连就能解决问题了,因为这样会导致 1n 相连,n2 相连,2 又与 n-1 相连……in-i+1n-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_ib_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} 可知 lr 染色相同,故我们显然只在颜色相同的点之间连边,故黑格与白格间没有边,图也就不连通了。

所以怎么说呢?这种人类智慧思维题,我根本想不出来/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;
}