热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

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

2016年第七届蓝桥杯Java程序设计本科B组决赛碱基(编程大题),Go语言社区,Golang程序员人脉社

2016年第七届蓝桥杯Java程序设计本科B组决赛个人题解汇总:

https://blog.csdn.net/daixinliangwyx/article/details/90169154

 

第五题

标题:碱基

交题测试地址:https://www.dotcpp.com/oj/problem1835.html

生物学家正在对n个物种进行研究。
其中第i个物种的DNA序列为s[i],其中的第j个碱基为s[i][j],碱基一定是A、T、G、C之一。
生物学家想找到这些生物中一部分生物的一些共性,他们现在关注那些至少在m个生物中出现的长度为k的连续碱基序列。准确的说,科学家关心的序列用2m元组(i1,p1,i2,p2....im,pm)表示,
满足:
1<=i1 且对于所有q(0<=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,否则按无效代码处理。


解法:题目意思要好好理解一下,就是求有多少种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

评测结果:


推荐阅读
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • 深入理解Java中的volatile、内存屏障与CPU指令
    本文详细探讨了Java中volatile关键字的作用机制,以及其与内存屏障和CPU指令之间的关系。通过具体示例和专业解析,帮助读者更好地理解多线程编程中的同步问题。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 资源推荐 | TensorFlow官方中文教程助力英语非母语者学习
    来源:机器之心。本文详细介绍了TensorFlow官方提供的中文版教程和指南,帮助开发者更好地理解和应用这一强大的开源机器学习平台。 ... [详细]
  • 本文探讨了如何像程序员一样思考,强调了将复杂问题分解为更小模块的重要性,并讨论了如何通过妥善管理和复用已有代码来提高编程效率。 ... [详细]
  • python的交互模式怎么输出名文汉字[python常见问题]
    在命令行模式下敲命令python,就看到类似如下的一堆文本输出,然后就进入到Python交互模式,它的提示符是>>>,此时我们可以使用print() ... [详细]
  • Java 中的 BigDecimal pow()方法,示例 ... [详细]
  • 本文总结了汇编语言中第五至第八章的关键知识点,涵盖间接寻址、指令格式、安全编程空间、逻辑运算指令及数据重复定义等内容。通过详细解析这些内容,帮助读者更好地理解和应用汇编语言的高级特性。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 深入理解Cookie与Session会话管理
    本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息,以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制,解释其原理及应用场景。 ... [详细]
  • 前言--页数多了以后需要指定到某一页(只做了功能,样式没有细调)html ... [详细]
  • 深入理解C++中的KMP算法:高效字符串匹配的利器
    本文详细介绍C++中实现KMP算法的方法,探讨其在字符串匹配问题上的优势。通过对比暴力匹配(BF)算法,展示KMP算法如何利用前缀表优化匹配过程,显著提升效率。 ... [详细]
  • 在Linux系统中配置并启动ActiveMQ
    本文详细介绍了如何在Linux环境中安装和配置ActiveMQ,包括端口开放及防火墙设置。通过本文,您可以掌握完整的ActiveMQ部署流程,确保其在网络环境中正常运行。 ... [详细]
author-avatar
黎世江
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有