点击打开链接uva 1368
思路:暴力
分析:
1 给定m个长度均为n的DNA序列,求一个DNA使其所有的序列的
Hamming distances最小,如果有多个解输出字典序最小的序列
2 m最大为50,n最大为1000,很明显的暴力题目,没什么解题的方法就是暴力
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100;
const int maxn = 1010;
const char ch[4] = {'A' , 'C' , 'G' , 'T'};
char str[N][maxn];
//得到下标
int getIndex(char c){
for(int i = 0 ; i < 4 ; i++)
if(c == ch[i])
return i;
}
//得到最大的值的下标
int getMax(int *num){
int pos = 0;
for(int i = 1 ; i < 4 ; i++)
if(num[i] > num[pos])
pos = i;
return pos;
}
void solve(int m , int n){
int num[4];
int ans = 0;
char ansStr[maxn];
memset(ansStr , '\0' , sizeof(ansStr));
for(int i = 0 ; i < n ; i++){
memset(num , 0 , sizeof(num));
for(int j = 0 ; j < m ; j++)
num[getIndex(str[j][i])]++;
int maxIndex = getMax(num);
ansStr[i] = ch[maxIndex];
ans += m-(num[maxIndex]);
}
printf("%s\n%d\n" , ansStr , ans);
}
int main(){
int Case , m , n;
scanf("%d" , &Case);
while(Case--){
scanf("%d%d" , &m , &n);
for(int i = 0 ; i < m ; i++)
scanf("%s" , str[i]);
solve(m , n);
}
return 0;
}
分享到:
相关推荐
consensus bridging theory and practice
This code contains the simulation of consensus of balanced graph topology.
标准的一致性算法,该算法能够使设置的一致性变量收敛于同一值。同时附上常用的30个函数,便于理解。
Localizing Parts of Faces Using a Consensus of Exemplars
CSA_Consensus_Assessments_Initiative_Questionnaire.pdfCSA_Consensus_Assessments_Initiative_Questionnaire.pdfCSA_Consensus_Assessments_Initiative_Questionnaire.pdfCSA_Consensus_Assessments_Initiative_...
This code contains the simulation of consensus in multi agent system control system.
The Paxos Commit algorithm runs a Paxos consensus algorithm on the commit/abort decision of each participant to obtain a transaction commit protocol that uses 2F + 1 coordinators and makes progress ...
Ripple协议,一种更激进的区块链协商机制。
Distributed adaptive control for consensus tracking with application to formation control of nonholonomic mobile robots
optimal consensus control for a continuous-time heterogeneous linear multiagent system subject to time varying input delays. First, by discretization and model transformation, the continuous-time ...
本专著发展了分布式共识策略,以确保网络中所有车辆的信息状态收敛到一个共同的值。读者将学习如何处理空中、地面和海底环境中的自主飞行器群
Bipartite consensus of general linear multi-agent systems
TenderMint: Consensus without Mining
Consensus problems in networks of agents with switching topology and time-delays
本程序时使用小世界模型对多个智能体寻优结果的仿真。 使用方法: 将本目录下的三个文件拷贝到Matlab的工作区下,然后在Matlab的命令行中输入:confilter116(10, 1),回车即可运行。第一个参数代表仿真时间长度,第...
them into a single consensus BN structure. Specically, we are interested in that the consensus BN structure only represents independences all the given BN structures agree upon and that it has as few ...
02_ben-arieh2009_ minimum cost consensus with quadratic cost functions
分布式一致性经典论文,教你一行一行写出一个 Raft 实现
Blockchain enables new trust models ‣ Many interesting technologies – Distributed computing for consensus – Cryptography for integrity, privacy, anonymity
01_2006_multi-criteria group consensus under linear cost opinion elasticity原文