A32889. 基因组分析程序文件名：t5.cpp输入文件名：t5.in输出文件名：t5.out。乌龟得到了他的基因组，一个只包含“ATCG”四种字母的字符串。乌龟想起科学家说，基因组中很多片段都多次重复出现，而且这种重复是很有意义的，于是他想计算一下自己基因组里片段的重复情况。给定一个基因组，其中一个长度为k 的子串称为一个“k-片段”。乌龟希望你计算出基因组中不同的k-片段数量。例如，基因组“TACAC” …
填空题
困难
知识点
题目描述
基因组分析
程序文件名：t5.cpp
输入文件名：t5.in
输出文件名：t5.out。
乌龟得到了他的基因组，一个只包含“ATCG”四种字母的字符串。乌龟想起科学家说，基因组中很多片段都多次重复出现，而且这种重复是很有意义的，于是他想计算一下自己基因组里片段的重复情况。给定一个基因组，其中一个长度为k 的子串称为一个“k-片段”。乌龟希望你计算出基因组中不同的k-片段数量。例如，基因组“TACAC” 的2-片段有“TA”,“AC”, “CA”, “AC”，其中不同的片段数量有3 个。
输入
整数n, k, R1，表示基因组的长度、片段的长度和数列生成的首项。基因组第i (1 _ i _ n) 个字符在Ri mod 4 的值为0, 1, 2, 3 时分别为A, T, C, G
输出
一个整数，表示不同的k-片段的数量
样例输入
20 2 37
样例输出
10
数据规模
30% 的数据满足n<=100; 100%的数据满足1<=n<=10^5, 1<=k<= 10
参考答案
#include<bits/stdc++.h>
using namespace std;
int a[100010],r[100010],ha[2000000];
int n,k,t=1,ans,sum;
void init()
{
cin>>n>>k>>r[1];
for(int i=1;i<=n;++i){
a[i]=r[i]%4;
r[i+1]=(r[i]*6807+2831)%201701;
}
}
int main()
{
freopen("t5.in","r",stdin);
freopen("t5.out","w",stdout);
init();
for(int i=1;i<=k;++i){
sum=sum+a[i]*t;
t=t*4;
}
ha[sum]=1;t=t/4;
for(int i=k+1;i<=n;++i){
sum=sum/4;
sum=sum+a[i]*t;
ha[sum]=1;
}
for(int i=0;i<2000000;++i)
if(ha[i]==1)ans++;
cout<<ans;
fclose(stdin);fclose(stdout);
return 0;
}
上一题
下一题