首页 > 其他分享 >P3670 [USACO17OPEN] Bovine Genomics S 题解

P3670 [USACO17OPEN] Bovine Genomics S 题解

时间:2024-03-09 12:36:40浏览次数:22  
标签:Genomics vis int 题解 31 三元组 字符串 num USACO17OPEN

题意

给定 \(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\)(已被标记),则直接继续枚举下一个三元组。

  • 否则,若第二组字符串遍历完成后仍没有被标记过的,将答案累加。

需要注意的细节是,我们可以将字符串中包含的 ACGT 字母映射为 \(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

相关文章

  • CF99B Help Chef Gerasim 题解
    分别对三种情况进行分类讨论。第一种情况:显然,若\(\sum^{n}_{i=1}a_i\bmodn\neq0\),则输出\(\texttt{Unrecoverableconfiguration.}\);同时,我们遍历\(a_{1\simn}\),若存在两个以上的\(a_i\)满足\(a_i\neq\sum^{n}_{i=1}a_i\divn\),则也输出\(\texttt{Unreco......
  • P10217 [省选联考 2024] 季风题解
    考场上没写出来,火大,实际上这题放校内%你赛我肯定写的出来,可惜这是省选。实际上这题不难,主要是观察性质,接着拆柿子,然后就是有点难写,要写得好看有点考验代码构建能力和数学能力。我们考虑原题的每对\((x,y)\)都要满足\(|x|+|y|\lek\)而我们可以知道后面应该填的\((x,y)\)如......
  • CF348A Mafia 题解
    由于题目具有十分明显的单调性(若\(x\)局能满足要求,则\(>x\)局一定能满足;若\(x\)局无法满足要求,则\(<x\)局也无法满足),因此我们考虑进行二分答案。二分所需要的局数\(x\),设所有人想玩的总局数为\(S\),由题意可得\(S=\sum^{n}_{i=1}a_i\)。因为每局都会有\(1\)人主持,\(n......
  • [ABC297F] Minimum Bounding Box 2 题解
    容斥真有趣。有一个性质:两个相同的子矩阵,对答案的贡献一定相同。所以就只需要枚举矩阵大小即可。我们设当前矩阵长\(i\)宽\(j\)(对应的,\(H\)为长,\(W\)为宽),假如要给答案做出贡献,矩阵的四条边一定都有点,发现可以容斥了。至少\(0\)条边上有点的方案数为\(a=C_{i\times......
  • P4139 上帝与集合的正确用法 题解
    传送门我觉得这题最有意思的其实是"最终会固定为一个数"这个结论。扩展欧拉定理:\(a^b\bmodp\),当\(b\ge\varphi(p)\)时,\(a^b\equiva^{b\bmod\varphi(p)+\varphi(p)}\pmodp\)。所以\(2^{2^{2^{\cdots}}}\)可以递归求解。边界条件\(p=1\)。复杂度如何保证?其实就是......
  • P4774 屠龙勇士 题解
    传送门显然每一只龙对应了唯一的一把剑。用multiset可以求出每一把剑。于是题目就变成了:\[\begin{cases}b_1x\equiva_1\pmod{m_1}\\b_2x\equiva_2\pmod{m_2}\\\dots\\b_nx\equiva_n\pmod{m_n}\end{cases}\]如果\(b_i=1\),直接EXCRT即可。现在\(b_i>1\),还是以EXCRT......
  • APatch常见问题解答
    常见问题解答什么是APatch?APatch是一种类似于Magisk或KernelSU的root解决方案,但APatch提供更多功能。APatch分别结合了Magisk方便易用的通过boot.img安装的方法,和KernelSU强大的内核修补能力。APatch与Magisk的区别?Magisk对启动映像中的ramdisk进行补丁,以修改init系统。而AP......
  • P6810 「MCOI-02」Convex Hull 凸包 题解
    分析推式子题。\[ans=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\tau(i)\tau(j)\tau(\gcd(i,j))\]对于\((i,j)\),若\(k\)是\((i,j)\)的因子,则\(k\)一定整除\(i,j\),所以有:\[\\\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\tau(i)\tau(j)\sum\limits......
  • CF1436E Complicated Computations 题解
    题目链接:CF或者洛谷关于\(mex\)问题是一个比较久远的问题,有很多经典的方法去解决。本题的\(mex\)是从正整数开始的,不要忽略掉。来讲讲常见的两种解决方案,首先回到题目所问,如果我们暴力地询问:\(1,2,3,4,.....mex\)是否都能由原数组构造出来,对于\(i\)如果它可以由原数组......
  • CF935D Fafa and Ancient Alphabet 题解
    讲一个很暴力的方法(为描述方便,下文\(a\)数组代表\(s1\),\(b\)数组代表\(s2\))。发现假如当前\(a_i\neb_i\),就不需要再向下枚举了,于是拥有了分类讨论的雏形。我们设\(inv\)代表进行到这一步的概率,可分为以下四种情况:\(a_i>0,b_i>0\)。此时假如\(a_i=b_i\),略过;若\(a_i>......