【清华集训2014】虫逢

一道随机化数据的好题。

题干

小强和阿米巴是好朋友。

阿米巴告诉小强，变形虫（又叫阿米巴虫）和绝大多数生物一样，也是有 DNA 的。并且，变形虫可以通过分裂的方式进行无性繁殖。

我们把一个变形虫的基因组抽象成一个大小为 LLL 的基因集合。每个基因都是一个 444 位长的字符串（字符包括大小写字母、数字、符号 “~!@#%^&()[]`:;"'<>,.?/|=-{}”)。现在，有 N个变形虫凑到了一起。由于他们是从天南海北过来的，我们可以认为，他们的基因组都是从一个大小为 个变形虫凑到了一起。由于他们是从天南海北过来的，我们可以认为，他们的基因组都是从一个大小为 个变形虫凑到了一起。由于他们是从天南海北过来的，我们可以认为，他们的基因组都是从一个大小为M的“变形虫基因库“中独立的随机的选取L个基因得到的。目前人类并不了解这个基因库里都有什么基因，但是我们知道它的大小是 的“变形虫基因库“中独立的随机的选取L个基因得到的。目前人类并不了解这个基因库里都有什么基因，但是我们知道它的大小是 的“变形虫基因库“中独立的随机的选取L个基因得到的。目前人类并不了解这个基因库里都有什么基因，但是我们知道它的大小是M$。

这时，环境突然发生巨变。这\(N\)个变形虫在外界的刺激下同时进行了一次分裂。每个变形虫分裂成了两个。分裂的过程中，原来的变形虫的基因组（基因的集合）被原样的复制成了两份，分别进入两个新的变形虫。两个新变形虫中的一只的基因组中有一半发生了突变，被替换为“变形虫基因库”中随机的其他的基因。如果两个变形虫是由原来的一个变形虫产生的，我们叫它们“同源”的。

给出 \(2N\) 个变形虫的基因组，请你找出每个变形虫同源的另一只虫是谁。
输入格式

第一行三个整数 \(N\)、\(M\)、\(L\)。

接下来一行 \(2NL×4\)个字符，依次表示每个集合中的元素。集合内的元素之间的顺序是无关紧要的。
输出格式

输出\(2N\)行，每行一个整数表示第\(i\)个变形虫（从\(1\)开始标号）同源的另一只变形虫是谁。

思路：

50pt暴力

非常容易想到一个朴素的做法。

我们对序列中的每一个基因片段都单独计算hash值，同时标记出这个基因属于哪一只虫子。
同时，我们用结构体去存储每一个基因的所属与hash值。
这样，我们就可以以hash值大小为关键字排序。排序后，基因会排列成一段一段的。
我们建立一个二维的\(fri[i][j]\)数组，表示第\(i\)和\(j\)只虫子间有多少相同的基因，即相似度。
这样，我们就可以对每一段中的每一个基因的所属\(i\),\(j\)只虫子间的数组提供贡献，最后\(O(n^2)\)的找出每一对相似度恰好为\(L\)的虫子。
这个算法的时间和空间复杂度均为\(O(n^2)\)，可以说暴力到极致了。

Coding:

#include<bits/stdc++.h>
#define N 7200
#define M N*2*80
#define base 131
#define ll long long
#define ull unsigned long long
#define f1(i,n,m) for(int i=n;i<=m;++i)
#define f2(i,n,m) for(int i=n;i>=m;--i)
using namespace std;
char s[M*4];
int n,m,l,tot;
int bel[M],fri[N][N],to[N];
ull hs[M];
int cnt[N];
struct node{
	ull hs;
	int bel;
}a[N*80];
inline ull get(char c[]){
    ull res=0;
	f1(i,1,4)res=res*base+(int)c[i];  
    return res;
}
bool cmp(node a,node b){
	return a.hs<b.hs;
}
signed main(){
	int pre;
	freopen("dna.in","r",stdin); 
	freopen("dna.out","w",stdout);
    scanf("%d%d%d",&n,&m,&l);
    scanf("%s",s+1);
    f1(i,1,2*n)f1(j,1,l){
    	a[++tot].hs=get(s+(i-1)*l*4+(j-1)*4);
    	a[tot].bel=i;
	}
	sort(a+1,a+1+tot,cmp);	
	f1(i,1,tot){
		if(a[i].hs==a[i-1].hs){
			f1(j,pre,i-1)fri[a[i].bel][a[j].bel]++;
		}
		else pre=i;
	}
	f1(i,1,2*n)f1(j,1,i-1)
		if(fri[i][j]+fri[j][i]>=(l/2))to[i]=j,to[j]=i;
	f1(i,1,2*n)printf("%d\n",to[i]);
    return 0;
}

100pt做法

这个做法的正确性是基于题目数据的随机性得到的