首页 > 其他分享 >P3667 [USACO17OPEN] Bovine Genomics G (set容器)

P3667 [USACO17OPEN] Bovine Genomics G (set容器)

时间:2024-04-24 11:00:33浏览次数:21  
标签:Genomics set Cow 斑点 Bovine int ch cows he

[USACO17OPEN] Bovine Genomics G

题目描述

Farmer John owns \(N\) cows with spots and \(N\) cows without spots. Having just completed a course in bovine genetics, he is convinced that the spots on his cows are caused by mutations in the bovine genome.

At great expense, Farmer John sequences the genomes of his cows. Each genome is a string of length \(M\) 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\) and \(M=8\):

Positions: 1 2 3 4 5 6 7 8

Spotty Cow 1: A A T C C C A T
Spotty Cow 2: A C 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 C T C G C A T
Plain Cow 3: A C T T C C A T

Looking carefully at this table, he surmises that the sequence from position 2 through position 5 is sufficient to explain spottiness. That is, by looking at the characters in just these these positions (that is, positions \(2 \ldots 5\)), Farmer John can predict which of his cows are spotty and which are not. For example, if he sees the characters GTCG in these locations, he knows the cow must be spotty.

Please help FJ find the length of the shortest sequence of positions that can explain spottiness.

农夫约翰拥有N头带斑点的奶牛和N头没有斑点的奶牛。他刚刚完成了牛遗传学课程,他确信奶牛上的斑点是由牛基因组突变引起的。

农夫约翰花了大钱对他奶牛的基因组进行测序。每个基因组都是一串长度为M的字符串,由四个字符A,C,G和T构成。当他排列奶牛的基因组时,他得到一张如下表,如下所示

对于N = 3和M = 8:

Positions:1 2 3 4 5 6 7 8

Positions: 1 2 3 4 5 6 7 8

Spotty Cow 1: A A T C C C A T
Spotty Cow 2: A C 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 C T C G C A T
Plain Cow 3: A C T T C C A T
他仔细查看该表,认为从位置2到位置5的顺序足以解释斑点。也就是说,仅通过查看这些位置(即位置2 ……5)中的字符,农夫约翰就可以预测出他的哪些母牛斑点,哪些不是斑点。例如,如果他在这些位置看到字符GTCG,他就知道那头母牛一定是斑点的。

请帮助FJ找到可以解释斑点的最短位置序列的长度。

FJ有一些有斑点和一些没有斑点的牛,他想搞清楚到底什么基因控制这个牛有没有斑点。

于是他找了n有斑点的牛和n头没有斑点的牛

这些牛的基因长度为m(基因中之包含ATCG四个字母)

求这个序列中的一个子串,可以确定是否有斑点。

子串需要符合要求:有斑点的牛这部分的子串,不能和无斑点的牛的这部分子串相同

求最短子串长度

输入格式

The first line of input contains \(N\) (\(1 \leq N \leq 500\)) and \(M\) (\(3 \leq M \leq 500\)). 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. No spotty cow has the same exact genome as a plain cow.

输出格式

Please print the length of the shortest sequence of positions that is sufficient to explain spottiness. A sequence of 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 locations in the genome.

样例 #1

样例输入 #1

3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

样例输出 #1

4

分析

这本是一个字符串hash题

但是set容器的使用 让这道题变得轻而易举

读题可知

给定n个A串和n个B串,长度均为m,求一个最短的区间[l,r]

使得不存在一个A串a和一个B串b,使得a[l,r]=b[l,r]

求最大的最小

直接二分

上代码

code

Elaina's code
#include<bits/stdc++.h>
using namespace std;
const int N=505;
#define ll long long
//#define int long long
#define inf 0x3f
#define INF 0x3f3f3f3f
#define Elaina 0
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

int n,m;
string a[N],b[N];
set<string> s;//set容器 -->集合 

bool check(int x,int k){
	s.clear();//清空 
	
	for(int i=1;i<=n;i++){
		s.insert(a[i].substr(x,k));//插入元素 
	}
	for(int i=1;i<=n;i++){
		if(s.count(b[i].substr(x,k))){//count(i)判断容器中是否存在i这个元素 
			return 0;
		}
	}
	return 1;
}

main(){
	n=read(),m=read();
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	
	int l=1,r=m,mid;
	bool flag;
	while(l<r){
		flag=0;
		mid=(l+r)>>1;
		for(int i=0;i<=m-mid;i++){
			if(check(i,mid)){
				flag=1;
				break;
			}
		}
		if(flag){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	
	printf("%d\n",l);
	return Elaina;
}

都看到这了,真的不点个赞吗(>ω<*)

标签:Genomics,set,Cow,斑点,Bovine,int,ch,cows,he
From: https://www.cnblogs.com/Elaina-0/p/18154586

相关文章

  • 关于set容器
    简介集合(set)用以有序地存储互异元素的容器。其实现是由节点组成的红黑树,每个节点都包含着一个元素,节点之间以某种比较元素大小的谓词进行排列。头文件#include<set>常用操作声明set<数据类型>变量名操作插入与删除insert(x)当容器中没有等价元素的时候,将元素......
  • MPV PLAYER video settings 视频设置
    ###################videosettings####################Startinfullscreenmodebydefault.#fs=yes#forcestartingwithcenteredwindow#geometry=50%:50%#don'tallowanewwindowtohaveasizelargerthan90%ofthescreensize#autofit-larger=90......
  • Mysql 密码报错 You must reset your password ... 和 Your password does N
    如果MySQL数据库用户的密码设置过于简单,数据库在用户登录后会提示重置密码,并且不接受简单的密码。提示需要重置密码:ERROR1820(HY000):YoumustresetyourpasswordusingALTERUSERstatementbeforeexecutingthisstatement.Mysql数据库版本:5.7.1操作系统:CentOS7这......
  • HINT: It seems you set a fixed date / time / datetime value as default for this
    WARNINGS:customers.PackingHead.packing_date:(fields.W161)Fixeddefaultvalueprovided.HINT:Itseemsyousetafixeddate/time/datetimevalueasdefaultforthisfield.Thismaynotbewhatyouwant.Ifyouwanttohavethecurrentdateasdefault......
  • multiset容器
    和set容器不同的是,multiset容器可以存储多个值相同的元素。multiset容器类模板的定义如下所示:template<classT,//存储元素的类型classCompare=less<T>,//指定容器内部的排序规则classAlloc=allocator<T......
  • 容器使用之multiset
    容器使用之multiset可以理解为小型关联数据库底层结构:红黑树示例代码:#pragma#ifndef__MULTISET__#define__MMULTISE__​#include<set>#include<iostream>​usingnamespacestd;​namespaceMyTestSet{voidtest_set(long&value){multiset<string>c;/......
  • Solution Set - 杂题分享3
    [THUPC2018]淘米神的树先考虑开局只有一个黑点,将黑点做根,问有多少种排列满足父亲在儿子前。很平凡的问题,设\(f_u\)为\(u\)子树的合法序列个数,\(f_u=(siz_u-1)!\sum_{v\inson_u}\frac{f_v}{siz_v!}\),先将根放入,再由合法子树相对序列代替全排列。整理答案为\(ans=\frac{\prod_u......
  • set容器
    set容器定义于<set>头文件,并位于std命名空间中。因此如果想在程序中使用set容器,该程序代码应先包含如下语句:#include<set>usingnamespacestd;set容器的类模板定义如下:template<classT,//键key和值value的类型classCom......
  • 使用ThreadPool.SetMinThreads方法提升API服务响应性能
     使用该方法的背景?某个API服务在每日请求量40W的情况下,流量增多时会产生大量请求异常:Theoperationwascanceled,从实际情况来看,并不是外部依赖接口或者服务实例不足导致,于是设置线程池数量后,服务性能提升效果显著。方法定义:设置线程池在新请求预测中维护的空闲线程数。pu......
  • django的settings
    django的settings模板jwt配置fromdatetimeimporttimedelta#jwt配置SIMPLE_JWT={#AccessToken的有效期'ACCESS_TOKEN_LIFETIME':timedelta(minutes=5),#RefreshToken的有效期'REFRESH_TOKEN_LIFETIME':timedelta(days=7),......