2016年第七届蓝桥杯Java程序设计本科B组决赛碱基(编程大题)

现在给定所有生物的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，否则按无效代码处理。

解法：题目意思要好好理解一下，就是求有多少种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序列是否都包含这个子串，进行统计即可。

代码：

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

评测结果：