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

CodeForces 520C DNA Alignment

編輯：C++入門知識

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
  1. 上一頁:
  2. 下一頁:
C++入門知識
帶姓名的成績單

[cpp] /*  * 程序的版權和版本聲明
一種使用GDI+對圖片尺寸和質量的壓縮方法

今天同事向我詢問圖片壓縮的算法，我想起
hdu 5074 Hatsune Miku（2014 鞍山現場賽）

hdu 5074 Hatsune Miku（2014 鞍山現
Qt回憶錄之配置開發環境，qt回憶錄開發

Qt回憶錄之配置開發環境，qt回憶錄開發　　光陰荏苒，用Qt
LeetCode 第一題，Two Sum

LeetCode 第一題，Two Sum 今天早上起來去
POJ 1077 eight 拼圖游戲 BFS

描述： POJ 1077 3X3的方格中，其中8個格子
相關文章
閱讀排行榜
UVA11988 Broken Keyboard 鏈表 隊列的數組實現 中序線索二叉樹創建及其遍歷，序線索二叉樹 [C語言，c語言 C++裡的模板 題目1016: Prime Ring Problem 題目1165：字符串匹配 讀寫文件1——以字節為單位,讀寫文件（筆記實例） Qt--支持鼠標拖動來移動內容的QScrollArea視窗，qt--qscrollarea 01背包 HDU 2639，第K優解 詳細述說C++編譯環境
熱門圖文
MSChart圖表控件的一些使用 Rails開發細節（五）Migrations 數據遷移 Delphi面向對象的編程方法 帶有中文的字符串各個字符的獲取c++程序 Python中用於計算對數的log()方法 C#實現匈牙利算法 地統計 克裡格-地統計克裡格插值如何驗證二階平穩假設？ 精進不休 .NET 4.0 (5) - C# 4.0 新特性之並行運算(Parallel)
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved