CodeForces 520C DNA Alignment

题意:

一段DNA序列(10^5长度) 定义h函数为两序列相同碱基个数 p函数为分别移动两个DNA序列后所有可能的h函数之和 问使p最大的序列有多少个

思路:

根据p函数的定义 我们发现p这个函数其实就是A序列每个碱基和B序列每个碱基比较再乘一个n

因此可以贪心构造B序列 即每次新加一个碱基必定是A序列中出现次数最多的碱基

那么最后的答案就是A序列中出现次数最多的碱基种类数的n次方

代码:

#include<cstdio>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<map>#include<set>#include<vector>#include<queue>#include<cstdlib>#include<ctime>#include<cmath>using namespace std;typedef long long LL;#define N 100010#define mod 1000000007int n;char s[N];int f[10];template<class T>inline void RD(T &ret){char c;ret = 0;while ((c = getchar()) < '0' || c > '9');while (c >= '0' && c <= '9')ret = ret * 10 + (c – '0'), c = getchar();}LL quickpow(LL m , int n){LL ans = 1;while(n) {if(n&1) ans = (ans * m) % mod;n = n >> 1;m = (m * m) % mod;}return ans;}int main(){RD(n);scanf("%s",s);for(int i=0;i<n;i++){if(s[i]=='A') f[1]++;else if(s[i]=='G') f[2]++;else if(s[i]=='C') f[3]++;else if(s[i]=='T') f[4]++;}int m;m=max(max(f[1],f[2]),max(f[3],f[4]));int x=0;for(int i=1;i<=4;i++){if(f[i]==m) x++;}printf("%I64d\n",quickpow(x,n));return 0;}

,每年的情人节圣诞节除夕,也和他共度。甚至连吵架也是重复的,

CodeForces 520C DNA Alignment

相关文章:

你感兴趣的文章:

标签云: