POJ训练计划3080_Blue Jeans(串处理/暴力)
训练 处理 计划 poj 暴力
2023-09-14 09:08:12 时间
Blue Jeans
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 11542 | Accepted: 4962 |
Description
The Genographic Project is a research partnership between IBM and The National Geographic Society that is analyzing DNA from hundreds of thousands of contributors to map how the Earth was populated.
As an IBM researcher, you have been tasked with writing a program that will find commonalities amongst given snippets of DNA that can be correlated with individual survey information to identify new genetic markers.
A DNA base sequence is noted by listing the nitrogen bases in the order in which they are found in the molecule. There are four bases: adenine (A), thymine (T), guanine (G), and cytosine (C). A 6-base DNA sequence could be represented as TAGACC.
Given a set of DNA base sequences, determine the longest series of bases that occurs in all of the sequences.
As an IBM researcher, you have been tasked with writing a program that will find commonalities amongst given snippets of DNA that can be correlated with individual survey information to identify new genetic markers.
A DNA base sequence is noted by listing the nitrogen bases in the order in which they are found in the molecule. There are four bases: adenine (A), thymine (T), guanine (G), and cytosine (C). A 6-base DNA sequence could be represented as TAGACC.
Given a set of DNA base sequences, determine the longest series of bases that occurs in all of the sequences.
Input
Input to this problem will begin with a line containing a single integer n indicating the number of datasets. Each dataset consists of the following components:
- A single positive integer m (2 <= m <= 10) indicating the number of base sequences in this dataset.
- m lines each containing a single base sequence consisting of 60 bases.
Output
For each dataset in the input, output the longest base subsequence common to all of the given base sequences. If the longest common subsequence is less than three bases in length, display the string "no significant commonalities" instead. If multiple subsequences
of the same longest length exist, output only the subsequence that comes first in alphabetical order.
Sample Input
3 2 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 3 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA 3 CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Sample Output
no significant commonalities AGATAC CATCATCAT
Source
解题报告
真心不想写这解题报告。。。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char str[12][100],ch[100],ans[100]; int main() { int t,i,j,k,n,maxl,f; cin>>t; while(t--) { memset(str,0,sizeof(str)); memset(ans,0,sizeof(ans)); cin>>n; maxl=0,f=0; for(i=0; i<n; i++) cin>>str[i]; for(i=0; i<58; i++) { for(j=3; j<=60-i; j++) { strncpy(ch,str[0]+i,j); ch[j]=0; f=0; for(k=1; k<n; k++) { if(strstr(str[k],ch)==NULL) { f=1; break; } } if(!f) { if(j>maxl) { maxl=j; strcpy(ans,ch); } else if(j==maxl) { if(strcmp(ch,ans)<0) strcpy(ans,ch); } } } } if(maxl) cout<<ans<<endl; else cout<<"no significant commonalities"<<endl; } return 0; }
相关文章
- Java实现 蓝桥杯VIP 算法训练 开心的金明
- Java实现蓝桥杯VIP 算法训练 找公倍数
- Java实现 蓝桥杯 算法训练 2的次幂表示
- Java实现 蓝桥杯 算法训练 Torry的困惑(基本型)
- paddle 31 安装paddledetection并训练自己的数据集(支持voc与coco数据集)
- 【henuacm2016级暑期训练-动态规划专题 B】Coloring Trees
- NLP:自然语言处理NLP的发展史(传统/预训练大模型)四个阶段/四大思想/PTM两代区别/各个算法诞生具体细节、基于不同基础架构衍生的一系列大模型(BERT系列等)之详细攻略
- NLP之PTM:自然语言处理领域—预训练大模型时代各种吊炸天算法概述(NNLM→Word2Vec→ELMO→Attention→Transformer→GPT/BERT系列)、关系梳理、模型对比之详细
- 加载预训练模型解密
- 学习AI之NLP后对预训练语言模型——心得体会总结
- 在分类中如何处理训练集中不平衡问题
- 天天快乐编程集训队2021暑假训练-0807-模拟题解
- gym强化学习入门demo——随机选取动作 其实有了这些动作和反馈值以后就可以用来训练DNN网络了
- 【数据挖掘】XGBoost面试题:与GBDT的区别?为什么使用泰勒二阶展开?为什么可以并行训练?为什么快?防止过拟合的方法?如何处理缺失值?
- DBNet实战:详解DBNet训练与测试(pytorch)
- cs231n-2022-assignment1#Q2:训练一个支持向量机(SVM)
- Pytorch模型训练实用教程学习笔记:二、模型的构建