列表

详情

NC24710. [USACO 2010 Jan B]DNA Sequencing

描述

Farmer John is studying the geneology of his herd. He has M bulls (1 <= M <= 20) and F cows (1 <= F <= 20). He doesn't know, though, which bovines are potential descendants of which other bovines.
Farmer John does know the unique DNA sequence DNA_i of each and every cow and bull on his farm. DNA_i has length 25 characters and contains only upper-case letters 'A', 'C', 'G', and 'T'. He wants to determine which bovines could possibly be children of which pairs of cows and bulls.
Help Farmer John make this determination. For each pair of a cow and a bull, print how many of FJ's other bovines could possibly be their children. A bovine can be a child of a given cow and bull if
(1) it is not either of its parents (that is, a cow cannot be its own mother and a bull cannot be its own father)
(2) each position in its DNA sequence matches at least one of the characters in the same position in the two parent sequences 
So for example, 'abc' could come from pair ('axx', 'xbc'), but not from the pair ('aaa', 'bbb'). Consider three bulls and two cows with these DNA sequences:        Bull 1: GTTTTTTTTTTTTTTTTTTTTTTTT        Bull 2: AATTTTTTTTTTTTTTTTTTTTTTT        Bull 3: GATTTTTTTTTTTTTTTTTTTTTTT        Cow 1:  TTTTTTTTTTTTTTTTTTTTTTTTT        Cow 2:  ATTTTTTTTTTTTTTTTTTTTTTTT Bull 2 and cow 1 could be the parents of cow 2:        Bull 2: AATTTTTTTTTTTTTTTTTTTTTTT        Cow 1:  TTTTTTTTTTTTTTTTTTTTTTTTT        Cow 2:  ATTTTTTTTTTTTTTTTTTTTTTTT since cow 2's first letter 'A' could be from Bull 2; cow 2's second letter 'T' could come from cow 1; the remainder of the letters could come from either parent. Your goal is to create a matrix of the count of possible offspring of each pairing of bulls and cows.

输入描述

* Line 1: Two space-separated integers: M and F
* Lines 2..M+1: Line i+1 gives the DNA sequence of bull i: DNA_i
* Lines M+2..M+F+1: Line j+M+1 gives the DNA sequence of cow j: DNA_j

输出描述

* Lines 1..M: Line i: F space-separated integers. The jth integer is the number of bovines that could be children of the ith bull and jth cow.

示例1

输入: 

2 3
TGAAAAAAAAAAAAAAAAAAAAAAA
AGAAAAAAAAAAAAAAAAAAAAAAA
ATAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAA
TTAAAAAAAAAAAAAAAAAAAAAAA

输出: 

2 1 0
0 0 2

说明:

Two bulls' DNA followed by three cows' DNA
Consider bull 1 and cow 1:
b1: TGAAAAAAAAAAAAAAAAAAAAAAA
c1: ATAAAAAAAAAAAAAAAAAAAAAAA
One might express the important part of their DNA as {T|A} followed by {G|T}
Here's the 'matching' tests for bull 0 and cow 0:
b1: TGAAAAAAAAAAAAAAAAAAAAAAA -- parent, can't be offspring
b2: AGAAAAAAAAAAAAAAAAAAAAAAA offspring! Matches [TA][GT]
c1: ATAAAAAAAAAAAAAAAAAAAAAAA -- parent, can't be offspring
c2: AAAAAAAAAAAAAAAAAAAAAAAAA -- second character is 'A'; must be G or T
c3: TTAAAAAAAAAAAAAAAAAAAAAAA offspring! Matches [TA][GT]
Thus, the first element of the result matrix is 2. Other elements derived similarly.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

Java 解法, 执行用时: 59ms, 内存消耗: 10988K, 提交时间: 2023-07-16 22:47:30 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();
        int F = scanner.nextInt();
        int N = M + F;

        String[] DNA = new String[N];
        for (int i = 0; i < N; i++) {
            DNA[i] = scanner.next();
        }

        for (int bull = 0; bull < M; bull++) {
            for (int cow = M; cow < N; cow++) {
                int count = 0;
                for (int other = 0; other < N; other++) {
                    if (other == bull || other == cow) {
                        continue;
                    }
                    boolean match = true;
                    for (int j = 0; j < 25; j++) {
                        if (DNA[other].charAt(j) != DNA[bull].charAt(j) && DNA[other].charAt(j) != DNA[cow].charAt(j)) {
                            match = false;
                            break;
                        }
                    }
                    if (match) {
                        count++;
                    }
                }
                System.out.print(count + " ");
            }
            System.out.println();
        }
    }
}

C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 380K, 提交时间: 2019-11-16 21:14:46 

#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<string>
#include<string.h>
#include<iostream>
#define ll long long
using namespace std;
string s1[30],s2[30];
int M,F;
bool odk(string x,string y,string z)
{
	for(int i=0;i<x.size();i++)
	if(z[i]!=x[i]&&z[i]!=y[i])
	return 0;
	return 1;
}
int f(int x,int y)
{
	int ans=0;
	for(int i=1;i<=M;i++)
	{
		if(i==x) continue;
		if(odk(s1[x],s2[y],s1[i]))
		ans++;
	}
	for(int i=1;i<=F;i++)
	{
		if(i==y) continue;
		if(odk(s1[x],s2[y],s2[i]))
		ans++;
	}
	return ans;
}
int main()
{
	scanf("%d%d",&M,&F);
	for(int i=1;i<=M;i++)
	cin>>s1[i];
	for(int i=1;i<=F;i++)
	cin>>s2[i];
	for(int i=1;i<=M;i++)
	{
		for(int j=1;j<=F;j++)
		printf("%d ",f(i,j));
		printf("\n");
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 492K, 提交时间: 2020-04-03 11:55:13 

#include<bits/stdc++.h>
using namespace std;
string str[50];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>str[i];
	for(int i=n+1;i<=n+m;i++)
	cin>>str[i];
	for(int i=1;i<=n;i++){
	    for(int j=n+1;j<=n+m;j++){
	    	int ans=0;
	    	for(int k=1;k<=n+m;k++){
	    		if(i==k||j==k)continue;
	    		bool flag=true;
	    		for(int kk=0;kk<25;kk++)
	    		if(str[k][kk]!=str[i][kk]&&str[k][kk]!=str[j][kk]){
	    			flag=false;
	    			break;
				}
				ans+=flag;
			}
			cout<<ans<<" ";
		}
	    cout<<"\n";
	}
	return 0;
}

上一题

© 2024 nowcoder.com