java实现第七届蓝桥杯碱基

碱基

题目描述

生物学家正在对n个物种进行研究。

其中第i个物种的DNA序列为s[i]，其中的第j个碱基为s[i][j],碱基一定是A、T、G、C之一。

生物学家想找到这些生物中一部分生物的一些共性，他们现在关注那些至少在m个生物中出现的长度为k的连续碱基序列。准确的说，科学家关心的序列用2m元组(i1,p1,i2,p2…im,pm)表示，

满足:

1<=i1<i2<…<im<=n;

且对于所有q(0<=q<k), s[i1][p1+q]=s[i2][p2+q]=…=s[im][pm+q]。

现在给定所有生物的DNA序列，请告诉科学家有多少的2m元组是需要关注的。如果两个2m元组有任何一个位置不同，则认为是不同的元组。

【输入格式】

输入的第一行包含三个整数n、m、k，两个整数之间用一个空格分隔，意义如题目所述。

接下来n行，每行一个字符串表示一种生物的DNA序列。

DNA序列从1至n编号，每个序列中的碱基从1开始依次编号，不同的生物的DNA序列长度可能不同。

【输出格式】

输出一个整数，表示关注的元组个数。

答案可能很大，你需要输出答案除以1000000007的余数。

【样例输入】

3 2 2

ATC

TCG

ACG

【样例输出】

2

再例如：

【样例输入】

4 3 3

AAA

AAAA

AAA

AAA

【样例输出】

7

【数据规模与约定】

对于20%的数据，k<=5,所有字符串总长L满足L <=100

对于30%的数据，L<=10000

对于60%的数据，L<=30000

对于100%的数据，n<=5,m<=5,1<=k<=L<=100000

保证所有DNA序列不为空且只会包含’A’ ’G’ ’C’ ’T’四种字母

资源约定：

峰值内存消耗 < 256M

CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。

注意：主类的名字必须是：Main，否则按无效代码处理。

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Scanner;

public class Main {

    public static int n, m, k;

    public static String[] S;

    public static String[] num;

    public static int[] start;

    public static long MOD = 1000000007;

    public static long count = 0;

    public static HashSet<String> result = new HashSet<String>();

    public void dfs(int step, int sum) {

        if(step == n || sum >= m) {

            if(sum >= m) {

                ArrayList<String> set = new ArrayList<String>();

                StringBuffer[] s = new StringBuffer[sum];

                for(int i = 0;i < sum;i++)

                    s[i] = new StringBuffer("");

                for(int i = 0;i < n;i++) {

                    if(!num[i].equals("-")) {

                        if(!set.contains(num[i])) {

                            set.add(num[i]);

                            s[set.size() - 1].append(i);

                            s[set.size() - 1].append(start[i]);

                        } else {

                            int j = set.indexOf(num[i]);

                            s[j].append(i);

                            s[j].append(start[i]);

                        }

                    }

                }

                if(set.size() == sum - m + 1) {

                    for(int i = 0;i < sum;i++) {

                        if(s[i].toString().length() == k * 2) {

                            if(!result.contains(s[i].toString()))

                                count = (count + 1) % MOD;

                            result.add(s[i].toString());

                            break;

                        }

                    }

                }

            }

            return;

        } else {

            for(int i = 0;i < S[step].length();i++) {

                if(i + k <= S[step].length()) {

                    num[step] = S[step].substring(i, i + k);

                    start[step] = i;

                    dfs(step + 1, sum + 1);

                    num[step] = "-";

                }

                dfs(step + 1, sum);

            }

        }

    }

    public static void main(String[] args) {

        Main test = new Main();

        Scanner in = new Scanner(System.in);

        n = in.nextInt();

        m = in.nextInt();

        k = in.nextInt();

        S = new String[n];

        for(int i = 0;i < n;i++)

            S[i] = in.next();

        num = new String[n + 1];

        start = new int[n + 1];

        for(int i = 0;i <= n;i++)

            num[i] = "-";

        test.dfs(0, 0);

        System.out.println(count);

    }

}

巴特西

java实现第七届蓝桥杯碱基

最新文章

热门文章