自动搬运

查看原文

来自洛谷，原作者为

	Hate_and_Love 爱还是恨，我自己也不知道

搬运于2025-08-24 23:09:43，当前版本为作者最后更新于2025-05-17 11:29:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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