UVA 3716 DNA Regions ( Math )

ACM-ICPC Live Archive

題意：
給兩個字串 A 和 B，你要選擇一個 [ L, R ] 使得所有滿足 L ≤ x ≤ R 的 x 都滿足 A[ x ] ≠ B[ x ] 的比率佔長度的 p% 以下。求最長長度。

資料規模：
N ≤ 1.5e5

解法：
考慮對 A[ x ] ≠ B[ x ] 先做前綴和，令前 x 個字符裡相異的字符數為 pfx[ x ]。所求即是滿足下列條件的 j 和 i 的最大差：

遇到這種式子就要直覺將 i 和 j 獨立出來：

就會發現只要按照這個由小到大排序，就可以維護可以用的右界裡最大的值。

時間 / 空間複雜度：
O( N lg N ) / O( N )

#include <bits/stdc++.h>
using namespace std;

signed main(){
  ios::sync_with_stdio( 0 );
  int N, P;
  while( cin >> N >> P and N + P ){
    string A, B; cin >> A >> B;
    vector< int > pfx( A.size() + 1 );
    for( int i = 0; i < A.size(); ++i ){
      pfx[ i + 1 ] = pfx[ i ] + ( A[ i ] != B[ i ] );
    }
    int max_len = 0;
    vector< pair< int, int > > trait( A.size() + 1 );
    for( int i = 0; i <= A.size(); ++i ){
      trait[ i ] = make_pair( 100 * pfx[ i ] - P * i, - i );
    }
    sort( trait.begin(), trait.end() );
    for( int i = 0, max_R = 0; i < trait.size(); ++i ){
      max_len = max( max_len, max_R - ( - trait[ i ].second ) );
      max_R = max( max_R, - trait[ i ].second );
    }
    if( max_len == 0 ){
      cout << "No solution.\n";
    } else{
      cout << max_len << "\n";
    }
  }
  return 0;
}