程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> CodeForces 520C DNA Alignment

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved