[LibreOJ 537] DNA 序列

//其实本来是要写LibreOJ的比赛来
//但成绩惨不忍睹，而且题目也不会改

题目描述
NOIP 复赛之前，HSD 桑进行了一项研究，发现人某条染色体上的一段 DNA 序列中连续的 kkk 个碱基组成的碱基序列与做题的 AC 率有关！于是他想研究一下这种关系。
现在给出一段 DNA 序列，请帮他求出这段 DNA 序列中所有连续 k 个碱基形成的碱基序列中，出现最多的一种的出现次数。
输入格式
两行，第一行为一段 DNA 序列，保证 DNA 序列合法，即只含有 A, G, C, T 四种碱基；
第二行为一个正整数k，意义与题目描述相同。
输出格式
一行，一个正整数，为题目描述中所求答案。
样例
样例输入 1

AAAAA
1
样例输出 1

5
样例解释 1

对于这段 DNA 序列，连续的 1 个碱基组成的碱基序列只有 A，共出现 5 次，所以答案为 5。

样例输入 2

ACTCACTC
4
样例输出 2

2
样例解释 2

对于这段 DNA 序列，连续的 4 个碱基组成的碱基序列为：ACTC, CTCA, TCAC 与 CACT。其中 ACTC 出现 2次，其余均出现 1次，所以出现最多的次数为 2，即为答案。

//刚开始看错题，以为是水题
//后来读懂了，发现要用hash，(但本蒟蒻不会玩hash啊
//只能写了个十进制的map维护的hash
//但提交时忘了去掉freopen了（GG

80分map

#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<cstring>
using namespace std;

const int maxn = 5000000 + 100;
char a[maxn];
int val[maxn],k;
long long ans = 0;
map<long long,long long>q;

int main() {
	scanf("%s%d",a,&k);
	int l = strlen(a);
	for(int i = 0; i < l; i++) {
		if(a[i] == 'A') val[i + 1] = 1;
		else if(a[i] == 'G') val[i + 1] = 2;
		else if(a[i] == 'C') val[i + 1] = 3;
		else if(a[i] == 'T') val[i + 1] = 4;
	}
	long long p = val[1];
	long long mod = 1;
	for(int i = 1; i < k; i++) mod *= 10;
	for(int i = 2; i <= k; i++) {
		p = p * 10 + val[i];
	}
	q[p]++;
	ans = max(ans,q[p]);		
	for(int i = k + 1; i <= l; i++) {
		p = p % mod;
		p = p * 10 + val[i];
		q[p]++;
		ans = max(ans,q[p]);
	}
	cout<<ans;
	return 0;
}

正解其实有很多种搞法
因为hash后只有4^10所以记个数组O(1)维护就好，不用map
(其实还可以位运算优化下)

#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<cstring>
using namespace std;

const int maxn = 5000000 + 100;
char a[maxn];
int q[maxn];
int val[maxn],k;
int ans = 0;

int main() {
	scanf("%s%d",a,&k);
	int l = strlen(a);
	for(int i = 0; i < l; i++) {
		if(a[i] == 'A') val[i + 1] = 1;
		else if(a[i] == 'G') val[i + 1] = 2;
		else if(a[i] == 'C') val[i + 1] = 3;
		else if(a[i] == 'T') val[i + 1] = 4;
	}
	int p = 0;
	int mod = 1;
	for(int i = 1; i < k; i++) mod *= 4;
	for(int i = 1; i <= k; i++) {
		if(!p) p = val[i];
		else p = p * 4 + val[i];
	}		
	q[p]++;	ans = max(ans,q[p]);
	for(int i = k + 1; i <= l; i++) {
		p = p % mod;
		p = p * 4 + val[i];
		q[p]++;
		ans = max(ans,q[p]);
	}
	cout<<ans;
	return 0;
}