频道栏目
首页 > 程序开发 > 软件开发 > 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

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:BZOJ 2326 HNOI 2011 数学作业 矩阵乘法
下一篇:45. Jump Game II Leetcode Python
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站