现在的位置: 首页 > 综合 > 正文

【hihocoder】基因工程

2018年04月12日 ⁄ 综合 ⁄ 共 2215字 ⁄ 字号 评论关闭

描述<原题链接

小Hi和小Ho正在进行一项基因工程实验。他们要修改一段长度为N的DNA序列,使得这段DNA上最前面的K个碱基组成的序列与最后面的K个碱基组成的序列完全一致。  

例如对于序列"ATCGATAC"和K=2,可以通过将第二个碱基修改为"C"使得最前面2个碱基与最后面两个碱基都为"AC"。当然还存在其他修改方法,例如将最后一个碱基改为"T",或者直接将最前面两个和最后面两个碱基都修改为"GG"。

小Hi和小Ho希望知道在所有方法中,修改碱基最少的方法需要修改多少个碱基。

输入

第一行包含一个整数T(1 <= T <= 10),代表测试数据的数量。

每组测试数据包含2行,第一行是一个由"ATCG"4个大写字母组成的长度为N(1 <= N <= 1000)的字符串。第二行是一个整数K(1 <= K <= N)。

输出

对于每组数据输出最少需要修改的碱基数量。

样例输入
2  
ATCGATAC  
2  
ATACGTCT
6 

本题双线性扫描处理匹配问题。关键点在于处理前后两个串交集部分的匹配。以as和bs表示两个串。

可以看出

#include <string.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int calc(string as,string bs,int k){
    //bs[0~k]==as[n-k~n] 
    int n=as.length();
    if(k==n) return 0;
    int num=0;
    for(int i=0;i<n;i++){
        if(i<k){
            if(i>=n-k) break;///very important....
            int j=i;
            vector<char> ss;
            ss.push_back(as[i]);
            while(true){
                ss.push_back(bs[j]);
                if(j>=k) break;
                j+=(n-k);
            }
            // for test
            for(int s=0;s<ss.size();s++){
                cout<<ss[s]<<" ";
            }cout<<endl;

            sort(ss.begin(),ss.end());
            char lst=0;int cnt=0;int mcnt=0;
            for(int s=0;s<ss.size();s++){
                if(lst!=ss[s]) cnt=1,lst=ss[s];
                else cnt++;
                mcnt=max(mcnt,cnt);
            }
            mcnt=max(mcnt,cnt);
            num+=(ss.size()-mcnt);
        }
        else if(i<n-k){
            if(as[i]!=bs[i]) num++;
        }
        else break;
    }
    return num;
}
int main(){
    int cases;cin>>cases;
    for(int i=0;i<cases;i++){
        char buf[1002];
        cin>>buf;
        string temp=buf;
        int n;cin>>n;int len=strlen(buf);
        string as=temp.substr(0,n),bs=temp.substr(len-n,n);
        int k=(n-1)-(len-n)+1;
        //cout<<as<<endl<<bs<<endl<<"k:"<<k<<endl;
        if(k<0) k=0;
        cout<<calc(as,bs,k)<<endl;
    }
    return 0;
}

据说上面不能ac,没查哪里写错了。发一个自己ac的版本。

#include <string.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int calc(string as,string bs,int k){
    //bs[0~k]==as[n-k~n] 
    int n=as.length();
    if(k==n) return 0;
    int num=0;
    for(int i=0;i<n;i++){
        if(i<k){
            if(i>=n-k) break;
            int j=i;
            vector<char> ss;
            ss.push_back(as[i]);
            while(true){
                ss.push_back(bs[j]);
                if(j>=k) break;
                j+=(n-k);
            }

            sort(ss.begin(),ss.end());
            char lst=0;int cnt=0;int mcnt=0;
            for(int s=0;s<ss.size();s++){
                if(lst!=ss[s]) cnt=1,lst=ss[s];
                else cnt++;
                mcnt=max(mcnt,cnt);
            }
            mcnt=max(mcnt,cnt);
            num+=(ss.size()-mcnt);
        }
        else if(i<n-k){
            if(as[i]!=bs[i]) num++;
        }
        else break;
    }
    return num;
}
int main(){
    int cases;cin>>cases;
    for(int i=0;i<cases;i++){
        char buf[1002];
        cin>>buf;
        string temp=buf;
        int n;cin>>n;int len=strlen(buf);
        string as=temp.substr(0,n),bs=temp.substr(len-n,n);
        int k=(n-1)-(len-n)+1;
        if(k<0) k=0;
        cout<<calc(as,bs,k)<<endl;
    }
    return 0;
}

 

抱歉!评论已关闭.