题解：P4795 [BalticOI 2018] 基因工程

· · 题解

这是一篇乱搞题解。

题意

给定 n 个长度为 m 且仅包含 A、T、G 和 C 的字符串，其中有一个模式串，其它字符串与这个模式串恰好有 k 个位置不同，求模式串的编号。

思路

思考 1s 后发现没思路，考虑乱搞。

一种很暴力的做法是，我们每次随机一个字符串，钦定它是模式串，然后暴力匹配即可。

这种做法的时间复杂度最坏是 O\left(n^2m\right)，经过卡时后我最高获得了 82 分，还是很优秀的。

于是您发现了这种做法很有前途（大雾），考虑卡常优化。

注意到有个东西叫做 bitset，我们考虑用这个来维护字符串。

由于 bitset 很快，所以它可以把时间复杂度压到最坏 O\left(\frac{n^2m}{64}\right)，凭借您买彩票必中奖的运气，想必是能一发卡过的。当然一发没过多交几发就行了。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5000;
int n,m,k;
string s[N];
bool f[N];
inline int mapp(char x){
    if(x=='A') return 1;
    else if(x=='T') return 2;
    else if(x=='G') return 3;
    else return 4;
}
bitset<4100> b[4100][5];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;j<m;j++) b[i][mapp(s[i][j])].set(j); 
    }
    while((double)clock()/CLOCKS_PER_SEC<=1.90){ // 卡时大法好
        int p=rng()%n+1;
        while(f[p]) p=rng()%n+1;
        for(int i=1;i<=n;i++){
            if(i==p) continue;
            int sum=0;
            for(int j=1;j<=4;j++) sum+=(b[i][j]&b[p][j]).count();
            if(sum+k!=m){
                f[p]=1;
                break;
            }
        }
        if(!f[p]){
            cout<<p;
            return 0;
        }
    }
    int p=rng()%n+1;
    while(f[p]) p=rng()%n+1;
    cout<<p;
    return 0;
}