Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

A DNA sequence or genetic sequence is a succession of letters representing the primary structure of a real or hypothetical DNA molecule or strand, with the capacity to carry information. The possible letters are A, C, G, and T, representing the four nucleotide subunits of a DNA strand: adenine, cytosine, guanine and thymine bases covalently linked to phospho-backbone.

DNA sequences undergo mutations during the evolution of species, which means that some letters are randomly replaced with others. Therefore, the DNA sequences of two closely related species are very similar, and the difference increases as the distance between the species increases. The mutations do not occur with uniform frequency throughout the sequence; typically there are fewer mutations at the biologically important parts, since even a single mutation can be lethal at such a place. On the other hand, if a part of the sequence does not carry any biologically relevant information, then mutations on this part have no effect. It follows that if we compare the DNA sequences of two species and a particular region of the sequence contains fewer than the average number of mutations, then most probably this part of the sequence plays an important biological role. Therefore, it is of crucial importance to identify such regions. More precisely, a conserved region is a consecutive interval of the DNA sequence such that in this region at most p percent of the letters are different in the two sequences. Your task is to write a program that, given two DNA sequences, finds the longest conserved region.

Input 

The input contains several blocks of test cases. Each case begins with a line containing two integers: 1n150000 , the length of the genetic sequences and 1p99 , the maximum percentage of mutated letters allowed in a conserved region. This is followed by two lines, each containing a DNA sequence of length n . The sequence contains only the letters `A', `C', `G', and `T'.

The input is terminated by a test case with n = 0 .

Output 

For each test case, you have to output a line containing a single integer: the length of the longest conserved region between the two sequences. If there are no conserved regions in the input, then output `No solution.' (without quotes).

Sample Input 

14 25
ACCGGTAACGTGAA
ACTGGATACGTAAA
14 24
ACCGGTAACGTGAA
ACTGGATACGTAAA
8 1
AAAAAAAA
CCCCCCCC
8 33
AAACAAAA
CCCCCCCC 
0 0

Sample Output 

8
7
No solution.
1

---

題目意思：
給定兩個字串，然後同時挑同一個區間 [l, r]，其不同的字元最多占有 p%。

解法：
知道最大平均值問題後，這題就很好下手了。
首先最大平均值問題是要找某個區間平均值最高為多少，而規定其區間長度至少 L。

藉此我們可以利用二分搜尋這個長度 L，然後調用上方的問題，得到其平均值，然後判斷二分。

總效率是 O(nlogn)

另一個解法：
將 C[i] = (A[i] == B[i]), 之後將 C[i] -= p%, 之後找最長連續和大於零。
效率也是 O(nlogn)

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
double get_avg(int l, int r, int sum[]) {
    return (double)(sum[r]-sum[l])/(r-l);
}
int q[150005], sum[150005];
double globalCut;
int nextL;
double mxAvgProblem(int n, int L, int sum[]) {
    double ans = (double)sum[n]/n;
    int front, rear, i, j;
    front = 0, rear = -1;
    for(i = L; i <= n; i++) {
        int tmp = i-L;
        while(front < rear && get_avg(q[rear], tmp, sum) <= get_avg(q[rear-1], q[rear], sum))
            rear--;
        q[++rear] = tmp;
        while(front < rear && get_avg(q[front], i, sum) <= get_avg(q[front+1], i, sum))
            front++;
        double tans = get_avg(q[front], i, sum);
        if(tans > ans)
            ans = tans;
        if(ans >= globalCut) {
            nextL = i-q[front];
            return ans;
        }
    }
    return ans;
}
int main() {
    int n, p;
    int i, j;
    char A[150005], B[150005];
    while(scanf("%d %d", &n, &p) == 2) {
        if(n == 0)  break;
        scanf("%s %s", A+1, B+1);
        double s = (100-p)/100.0, f;
        for(i = 1; i <= n; i++)
            sum[i] = sum[i-1] + (A[i] == B[i]);
        int l = 0, r = n, m;
        int ret = 0;
        globalCut = s;
        while(l <= r) {
            m = (l+r)/2;
            f = mxAvgProblem(n, m, sum);
            if(f >= s)
                l = nextL+1, ret = max(ret, nextL);
            else
                r = m-1;
        }
        if(ret)
            printf("%d\n", ret);
        else
            puts("No solution.");
    }
    return 0;
}