P9924 题解

· · 题解

Problem Link

题目大意

给定左右各 n 个点，m 条边二分图，给每个点构造长度为 n+1 的字符串（字符集 \texttt{A,B,C}），使得：

  • 两个字符串之间存在至少一位相等当且仅当对应的两个节点属于二分图同一侧，或者有边相连。
  • 字符串两两不同。

数据范围：n\le 1000,m\le n^2。

思路分析

一个朴素的做法是对左部点 1\sim n，给第 i 个串第 i 位填 \texttt C，其他填 \texttt A。

对于每个右部点，如果其和左部第 i 个点有边，填 \texttt{C}，否则填 \texttt B。

第 0 位左部点填 \texttt A，右部点填 \texttt B ，这样一个长度为 n+1 的串就能得到答案。

但此时我们无法保证每个右部点字符串两两不同，我们可以额外用 \lceil\log_2 n\rceil 位对第 i 个右部点表示 i 的二进制表示（用 \texttt{B,C} 代替 0,1），且左部点这些位填 \texttt A。

这样的的串长是 n+1+\lceil\log_2n\rceil 的，无法通过。

考虑什么样的右部点会得到相同的字符串，当且仅当他们的邻域相同，把这些点称为“等价类”。

注意到只有同一个等价类中的点才需要区分，因此我们可以直接传递其在等价类中排名的二进制表示，而不是 i 的二进制表示。

那么假设右部点最大的等价类大小是 R_s，那么我们只要 n+1+\lceil\log_2 R_s\rceil 个位，但这不够，需要继续优化。

考虑把左部点的等价类也划分出来，容易发现一个等价类可以共用一个位置填 \texttt C，但我们要对相同的。

那么设左、右部点的等价类数量是 L_c,R_c，等价类大小最大为 L_s,R_s。

那么花费位数为 L_c+\lceil \log_2L_s\rceil+\lceil\log_2 R_s\rceil，在 R_c<L_c 的时候可以交换左右部点得到更优的次数。

综上我们得到的花费位数为 \min(L_c,R_c)+\lceil \log_2L_s\rceil+\lceil\log_2 R_s\rceil。

分析一下这个东西的量级，注意到 L_s\le n-L_C+1\le n-\min(L_c,R_c)+1。

因此设 x=n-\min(L_c,R_c)+1，那么花费位数不超过 n-x+1+2\lceil \log_2x\rceil。

当 x\ge 2\lceil\log_2x\rceil 时花费位数 \le n+1。

我们只要考虑 x<2\lceil\log_2x\rceil 的情况，发现此时一定有 x=3/x=5。

不妨设 x=3，那么此时左右部点都是 n-3 个大小为 1 的等价类和一个大小为 3 的等价类。

考虑左部大小为 3 的等价类 \{x,y,z\}，我们需要 1 个位传递其连边信息，并且需要 2 个位区分标号。

如果我们对每个点分别传递连边信息，那么不需要区分标号，但是要 3 个位传递连边。

结合一下两种做法，第一位传递 x,y 的连边信息，第二位传递 y,z 的连边信息，此时两次传递即可令所有字符串不同。

对 x=5 的情况类似，对于五元等价类 \{a,b,c,d,e\}，第一位传递 a,b,c，第二位传递 c,d,e，第三位传递 b,d 即可。

综上，我们得到了串长 \le n+1 时完整的构造方案。

时间复杂度 \mathcal O(n^2+m)。

代码呈现

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=2005;
int n,m,lim,id[MAXN];
vector <int> G[MAXN],lq[MAXN],rq[MAXN];
string s[MAXN];
mt19937_64 rnd(time(0));
ull hs[MAXN],hv[MAXN];
bool vis[MAXN];
int lg(int x) { return __lg(x)+!!(x&(x-1)); }
void solve() {
    for(int i=0;i<2*n;++i) {
        G[i].clear(),s[i].clear();
        lq[i].clear(),rq[i].clear();
        vis[i]=false,hs[i]=0,id[i]=-1;
    }
    for(int i=1,u,v;i<=m;++i) {
        cin>>u>>v,--u,--v;
        G[u].push_back(v),hs[u]^=hv[v];
        G[v].push_back(u),hs[v]^=hv[u];
    }
    cout<<lim<<"\n";
    for(int i=0;i<2*n;++i) s[i]=string(lim,(i<n?'A':'B'));
    int lc=0,rc=0,ls=0,rs=0;
    for(int i=0;i<n;++i) if(id[i]<0) {
        for(int j=i;j<n;++j) if(hs[i]==hs[j]) {
            id[j]=lc,lq[lc].push_back(j);
        }
        ls=max(ls,(int)lq[lc++].size());
    }
    for(int i=n;i<2*n;++i) if(id[i]<0) {
        for(int j=i;j<2*n;++j) if(hs[i]==hs[j]) {
            id[j]=rc,rq[rc].push_back(j);
        }
        rs=max(rs,(int)rq[rc++].size());
    }
    int len=min(lc,rc)+lg(ls)+lg(rs);
    if(len>lim) {
        assert(ls==rs&&lc==n-ls+1&&rc==n-rs+1&&(ls==3||ls==5));
        int k=0,x=lg(ls),y=lg(rs);
        for(int i=0;i<lc;++i) if(lq[i].size()>1) k=i;
        if(ls==3) {
            //ls=rs=3,lc=rc=n-2
            for(int i=0;i<n;++i) if(id[i]!=k) s[i][id[i]]='C';
            int a=lq[k][0],b=lq[k][1],c=lq[k][2];
            s[a][k]=s[b][k]=s[b][lc]=s[c][lc]='C';
            for(int i=n;i<2*n;++i) for(int j:G[i]) {
                s[i][id[j]]='C';
                if(id[j]==k) s[i][lc]='C';
            }
        } else {
            //ls=rs=5,lc=rc=n-4
            for(int i=0;i<n;++i) if(id[i]!=k) s[i][id[i]]='C';
            int a=lq[k][0],b=lq[k][1],c=lq[k][2],d=lq[k][3],e=lq[k][4];
            s[a][k]=s[b][k]=s[c][k]='C';
            s[c][lc]=s[d][lc]=s[e][lc]='C';
            s[b][lc+1]=s[d][lc+1]='C';
            for(int i=n;i<2*n;++i) for(int j:G[i]) {
                s[i][id[j]]='C';
                if(id[j]==k) s[i][lc]=s[i][lc+1]='C';
            }
        }
        for(int o=0;o<rc;++o) for(int i=0;i<(int)rq[o].size();++i) {
            for(int j=0;j<y;++j) {
                s[rq[o][i]][j+lc+x-1]="BC"[i>>j&1];
            }
        }
    } else if(lc<rc) {
        for(int i=0;i<n;++i) s[i][id[i]]='C';
        for(int i=n;i<2*n;++i) {
            for(int j:G[i]) s[i][id[j]]='C';
        }
        int x=lg(ls),y=lg(rs);
        for(int o=0;o<lc;++o) for(int i=0;i<(int)lq[o].size();++i) {
            for(int j=0;j<x;++j) {
                s[lq[o][i]][j+lc]="AC"[i>>j&1];
            }
        }
        for(int o=0;o<rc;++o) for(int i=0;i<(int)rq[o].size();++i) {
            for(int j=0;j<y;++j) {
                s[rq[o][i]][j+lc+x]="BC"[i>>j&1];
            }
        }
    } else {
        for(int i=n;i<2*n;++i) s[i][id[i]]='C';
        for(int i=0;i<n;++i) {
            for(int j:G[i]) s[i][id[j]]='C';
        }
        int x=lg(ls),y=lg(rs);
        for(int o=0;o<lc;++o) for(int i=0;i<(int)lq[o].size();++i) {
            for(int j=0;j<x;++j) {
                s[lq[o][i]][j+rc]="AC"[i>>j&1];
            }
        }
        for(int o=0;o<rc;++o) for(int i=0;i<(int)rq[o].size();++i) {
            for(int j=0;j<y;++j) {
                s[rq[o][i]][j+rc+x]="BC"[i>>j&1];
            }
        }
    }
    for(int i=0;i<2*n;++i) cout<<s[i]<<"\n";
}
signed main() {
    for(int i=0;i<MAXN;++i) hv[i]=rnd();
    ios::sync_with_stdio(false);
    while(cin>>n>>m>>lim) solve();
    return 0;
}