题解 P4795【基因工程】
cyffff
·
·
题解
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})。
如果你过不了，那么你需要一些评测机波动和玄学。
```cpp
#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$~