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

题意：

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