CodeForces 520C DNA Alignment - c++语言程序开发技术文章_c++编程

首页 > 程序开发 > 软件开发 > C++ > 正文

CodeForces 520C DNA Alignment

2015-03-03 14:57:53 来源：House

收藏我要投稿

题意：

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

思路：

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

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

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

代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define N 100010
#define mod 1000000007

int n;
char s[N];
int f[10];

template
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

点击复制链接与好友分享!回本站首页