蓝桥杯2016年第七届真题-碱基

解题思路:

解法：题目意思要好好理解一下，就是求有多少种DNA序列组合，在每种组合中，每个DNA序列都包含了同一个k长连续碱基序列子串(同一DNA序列中子串位置不一样的几种不会只算做一种，具体看下面样例2的解释)。

比如样例1：这2种组合是(1,2)、(2,3)：1串的TC和2串的TC、2串的CG跟3串的CG。

再比如样例2：这7种组合是(1,2,3)、(1,2,4)、(1,3,4)、(1,2,3)、(1,2,4)、(2,3,4)、(2,3,4),具体解释一下这7种，至于这里面重复的组合，是因为k长相同子串在某个串里面的位置不一样：

(1,2,3)：1串的"AAA"，2串[0,3]位置的"AAA"，3串的"AAA";

(1,2,3)：1串的"AAA"，2串[1,4]位置的"AAA"，3串的"AAA";

(1,2,4)：1串的"AAA"，2串[0,3]位置的"AAA"，4串的"AAA";

(1,2,4)：1串的"AAA"，2串[1,4]位置的"AAA"，4串的"AAA";

(2,3,4)：2串[0,3]位置的"AAA"，3串的"AAA"，4串的"AAA";

(2,3,4)：2串[1,4]位置的"AAA"，3串的"AAA"，4串的"AAA";

(1,3,4)：1串的"AAA"，3串的"AAA"，4串的"AAA"。

做起来的话，n和m的范围都很小，暴搜就行了，先搜出m个DNA序列，然后取这m个中的第一个DNA序列遍历找k长的子串，看后面m-1个DNA序列是否都包含这个子串，进行统计即可。

————————————————

注意事项:

版权声明：本文为CSDN博主「daixinliangwyx」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/daixinliangwyx/article/details/90263146

参考代码:

import java.io.BufferedInputStream;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStream;

import java.io.InputStreamReader;

import java.io.PrintWriter;

import java.math.BigDecimal;

import java.math.BigInteger;

import java.util.*;

public class Main {

    public static InputReader in = new InputReader(new BufferedInputStream(System.in));

    public static PrintWriter out = new PrintWriter(System.out);

    public static int n, m, k;

    public static long ans, tmp, mod = 1000000007;

    public static String str;

    public static String[] s = new String[10];

    public static int[] a = new int[10];

    public static void main(String[] args) {

        n = in.nextInt();

        m = in.nextInt();

        k = in.nextInt();

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

            s[i] = in.nextLine();

        ans = 0;

        dfs(1, 1);

        out.println(ans%mod);

        out.flush();

        out.close();

    }

    static void dfs(int kk, int p) {

        if (kk > m) {

            int len = s[a[1]].length();

            for (int i = 0; i < len-k+1; i++) {

                str = s[a[1]].substring(i, i+k);

                tmp = 1;

                for (int j = 2; j <= m; j++) {

                    tmp = (tmp * getStrCount(s[a[j]], str)) % mod;

                    if (tmp == 0) break;//这些DNA序列里遇到有不包含str子序列的，后面的DNA序列就不需要继续查找了，直接break

                }

                ans = (ans + tmp) % mod;

            }

            return;

        }

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

            a[kk] = i;

            dfs(kk+1, i+1);

        }

    }

    static long getStrCount(String s1, String s2) {

        long sum = 0;

        String tmps = s1;

        int index = tmps.indexOf(s2);

        while (index != -1) {

            sum++;

            tmps = tmps.substring(index+1);

            index = tmps.indexOf(s2);

        }

        return sum;

    }

    static class InputReader {

        public BufferedReader reader;

        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {

            reader = new BufferedReader(new InputStreamReader(stream), 32768);

            tokenizer = null;

        }

        public String next() {

            while (tokenizer == null || !tokenizer.hasMoreTokens()) {

                try {

                    tokenizer = new StringTokenizer(reader.readLine());

                } catch (IOException e) {

                    throw new RuntimeException(e);

                }

            }

            return tokenizer.nextToken();

        }

        public String nextLine() {

            String str = null;

            try {

                str = reader.readLine();

            } catch (IOException e) {

                e.printStackTrace();

            }

            return str;

        }

        public int nextInt() {

            return Integer.parseInt(next());

        }

        public long nextLong() {

            return Long.parseLong(next());

        }

        public Double nextDouble() {

            return Double.parseDouble(next());

        }

        public BigInteger nextBigInteger() {

            return new BigInteger(next());

        }

        public BigDecimal nextBigDecimal() {

            return new BigDecimal(next());

        }

    }

}