UVA 3716 DNA Regions ( Math )
題意:
給兩個字串 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; }