CFR 786 C. Till I Collapse ( Math, Sqrt Dcmp, Divide and Conquer )
題意:
給一個長度為 N 的陣列,用顏色描述。要求對於所有 K <- [ 1, N ] 輸出,分割成連續區間,使得每個區間不超過 K 個顏色,最少的區間數量。
資料規模:
N ≤ 1e5
解法:
據說這可以用資料結構 ( 樹狀數組 ) 直接做掉,但我看不懂。
首先答案一定是非嚴格遞減的。
這題的重點在於看透一個結論:「答案的種類大約在 N^0.5 級別」。
原因是,當 K ≤ N^0.5 時, 至多有 N^0.5 種答案。但當 K > N^0.5 時,由於一個區間至少可以涵蓋 N^0.5 這麼長的區間,因此最多的最少區間數量至多也是 N^0.5。
有了這個結論後,可以做一種很特別的剪枝的分治法。
剪枝的方法是這樣的:若當前左界和右界的答案是相同的,那麼直接將這個區間都劃記為該答案,並立刻結束這個區間的計算。否則,計算中間的答案,並分治為兩個規模相同的子問題。計算答案的部分用爬行法線性處理即可。由於計算答案的次數至多為答案種類的數量,一次計算的花費至多為 O( N ),所以可以得出這個做法的複雜度為 O( N^1.5 )。
時間 / 空間複雜度:
O( N^1.5 ) / O( N )
#include <bits/stdc++.h> using namespace std; const int MAXN = ( int ) 1e5; int N; int A[ MAXN ]; int ans[ MAXN + 1 ]; int calc( int k ){ static vector< int > cnt( MAXN + 1 ); int res = 0; for( int i = 0; i < N; ){ ++res; int j = i; int f = 0; while( j < N and f <= k ){ if( f == k and cnt[ A[ j ] ] == 0 ) break; f += ++cnt[ A[ j++ ] ] == 1; } while( i < j ){ --cnt[ A[ i++ ] ]; } } return res; } void dvcq( int lb, int rb ){ // ( lb, rb ) if( rb - lb < 2 ) return; if( ans[ lb ] == ans[ rb ] ){ for( int i = lb + 1; i < rb; ++i ){ ans[ i ] = ans[ lb ]; } return; } int mid = lb + rb >> 1; ans[ mid ] = calc( mid ); dvcq( lb, mid ); dvcq( mid, rb ); } signed main(){ ios::sync_with_stdio( 0 ); { // input cin >> N; for( int i = 0; i < N; ++i ){ cin >> A[ i ]; } } { ans[ 1 ] = calc( 1 ); ans[ N ] = calc( N ); dvcq( 1, N ); } { for( int i = 1; i <= N; ++i ){ cout << ans[ i ] << " \n"[ i == N ]; } } return 0; }