NC24101. [USACO 2017 Ope S]Bovine Genomics
描述
At great expense, Farmer John sequences the genomes of his cows. Each genome is a string of length MM built from the four characters A, C, G, and T. When he lines up the genomes of his cows, he gets a table like the following, shown here for N=3:
Positions: 1 2 3 4 5 6 7 ... M Spotty Cow 1: A A T C C C A ... T Spotty Cow 2: G A T T G C A ... A Spotty Cow 3: G G T C G C A ... A Plain Cow 1: A C T C C C A ... G Plain Cow 2: A G T T G C A ... T Plain Cow 3: A G T T C C A ... T
Looking carefully at this table, he surmises that positions 2 and 4 are sufficient to explain spottiness. That is, by looking at the characters in just these two positions, Farmer John can predict which of his cows are spotty and which are not (for example, if he sees G and C, the cow must be spotty).
Farmer John is convinced that spottiness can be explained not by just one or two positions in the genome, but by looking at a set of three distinct positions. Please help him count the number of sets of three distinct positions that can each explain spottiness.
输入描述
The first line of input contains N (1≤N≤500) and M (3≤M≤50). The next N lines each contain a string of M characters; these describe the genomes of the spotty cows. The final N lines describe the genomes of the plain cows.
输出描述
Please count the number of sets of three distinct positions that can explain spottiness. A set of three positions explains spottiness if the spottiness trait can be predicted with perfect accuracy among Farmer John's population of cows by looking at just those three locations in the genome.
示例1
输入:
3 8 AATCCCAT GATTGCAA GGTCGCAA ACTCCCAG ACTCGCAT ACTTCCAT
输出:
22
C(clang11) 解法, 执行用时: 531ms, 内存消耗: 1276K, 提交时间: 2020-11-07 13:52:51
#include<stdio.h>
char s[1000][1000];
a[4][4][4][2];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int i,j,k,t;
for(i=0;i<n*2;i++)
scanf("%s",s[i]);
int sum=0;
for(i=0;i<m;i++)
for(j=i+1;j<m;j++)
for(k=j+1;k<m;k++)
{
int b,c,d;
for(b=0;b<4;b++)
for(c=0;c<4;c++)
for(d=0;d<4;d++)
a[b][c][d][0]=a[b][c][d][1]=0;
for(t=0;t<n;t++)
{
if(s[t][i]=='A')
b=0;
else if(s[t][i]=='T')
b=1;
else if(s[t][i]=='C')
b=2;
else if(s[t][i]=='G')
b=3;
if(s[t][j]=='A')
c=0;
else if(s[t][j]=='T')
c=1;
else if(s[t][j]=='C')
c=2;
else if(s[t][j]=='G')
c=3;
if(s[t][k]=='A')
d=0;
else if(s[t][k]=='T')
d=1;
else if(s[t][k]=='C')
d=2;
else if(s[t][k]=='G')
d=3;
a[b][c][d][0]++;
}
for(t=n;t<n*2;t++)
{
if(s[t][i]=='A')
b=0;
else if(s[t][i]=='T')
b=1;
else if(s[t][i]=='C')
b=2;
else if(s[t][i]=='G')
b=3;
if(s[t][j]=='A')
c=0;
else if(s[t][j]=='T')
c=1;
else if(s[t][j]=='C')
c=2;
else if(s[t][j]=='G')
c=3;
if(s[t][k]=='A')
d=0;
else if(s[t][k]=='T')
d=1;
else if(s[t][k]=='C')
d=2;
else if(s[t][k]=='G')
d=3;
a[b][c][d][1]++;
}
int flag=1;
for(b=0;b<4;b++)
for(c=0;c<4;c++)
for(d=0;d<4;d++)
if(a[b][c][d][0]>0&&a[b][c][d][1]>0)
flag=0;
sum+=flag;
}
printf("%d",sum);
}
C++ 解法, 执行用时: 368ms, 内存消耗: 524K, 提交时间: 2022-06-04 13:39:31
// USACO 2017 Open S. Bovine Genomics
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
int main(void) {
ios::sync_with_stdio(false), cin.tie(0);
int N, M;
cin >> N >> M;
vector<string> A(N), B(N);
for (string& s : A) cin >> s;
for (string& s : B) cin >> s;
unordered_set<string> S;
int ans = 0;
_for(i, 0, M) _for(j, i + 1, M) _for(k, j + 1, M) {
bool ok = true;
S.clear();
for (const string& s : A) S.insert({s[i], s[j], s[k]});
for (const string& s : B)
if (S.count({s[i], s[j], s[k]})) {
ok = false;
break;
}
ans += ok;
}
cout << ans << "\n";
return 0;
}