题意
给定 \(2\) 组字符串,每组 \(n\) 个,每个字符串包含 \(m\) 个字符。
我们称一个三元组 \((i,j,k)\) 是合法的,当且仅当第二组的每个字符串中下标为 \((i,j,k)\) 的字符拼成的字符串与第一组的每个字符串中下标为 \((i,j,k)\) 的字符拼成的字符串均不相等。
现在需要你对于给定的 \(2\) 组字符串,找出所有合法的三元组 \((i,j,k)\) 的数量。
分析
因为观察到题目中 \(n,m\) 的数据范围都很小,所以我们考虑直接朴素枚举三元组 \((i,j,k)\),再依次检查合法性。
在检查三元组 \((i,j,k)\) 的合法性时,我们可以建立一个标记数组 \(vis\):
-
首先遍历第一组字符串,对于第 \(x\) 个字符串 \(s_x\),将 \(vis_{s_{x,i},s_{x,j},s_{x,k}}\) 标记为 \(1\)。
-
再遍历第二组字符串,对于第 \(x\) 个字符串 \(s_x\),若 \(vis_{s_{x,i},s_{x,j},s_{x,k}}=1\)(已被标记),则直接继续枚举下一个三元组。
-
否则,若第二组字符串遍历完成后仍没有被标记过的,将答案累加。
需要注意的细节是,我们可以将字符串中包含的 A
、C
、G
、T
字母映射为 \(0\)、\(1\)、\(2\)、\(3\) 四个数字,从而将字符矩阵转换为整数矩阵,方便存储。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,num[31]; //num表示映射数组
int a[531][131],b[531][131]; //a,b是由字符矩阵转换为的整数矩阵
bool vis[31][31][31]; //vis是标记数组
bool check(int x,int y,int z){ //检查三元组(x,y,z)是否合法
memset(vis,0,sizeof(vis)); //注意清空
for(int i=1;i<=n;i++)
vis[a[i][x]][a[i][y]][a[i][z]]=1; //标记
for(int i=1;i<=n;i++)
if(vis[b[i][x]][b[i][y]][b[i][z]]) //被标记过了
return 0;
return 1;
}
int main(){
cin>>n>>m;
num['A']=0,num['C']=1,num['G']=2,num['T']=3; //映射字母
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char c; cin>>c; a[i][j]=num[c]; //转为整数矩阵
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char c; cin>>c; b[i][j]=num[c]; //同上
}
for(int i=1;i<=m;i++) //枚举三元组
for(int j=i+1;j<=m;j++)
for(int k=j+1;k<=m;k++)
if(check(i,j,k)) ans++; //若合法则累加
cout<<ans;
return 0;
}
标签:Genomics,vis,int,题解,31,三元组,字符串,num,USACO17OPEN
From: https://www.cnblogs.com/XOF-0-0/p/18062510