自动搬运

查看原文

来自洛谷，原作者为

	YBaggio ♥carfosia

搬运于2025-08-24 21:51:27，当前版本为作者最后更新于2022-07-16 16:17:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

$\verb!FJ!$ 有 $n$ 头有斑点和 $n$ 头没有斑点的牛。

他认为一头牛有没有斑点和它的基因有关，所以他获取了所有奶牛的基因。

这些基因以字符串的形式给出，字符串中只包含 $\verb!A,C,G,T!$。

如果 $\verb!FJ!$ 认为一头奶牛的基因的第 $i,j,k$ 个字符决定它有没有斑点，那么 $i,j,k$ 必须满足:

任意一头 有斑点的 牛的基因的第 $i,j,k$ 个字符没有一个有斑点的 牛与其重复。

求共有的多少个 符合规定 的 $i,j,k$。

举个例子1

斑点牛 :

1. $\verb!ATG...!$

2. $\verb!ACG...!$

3. $\verb!AGT...!$

无斑牛 :

1. $\verb!ACC...!$

2. $\verb!ACC...!$

3. $\verb!ACC...!$

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

举个例子2

斑点牛 ：

1. $\verb!ATG...!$；

2. $\verb!ACC...!$；

3. $\verb!AGT...!$；

无斑牛 ：

1. $\verb!ACC...!$；

2. $\verb!ACC...!$；

3. $\verb!ACC...!$；

可见 $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;
}