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

我们考虑一个字符串

s_i

与另外

n-1

个字符串均有

k

个字符不同，但一个一个字符串枚举比较的时间复杂度显然是

O(n^2m)

的。所以考虑更优的实现方法，我们发现

s_i

与其它字符串应该一共有

(n-1)k

个字符不同，我们只需要用桶记录每个位置

4

种字符的个数，即可计算

s_i

与其它字符串不同字符的总数，时间复杂度是

O(nm)

的，但显然会有多个字符串满足上述约束，所以我们需要多次计算来获得唯一解，显然对于正确字符串

s_i

，从原来

n

个字符串中任意取

x

个不是

s_i

的字符串，

s_i

依然满足与另外

x-1

个字符串均有

k

个字符不同，也就是与其它字符串应该一共有

(x-1)k

个字符不同。于是我们考虑每次筛选出所有满足与其它字符串一共有

(n-1)k

个字符不同的字符串，然后从桶中删去部分不可能成为答案的字符串对其的贡献，再不断地重复上述过程直到找到唯一解，时间复杂度是

O(\alpha nm)

的，为了保证答案正确与时间不超时，我们发现在

n

比较小时删去部分字符串会使计算次数少使其正确性无保证，所以在

n\le100

时我们跑

O(n^2m)

的算法，在

n<1800

时每次仅删去

1

到

2

个字符串，在

n\geq 1800

时删去

\frac{n}{50}

之类个数的字符串，这样既可以保证正确性，也可以保证

\alpha

的大小不大。

CPP

#include<bits/stdc++.h>
using namespace std;
string s[4205];
int n,m,k,cnt,book[4205],id,sum;
vector<string> q; 
struct node{
    int a,b,c,d;
}se[4205];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    cnt=sum=n;
    for(int i=0;i<n;i++) {cin>>s[i];for(int j=0;j<m;j++)if(s[i][j]=='A')se[j].a++;else if(s[i][j]=='T')se[j].b++;else if(s[i][j]=='G')se[j].c++;else se[j].d++;}
    if(n<=100){
        for(int i=0;i<n;i++){
            int ccc=0,flag=true;
            for(int j=0;j<n&&flag;j++){
                if(i==j)continue;
                ccc=0;
                for(int o=0;o<m;o++)if(s[i][o]!=s[j][o]) ccc++;
                if(ccc!=k) flag=false;
            }
            if(flag) {cout<<i+1;return 0;}    
        }
    }
    while(cnt!=1){
        int cou=0;
        for(int i=0;i<n;i++){
            if(book[i]) continue;
            int num=0;
            for(int j=0;j<m;j++){
                if(s[i][j]=='A') num+=se[j].b+se[j].c+se[j].d;
                else if(s[i][j]=='T') num+=se[j].a+se[j].c+se[j].d;
                else if(s[i][j]=='G') num+=se[j].b+se[j].a+se[j].d;
                else num+=se[j].b+se[j].c+se[j].a;
            }
            if(num!=(sum-1)*k) {book[i]=1;q.push_back(s[i]);cou++;}
        }
        cnt-=cou;
        if(cnt!=1){
            int k;
            if(n<1700) k=2;
            else if(n<1800) k=1;
            else k=n/100;
            for(int i=0;i<k&&id<q.size();i++){
                for(int j=0;j<m;j++){
                    if(q[id][j]=='A') se[j].a--;
                    else if(q[id][j]=='T') se[j].b--;
                    else if(q[id][j]=='G') se[j].c--;
                    else se[j].d--;
                }
                id++;
                sum--;
            }
        }
    }
    for(int i=0;i<n;i++)if(!book[i]){cout<<i+1;return 0;} 
    return 0;
}

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

文章操作

相关推荐

评论

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