jsp网站建设期末作业,挖掘关键词爱站网,视觉设计师面试问题,wordpress resume【题目背景】
生物的遗传物质存在个体间或种群水平的差异#xff0c;这样的差异被称为遗传变异。突变及基因重组等因素都会导致遗传变异。尽管亲代在将其遗传信息传递给子代时会发生遗传变异#xff0c;但是这些遗传变异仅占遗传物质的一小部分#xff0c;通常亲代和子代之…【题目背景】
生物的遗传物质存在个体间或种群水平的差异这样的差异被称为遗传变异。突变及基因重组等因素都会导致遗传变异。尽管亲代在将其遗传信息传递给子代时会发生遗传变异但是这些遗传变异仅占遗传物质的一小部分通常亲代和子代之间的遗传物质非常相似。遗传变异会在生物繁殖的过程中不断累积。通过比较不同生物的基因特征及基因组结构可以大致确定生物之间的亲缘关系并建立系统进化树。在比较过程中可能有一些遗传物质的子序列完全相同或相似我们称这种序列为保守序列。 假设现在已经测定了若干以 DNA 为遗传物质的生物的 DNA 碱基序列希望通过比较这些基序列推测生物之间的亲缘关系。为了简化比较先将碱基序列划分为若干个保守序列片段。考虑到 DNA 序列可能发生缺失、插入等影响片段数量的遗传变异将划分得到的片段对齐至 M 个片段并使用小写字母来表示对齐后的每一个片段。
【题目描述】
已知一棵包含了 N 个生物的系统进化树这些生物的 DNA 序列对应的对齐至 M 个片段的序列可以用仅含小写字母的字符串表示为 1,…,s1,…,sN 。在这棵系统进化树上如果两个生物对应的序列最多只有 K 处对应位置上的片段不相同即对应字母不同就称这两个生物的亲缘关系相近。 现有 Q 个尚未确定亲缘关系的生物对齐得到序列分别为 1,…,t1,…,tQ 。为了确定这些生物在系统进化树上的位置请对 Q 个生物分别求出原树中有多少个生物与其亲缘关系相近。
Input 输入的第一行包含四个正整数 N,Q,M,K分别表示系统进化树上的生物数量、待确定亲缘关系的生物数量、对齐后的序列长度和比较序列时容许的最大差异数。保证 1≤N,Q≤3001≤M≤60,0001≤K≤10。 接下来 N 行每行输入一个长度恰好为 M仅包含小写字母的字符串 si 表示系统进化树上的每个生物对应的模板序列。 接下来 Q 行每行输入一个长度恰好为 M仅包含小写字母的字符串 tj 表示待确定亲缘关系的每个生物对应的查询序列。 保证输入的两个字符串均仅包含小写字母。
Output 输出共 Q 行其中第 j 行输出一个非负整数表示在系统进化树上与第 j 个待确定的生物亲缘关系相近的生物数量。
样例输入1 6 4 4 1 kaki kika manu nana tepu tero kaka mana teri anan
样例输出1 2 2 1 0
样例输入2 8 6 7 3 delphis aduncus peronii plumbea clymene hectori griseus electra delphis helpiii perphii clumeee eleelea ddlpcus
样例输出2 1 1 2 2 1 2
解析 因为k很小所以我们可以直接暴力枚举匹配串然后用字符串哈希加二分暴力往前跳到不匹配的地方 k次就可以了。
#include bits/stdc.h
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ULL;
typedef pairint,int PII;
const int N100010,P131;
ULL h[310][N]; //表示系统进化树上每个生物字符串的哈希值
ULL h1[N]; //表示待确定亲缘关系的生物字符串的哈希值
ULL p[N];
int n,q,m,k;
string s;
ULL find1(int i,int l,int r) //返回h[i]字符串中l到r的哈希值
{return h[i][r]-h[i][l-1]*p[r-l1];
}
ULL find2(int l,int r) //返回字符串中l到r的哈希值
{return h1[r]-h1[l-1]*p[r-l1];
}
bool check(int i,int l,int r)
{return find1(i,l,r)find2(l,r);
}
int main()
{ios;cinnqmk;p[0]1;for (int i1;iN;i) p[i]p[i-1]*P;for (int i0;in;i){cins;for (int j1;js.size();j) h[i][j]h[i][j-1]*Ps[j-1];}while (q--){cins;for (int i1;is.size();i) h1[i]h1[i-1]*Ps[i-1];int ans0;for (int i0;in;i){int now0;for (int j1;jm;j) {if (!check(i,j,j)){if (nowk) break;}else {int lj,rm;while (lr) //二分快速找到下一处不匹配的位置{int midlr11;if (check(i,l,mid)) lmid;else rmid-1;}jl; //返回不匹配的位置}}if (nowk) ans;}coutansendl;}return 0;
}
