CF1615G

Rainbow_qwq · 2022-08-18 18:57:18 · 题解

考虑直接都填新的数，这样会把 0 段的端点浪费掉。

考虑奇数长度的全 0 段和偶数长度的全 0 段。设端点的颜色为 u,v。

• 奇数长度：可以匹配 u 或匹配 v，使得答案比直接填 +1.
• 偶数长度：只有同时匹配 u,v 才使得答案比直接填 +1.

可以建立一般图最大匹配的模型：奇数长度建虚点 t，连边 (u,t),(v,t)；偶数长度连边 (u,v)；跑一般图最大匹配。

但这样有大量虚点，复杂度爆炸。

我们考虑一下奇数长度先提前预处理好匹配。

建一张新图，对于奇数长度的连在图中边 (u,v)，考察图中的每个连通块，设点数、边数为 n,m：

接下来再处理偶数长度（同时匹配 u,v 则答案 +1）:

如果 u,v 在不同的两棵树中则可以匹配掉 u,v，然后以 u,v 当根把树里其他的点都匹配掉。

于是对每个树建一个点，把这两棵树的点连一条边，跑一般图最大匹配，此时点数最多 600 可以接受。

可以用并查集和 dfs 简单实现这个过程。

#include<bits/stdc++.h>
#define For(i,a,b) for( int i=(a);i<=(b);++i)
#define Rep(i,a,b) for( int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 300005
#define inf 0x3f3f3f3f

namespace wk{

int n;
vi e[maxn];
void adde(int u,int v){e[u].pb(v),e[v].pb(u);}
int q[maxn],hd,tl;
int col[maxn],bel[maxn],pre[maxn],fa[maxn];
inline int getf(int x){
    while(x^fa[x])x=fa[x]=fa[fa[x]];
    return x;
}

int tim,vis[maxn];
int lca(int x,int y){
    ++tim;
    x=getf(x),y=getf(y);
    while(vis[x]!=tim){
        vis[x]=tim,x=getf(pre[bel[x]]);
        if(y)swap(x,y);
    }
    return x;
}
void shrink(int x,int y,int p){
    while(getf(x)!=p){
        pre[x]=y,y=bel[x];
        fa[x]=fa[y]=p;
        if(col[y]==2) col[y]=1,q[++tl]=y;
        x=pre[y];
    }
}
void link(int u,int v){bel[u]=v,bel[v]=u;}
void pushr(int u){if(u)pushr(bel[pre[u]]),link(u,pre[u]);}
bool work(int u)
{
    For(i,1,n)pre[i]=col[i]=0,fa[i]=i;
    col[u]=1,q[hd=tl=1]=u; int p;
    while(hd<=tl){
        int u=q[hd++];
        for(auto v:e[u])
            if(col[v]==1)shrink(u,v,p=lca(u,v)),shrink(v,u,p);
            else if(col[v]==0){
                pre[v]=u,col[v]=2;
                if(!bel[v])return pushr(v),1;
                col[bel[v]]=1,q[++tl]=bel[v];
            }
    }
    return 0;
}
int run(){
    int res=0;
    For(i,1,n)res+=(!bel[i]&&work(i));
    return res;
}

}

int n,tot,a[maxn],vis[maxn];
pii t[maxn]; int len;

int fa[605],hav[605];
int getf(int x){
    while(x^fa[x])x=fa[x]=fa[fa[x]];
    return x;
}
int id[605][605];
vector<pii>e[605];

void make(int i,int nd){
    int l=t[i].fi,r=t[i].se; vis[nd]=1;
    if(nd==a[l-1])a[l]=nd;
    else a[r]=nd;
}
void dfs(int u){
    for(auto t:e[u]){
        int v=t.fi;
        if(!vis[v])make(t.se,v),dfs(v);
    }
}

bool use[maxn];
signed main()
{
    n=read();
    bool hav=0;
    For(i,1,n)a[i]=read(),hav|=(a[i]>0);
    if(!hav){
        For(i,1,n)cout<<((i-1)/2)+1<<' ';
        return 0;
    }
    For(i,2,n)if(a[i]==a[i-1])vis[a[i]]=1;
    For(i,1,n)
        if(!a[i]&&(i==1||a[i-1])){
            int l=i,r=i;
            while(r<n&&!a[r+1])++r;
            i=r;
            if(l==1){if((r-l+1)&1)a[r]=a[r+1],vis[a[r]]=1;continue;}
            if(r==n){if((r-l+1)&1)a[l]=a[l-1],vis[a[l]]=1;continue;}
            t[++len]=mkp(l,r);
        }
    For(i,1,600)fa[i]=i;
    For(i,1,len){
        int l=t[i].fi,r=t[i].se;
        int u=a[l-1],v=a[r+1];
        if((r-l+1)%2!=0){
            if(vis[u])make(i,v),dfs(v);
            else if(vis[v])make(i,u),dfs(u);
            else if(getf(u)==getf(v))make(i,u),dfs(u);
            else e[u].pb(mkp(v,i)),e[v].pb(mkp(u,i)),fa[getf(u)]=getf(v);//cout<<"merge "<<u<<" "<<v<<endl;
        }
    }
    For(i,1,len){
        int l=t[i].fi,r=t[i].se;
        int u=a[l-1],v=a[r+1];
//      cout<<"l,r,u,v "<<l<<" "<<r<<" "<<u<<" "<<v<<endl;
        if((r-l+1)%2==0){
            u=getf(u),v=getf(v);
//          cout<<"U,V "<<u<<" "<<v<<endl; 
            if(u!=v&&!vis[u]&&!vis[v]&&!id[u][v])id[u][v]=id[v][u]=i,wk::adde(u,v);
        }
    }
    wk::n=600,wk::run();
    For(u,1,600)
        if(wk::bel[u]){
        //  cout<<"bel "<<u<<" "<<wk::bel[u]<<endl;
            int v=wk::bel[u],tmp=id[u][v];
            wk::bel[u]=wk::bel[v]=0;
            int x=a[t[tmp].fi-1],y=a[t[tmp].se+1];
            if(getf(x)!=u)swap(x,y);
            make(tmp,x),make(tmp,y),dfs(x),dfs(y);
        }
    For(u,1,600)
        if(!vis[u])vis[u]=1,dfs(u);
    For(i,1,n)if(a[i])use[a[i]]=1;
    int now=1;
    For(i,1,n){
        if(!a[i]){
            while(use[now])++now;
            a[i]=now; if(!a[i+1])a[i+1]=now;
            ++now;
        }
        printf("%d ",a[i]);
    }
    return 0;
}