CodeForces 520C DNA Alignment - c++编程基础

TOP

CodeForces 520C DNA Alignment

2015-07-20 17:13:58 来源: 作者: 【大中小】浏览:2次

Tags：CodeForces 520C DNA Alignment

题意：

一段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


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：BZOJ 2326 HNOI 2011 数学作业矩..	下一篇：C. DNA Alignment 数学公式推导 C..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: