P2547 DNA变异

· · 题解

在专栏食用本文章更佳。（真的更佳！不骗你）

题目意思

给出若干个不重复的 DNA 序列，每个 DNA 均是由 A，C，T 和 G 四个字母组成的 8 位字符串。求变异一次可以得到序列中另一个 DNA 的组数。

DNA 变异的过程：在 8 位字符串中找出 4 个不相同的位置，第一个位置和第二个位置上的字符互换，第三个和第四个位置上的字符互换。比如说 DNA 序列 \texttt{ATCTACTG} 变异位置为 1，2，3 和 4，则变异后就是 \texttt{TATCACTG}。

过程

很明显，对于每一个 DNA 都需要模拟它每一种变异后的结果。用一个简单的循环可以计算出任意一个 8 位 DNA 有 210 种变异方法。从数学角度也可以计算出： C_8^4\times3=210。


for(int i=0;i<8;i++)
    for(int j=i+1;j<8;j++)
        for(int k=i+1;k<8;k++){
            if(k==j) continue;
            for(int l=k+1;l<8;l++){
                if(l==j) continue;
                printf("%d %d %d %d\n", i, j, k, l);
                cnt++;
            }
        }
cout << cnt;

对于每一次变异之后的新 DNA，我们需要知道这个新 DNA 是否存在于给出的 DNA 序列中。首先想到的是用 bool 数组记录是否存在，由此想到了用哈希。这里，我令 A 表示 0，G 表示 1，T 表示 2，C 表示 3。哈希函数：

int hash_(string h_){
    int id=0;
    for(int i=0;i<8;i++){
        id*=4;
        switch(h_[i]){
            case 'G': id+=1; break;
            case 'T': id+=2; break;
            case 'C': id+=3; break;
            default: break;
        }
    }
    return id;
}

这样，得到变异后的 DNA，如果这个 DNA 的哈希值在序列中，就说明找到了一对。注意：一个 DNA 可能有多种修改方法得到的是同一个 DNA，所以需要用 bool 数组去重一下。

整体过程：

注意两点：1.模拟 DNA 变异需要交换字符，模拟完一次变异之后要换回来；2.如果 DNA \alpha 变异之后得到 DNA \beta，则说明 DNA \beta 变异也可以得到 DNA \alpha，每一对都被计算了两次，输出答案时要除以 2。

然后就没啥难的了。个人感觉这个题目难度应该不到蓝题吧。。

#include "iostream"
#include "cstring"
using namespace std;
int t, num1, num2, cnt;
string input[8005];
bool vis[65536], book[65536];
int hash_(string h_){
    int id=0;
    for(int i=0;i<8;i++){
        id*=4;
        switch(h_[i]){
            case 'G': id+=1; break;
            case 'T': id+=2; break;
            case 'C': id+=3; break;
            default: break;
        }
    }
    return id;
}
int main(){
    cin >> t;
    for(int i=1;i<=t;i++){
        cin >> input[i];
        book[hash_(input[i])]=1; // 这个哈希值在序列中出现过
    }
    for(int c=1;c<=t;c++){
        memset(vis, false, sizeof(vis)); // 去重数组
        for(int i=0;i<8;i++)
            for(int j=i+1;j<8;j++)
                for(int k=i+1;k<8;k++){
                    if(k==j) continue;
                    for(int l=k+1;l<8;l++){
                        if(l==j) continue;
                        num1=hash_(input[c]);
                        swap(input[c][i], input[c][j]);
                        swap(input[c][k], input[c][l]);
                        num2=hash_(input[c]); // 新DNA的哈希值
                        if(book[num2] && !vis[num2] && num2!=num1) cnt++, vis[num2]=true;
                        //注意，除了判断重复以外，还需要判断 num2!=num1，如果变异得到的和原来一样，就不能算一对。
                        swap(input[c][i], input[c][j]);
                        swap(input[c][k], input[c][l]); // 换回来
                    }
                }
    }
    printf("%d", cnt/2);
}

如何获得最优解

这个题到这儿就完毕了，接下来的内容大家……随便看看吧。

当我向教练请教这一题的时候，教练说：

所以，我决定启动面向结果编程技术！

因为变异方法只有 210 种，所以我们可以预处理这 210 种变异的位置。

把上面模拟变异的四重循环稍微改一下，单独运行，让它输出变异 210 组位置。

#include "iostream"
using namespace std;
int cnt;
int main(){
    cout << "int swaps[][4]={";
    for(int i=0;i<8;i++)
        for(int j=i+1;j<8;j++)
            for(int k=i+1;k<8;k++){
                if(k==j) continue;
                for(int l=k+1;l<8;l++){
                    if(l==j) continue;
                    printf("{%d,%d,%d,%d},", i, j, k, l);
                }
            }
    printf("};");
}

输出： int swaps[][4]={{0,1,2,3},{0,1,2,4}...{4,7,5,6}};

对，就是打表

接下来，因为 8 位 DNA 只有 4^8=65536 种可能，每个 DNA 只有 210 种变异方法，所以可以把 65536 个 DNA 的 210 种变异都列举出来。

在这之前，有一点值得注意：稍微想一下，每个 DNA 的 210 种变异方法不可能都不一样，肯定有一些变异是重复的。所以我先循环一遍，统计 DNA 最多有多少个变异方法。代码不放了，运算结果是 175。这样，我们就只需要 int ans[65536][176] 的数组来记录答案了。下面的打表代码里面，我用 freopen 将输出写在 txt 里（因为担心剪贴板复制不了）。我还在开始打表和结束打表的时候各放了一个输出时间，用来看打表用时多久。

#include "iostream"
#include "windows.h"
using namespace std;
int swaps[][4]={{0,1,2,3},{0,1,2,4},{0,1,2,5},{0,1,2,6},{0,1,2,7},{0,1,3,4},{0,1,3,5},{0,1,3,6},{0,1,3,7},{0,1,4,5},{0,1
        ,4,6},{0,1,4,7},{0,1,5,6},{0,1,5,7},{0,1,6,7},{0,2,1,3},{0,2,1,4},{0,2,1,5},{0,2,1,6},{0,2,1,7},{0,2,3,4},{0,2,3,5},{0,2
                        ,3,6},{0,2,3,7},{0,2,4,5},{0,2,4,6},{0,2,4,7},{0,2,5,6},{0,2,5,7},{0,2,6,7},{0,3,1,2},{0,3,1,4},{0,3,1,5},{0,3,1,6},{0,3
                        ,1,7},{0,3,2,4},{0,3,2,5},{0,3,2,6},{0,3,2,7},{0,3,4,5},{0,3,4,6},{0,3,4,7},{0,3,5,6},{0,3,5,7},{0,3,6,7},{0,4,1,2},{0,4
                        ,1,3},{0,4,1,5},{0,4,1,6},{0,4,1,7},{0,4,2,3},{0,4,2,5},{0,4,2,6},{0,4,2,7},{0,4,3,5},{0,4,3,6},{0,4,3,7},{0,4,5,6},{0,4
                        ,5,7},{0,4,6,7},{0,5,1,2},{0,5,1,3},{0,5,1,4},{0,5,1,6},{0,5,1,7},{0,5,2,3},{0,5,2,4},{0,5,2,6},{0,5,2,7},{0,5,3,4},{0,5
                        ,3,6},{0,5,3,7},{0,5,4,6},{0,5,4,7},{0,5,6,7},{0,6,1,2},{0,6,1,3},{0,6,1,4},{0,6,1,5},{0,6,1,7},{0,6,2,3},{0,6,2,4},{0,6
                        ,2,5},{0,6,2,7},{0,6,3,4},{0,6,3,5},{0,6,3,7},{0,6,4,5},{0,6,4,7},{0,6,5,7},{0,7,1,2},{0,7,1,3},{0,7,1,4},{0,7,1,5},{0,7
                        ,1,6},{0,7,2,3},{0,7,2,4},{0,7,2,5},{0,7,2,6},{0,7,3,4},{0,7,3,5},{0,7,3,6},{0,7,4,5},{0,7,4,6},{0,7,5,6},{1,2,3,4},{1,2
                        ,3,5},{1,2,3,6},{1,2,3,7},{1,2,4,5},{1,2,4,6},{1,2,4,7},{1,2,5,6},{1,2,5,7},{1,2,6,7},{1,3,2,4},{1,3,2,5},{1,3,2,6},{1,3
                        ,2,7},{1,3,4,5},{1,3,4,6},{1,3,4,7},{1,3,5,6},{1,3,5,7},{1,3,6,7},{1,4,2,3},{1,4,2,5},{1,4,2,6},{1,4,2,7},{1,4,3,5},{1,4
                        ,3,6},{1,4,3,7},{1,4,5,6},{1,4,5,7},{1,4,6,7},{1,5,2,3},{1,5,2,4},{1,5,2,6},{1,5,2,7},{1,5,3,4},{1,5,3,6},{1,5,3,7},{1,5
                        ,4,6},{1,5,4,7},{1,5,6,7},{1,6,2,3},{1,6,2,4},{1,6,2,5},{1,6,2,7},{1,6,3,4},{1,6,3,5},{1,6,3,7},{1,6,4,5},{1,6,4,7},{1,6
                        ,5,7},{1,7,2,3},{1,7,2,4},{1,7,2,5},{1,7,2,6},{1,7,3,4},{1,7,3,5},{1,7,3,6},{1,7,4,5},{1,7,4,6},{1,7,5,6},{2,3,4,5},{2,3
                        ,4,6},{2,3,4,7},{2,3,5,6},{2,3,5,7},{2,3,6,7},{2,4,3,5},{2,4,3,6},{2,4,3,7},{2,4,5,6},{2,4,5,7},{2,4,6,7},{2,5,3,4},{2,5
                        ,3,6},{2,5,3,7},{2,5,4,6},{2,5,4,7},{2,5,6,7},{2,6,3,4},{2,6,3,5},{2,6,3,7},{2,6,4,5},{2,6,4,7},{2,6,5,7},{2,7,3,4},{2,7
                        ,3,5},{2,7,3,6},{2,7,4,5},{2,7,4,6},{2,7,5,6},{3,4,5,6},{3,4,5,7},{3,4,6,7},{3,5,4,6},{3,5,4,7},{3,5,6,7},{3,6,4,5},{3,6
                        ,4,7},{3,6,5,7},{3,7,4,5},{3,7,4,6},{3,7,5,6},{4,5,6,7},{4,6,5,7},{4,7,5,6}};
int ans[65536][176];
bool flag;
int hash_(string s){
    int id=0;
    for(int i=0;i<8;i++){
        id*=4;
        switch(s[i]){
            case 'G': id+=1; break;
            case 'T': id+=2; break;
            case 'C': id+=3; break;
            default: break;
        }
    }
    return id;
}
char next_(char c){
    if(c=='A') return 'G';
    else if(c=='G') return 'T';
    else if(c=='T') return 'C';
    else return 0;
}
int main(){
    freopen("result.txt", "w", stdout);
    int num1, num2;
    string a="########";

    SYSTEMTIME time;
    GetLocalTime(&time);
    printf("Start at %02d:%02d:%02d\n\n", time.wHour, time.wMinute, time.wSecond);

    for(int w1='A';w1!=0;w1=next_(w1)){
        a[0]=w1;
        for(int w2='A';w2!=0;w2=next_(w2)){
            a[1]=w2;
            for(int w3='A';w3!=0;w3=next_(w3)){
                a[2]=w3;
                for(int w4='A';w4!=0;w4=next_(w4)){
                    a[3]=w4;
                    for(int w5='A';w5!=0;w5=next_(w5)){
                        a[4]=w5;
                        for(int w6='A';w6!=0;w6=next_(w6)){
                            a[5]=w6;
                            for(int w7='A';w7!=0;w7=next_(w7)){
                                a[6]=w7;
                                for(int w8='A';w8!=0;w8=next_(w8)){
                                    a[7]=w8;
                                    printf("%s\n", a.c_str());
                                    for(int t=0;t<210;t++){
                                        num1=hash_(a);
                                        swap(a[swaps[t][0]], a[swaps[t][1]]);
                                        swap(a[swaps[t][2]], a[swaps[t][3]]);
                                        num2=hash_(a);
                                        flag=true;
                                        for(int i=1;i<=ans[num1][0];i++)
                                            if(ans[num1][i]==num2){
                                                flag=false;
                                                break;
                                            }
                                        if(flag) ans[num1][++ans[num1][0]]=num2;
                                        swap(a[swaps[t][0]], a[swaps[t][1]]);
                                        swap(a[swaps[t][2]], a[swaps[t][3]]);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    printf("int ans[65536][25]={");
    for(int i=0;i<65536;i++){
        printf("{");
        for(int j=0;j<=ans[i][0];j++)printf("%d,", ans[i][j]);
        printf("},");
    }

    GetLocalTime(&time);
    printf("\n\nEnd at %02d:%02d:%02d", time.wHour, time.wMinute, time.wSecond);
}

事实上，打到 txt 里的 ans 数组有五千万个字符，我用的两个编译器 Dev-C++ 和 CLion 都无法打开或编辑。

综上，这一题的打表打法最终失败了。