P3670 [USACO17OPEN]Bovine Genomics S

· · 题解

题意

他认为一头牛有没有斑点和它的基因有关，所以他获取了所有奶牛的基因。 这些基因以字符串的形式给出，字符串中只包含 $\verb!A,C,G,T!$。 如果 $\verb!FJ!$ 认为一头奶牛的基因的第 $i,j,k$ 个字符决定它有没有斑点，那么 $i,j,k$ 必须满足: 任意一头 **有斑点的** 牛的基因的第 $i,j,k$ 个字符没有一个**有斑点的** 牛与其重复。 求共有的多少个 **符合规定** 的 $i,j,k$。 ### 举个例子1 **斑点牛** : 1. $\verb!ATG...!
  1. \verb!ACG...!
  2. \verb!AGT...!

无斑牛 :

  1. \verb!ACC...!
  2. \verb!ACC...!
  3. \verb!ACC...!

可见 1,2,3 号位可以判断牛有没有斑点，因为没有一头斑点牛的 1,2,3 号基因在无斑牛中出现过。

举个例子2

斑点牛 ：

无斑牛 ：

可见 1,2,3 号位不可以判断牛有没有斑点，因为有第 2 头斑点牛的 1,2,3 号基因在无斑牛中出现过。

思路

可以先从时间复杂度入手。

首先花 O(m^3) 暴力枚举这三个位置，接下来的问题是如何在 O(n) 的时间内判断。

可以先想想如何用 O(n^2) 的时间判断。

对于多个字符串是否相同的判断，我们很容易想到哈希表。

先计算出每个斑点牛这三个位置的哈希值，再计算每个无斑牛的哈希值，看有没有相同的。

怎么优化呢？

我么可以定义两个哈希数组: hashs,hashp ，分别储存斑点牛和无斑牛。设 H 一个为有斑牛的哈希值。那么我们将 hashs_H 设为 true。 设 h 为一个无斑牛的哈希值。则将 hashp_i 设为 h。

那么我们如果想要判断第 i 个无斑牛的哈希值是否在斑点牛中出现过。就可以使用表达式 hashs_{hashp_i} 来判断。

最后贴上代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char S[510][55],P[510][55];
int HashS[20000],HashP[20000];
bool B[55][55][55];
void hashS(int fir,int sec,int thi){
    memset(HashS,0,sizeof(HashS));
    for(int i=1;i<=n;i++){
        int tmp=(S[i][fir]-'A'+1)+(S[i][sec]-'A'+1)*26+(S[i][thi]-'A'+1)*26*26;
        HashS[tmp]=1;
    }
    return;
}
void hashP(int fir,int sec,int thi){
    memset(HashP,0,sizeof(HashP));
    for(int i=1;i<=n;i++){
        int tmp=(P[i][fir]-'A'+1)+(P[i][sec]-'A'+1)*26+(P[i][thi]-'A'+1)*26*26;
        HashP[i]=tmp;
    }
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)cin>>S[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>P[i][j];
    }
    int fir,sec,thi;
    for(fir=1;fir<=m;fir++){
        for(sec=fir+1;sec<=m;sec++){
            for(thi=sec+1;thi<=m;thi++){
                bool flag=0;
                hashS(fir,sec,thi);
                hashP(fir,sec,thi);
                for(int i=1;i<=n;i++){
                    if(HashS[HashP[i]]){flag=1;break;}//哈希小技巧
                }
                if(flag)continue;
                B[fir][sec][thi]=1;//记录答案
            }
        }
    }
    for(int i=1;i<=m;i++){//统计答案
        for(int j=1;j<=m;j++){
            for(int k=1;k<=m;k++){
                if(B[i][j][k])ans++;
            }
        }
    }   
    printf("%d",ans);
    return 0;
}