自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 22:03:42，当前版本为作者最后更新于2021-01-29 12:44:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P4795 基因工程

P4795 [BalticOI 2018]基因工程

我们知道有朴素的 $O(n^3)$ 的暴力，我又不会正解，于是我们来乱搞。

思路

既然复杂度不会优化，那就优化常数。

朴素字符串匹配是 $O(n)$ 的，于是我们用一个 $4\times 4100$ 的 $\texttt{bitset}$ 维护每个字符串，其中 $4$ 代表的是字符集大小，$4100$ 代表的是字符串长度，第 $i,j$ 个数为 $1$ 的意义是第 $j$ 位的字符为第 $i$ 种字符。

但是这样还是会 $\texttt{TLE 91pts/94pts}$。

于是我们考虑随机打乱字符串，使其期望运行次数减小。

我们使用 random_shuffle 随机打乱字符串顺序。

然后就过了...

时间复杂度 $O(\dfrac {n^3}{w})$。

如果你过不了，那么你需要一些评测机波动和玄学。

$Code$:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,k;
struct node{
	char a[4105];
	int id;
}a[4105];
bitset<4105>b[4110][5];
inline int change(char ch){
	switch(ch){
		 case 'A': return 1;
		 case 'T': return 2;
		 case 'G': return 3;
		 case 'C': return 4;
	}
}
inline void read(char *a){
	char ch=getchar();
	while(ch<'A'||ch>'Z') ch=getchar();
	int len=0;
	while(ch>='A'&&ch<='Z') a[++len]=ch,ch=getchar();
}
int main(){
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		read(a[i].a);
		a[i].id=i;
	}
	random_shuffle(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			b[i][change(a[i].a[j])].set(j);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j){
				int s=0;
				for(int p=1;p<=4;p++){
					s+=(b[i][p]&b[j][p]).count();
				}
				if(s+k!=m) goto nxt;
			}
		}
		printf("%d",a[i].id);
		return 0;
		nxt:;
	}
	return 0;
}

再见 $qwq$~