题解：P11720 [清华集训 2014] 虫逢

· · 题解

1. 题意

有 2n 个 m 位 01 串，每个串有恰好 L 个位置为 1。保证存在一个串的完美匹配，使得每对匹配都有恰好 L2 个公共的 1，请找出这些匹配。

数据生成方法：先分别地均匀随机 n 对匹配的串，再随机打乱。

2. 分析

考虑一对匹配串，它们有 \displaystyle \frac{l}{2} 个公共的 1。我们考虑把 m 位划分 B=\displaystyle \frac{l}{2}-1 个集合，这样一定存在某个集合中有多个公共 1 。

因此我们对每个集合分别做，依次枚举每个串在集合中为 1 的位的二元组。这样有两个二元组相同，我们就对两个串进行暴力检查。

分析一下复杂度。首先二元组总个数是 O(\displaystyle \frac{nL^2}{B})=O(L^3) 的。其次一对非匹配串的期望检查次数是 O(\displaystyle \frac{1}{B})=O(\displaystyle \frac{1}{L}) 。你可以跑这个算法两遍达到 O(\displaystyle \frac{n^2}{L^2})=O(n) 次检查。但是只做一遍，再把某个串已经有匹配的情况剪枝掉就过了。

3. 实现

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a),_=(b);i<=_;++i)
#define per(i,a,b) for(int i=(a),_=(b);i>=_;--i)
#define nc() (i1==i2&&(i2=(i1=in)+fread(in,1,T,stdin),i1==i2)?-1:*i1++)
using namespace std;
const int T=1<<20,M=135,mod=34981;
char in[T],*i1=in,*i2=in;
int n,m,L,B,a[mod][M],p[mod],st[M],res[mod];
int rd(int x=0,char c=0){
    do c=nc();while(c<48||c>57);
    do x=10*x+(c&15),c=nc();while(c>=48&&c<=57);
    return x;
}
struct HT{
    int cnt,lnk[mod],nxt[mod*5],to[mod*5];
    int ins(int x,int p){
        for(int i=lnk[p];i;i=nxt[i])if(to[i]==x)return i;
        return nxt[++cnt]=lnk[p],to[cnt]=x,lnk[p]=cnt;
    }
    void init(){
        cnt=0,memset(lnk,0,sizeof(lnk));
    }
}P;
void chk(int u,int v){
    if(res[u]||res[v])return;
    int i=1,j=1,w=0;
    while(i<=L&&j<=L){
        if(a[u][i]==a[v][j])++i,++j,++w;
        else a[u][i]<a[v][j]?++i:++j;
    }
    if(w==L>>1)res[u]=v,res[v]=u;
}
int main(){
    n=rd(),m=rd(),L=rd();
    rep(i,1,n*2){
        rep(j,1,L){
            int x=0;
            rep(k,0,3)x=(x<<7)|nc();
            a[i][j]=P.ins(x,x%mod);
        }
        sort(a[i]+1,a[i]+L+1),p[i]=1;
    }
    B=(m-1)/(L/2-1)+1;
    rep(k,1,(m-1)/B+1){
        P.init();
        rep(i,1,n*2){
            st[0]=0;
            for(;p[i]<=L&&a[i][p[i]]<=k*B;p[i]++)st[++st[0]]=a[i][p[i]]-1-(k-1)*B;
            rep(u,1,st[0])rep(v,1,u-1)P.ins(i,(((st[u]-1)*st[u])>>1)+st[v]);
        }
        rep(i,0,mod-1){
            st[0]=0;
            for(int j=P.lnk[i];j;j=P.nxt[j])st[++st[0]]=P.to[j];
            rep(u,1,st[0])rep(v,1,u-1)chk(st[v],st[u]);
        }
    }
    rep(i,1,n*2)printf("%d\n",res[i]);
    return 0;
}