2012年6月17日 星期日

tioj 1699 Problem I 害蟲決戰時刻

shik送我的生日快樂題 >/////////<
很有趣很困難很好玩
其實核心概念只有一個:
若一個區段要 > 1/k,
那『不可以』裁切後的每一個區段都 < 1/k
換句話說,就是對於裁切後的每一個區段,都最多只要看最大的 k 種即可
我的作法:
1. 預處理-
       Seg_tree: O( nlogn ) + O( n (logn+1) logn )      
       Vector: O(n)
2. 每次詢問-
         找出可以切成Seg_tree的哪些點( O( logn ))
                        乘上
對於每個點(logn):看最大的K種( K ) * 二分區間內數量( logn )

總時間複雜度:O( n(logn)^2+sumK(logn)^2 )

code: http://codepad.org/4QB0Eaav

2012年6月13日 星期三

tioj 1674 新專輯

對於 x > sqrt(n),至少有兩個數字除n得同一商

基於此,便可把原本的O(n)攤成『直接枚舉』O(sqrt(n)) + 『等差級數』O(sqrt(n))

以15為例:

--------(X15)
1: 0
--------(X7)
2: 1
--------(X5)
3: 0
--------(X3)
4: 3
5: 0
--------(X2)
6: 3
7: 1
--------(X1)
8: 7
9: 6
10: 5
11: 4
12: 3
13: 2
14: 1
15: 0

My code: http://codepad.org/QeDh2BXl

2012年6月5日 星期二

tioj 1401 功夫城堡

突然發現原來縱軸跟橫軸是獨立的

所以就分開來作啦

分開來就簡單很多了

sort過一遍,在配一個heap就可以了

code: http://codepad.org/uKdchYE4

2012年6月3日 星期日

tioj 1444 郵局設置問題

跟他的extreme版一點關係也沒有

這提示樹DP,O(N),O(N^2)不會過==

可是感覺明明就會阿,害我TLE

我是亂co的,很多地方還可以在更快

不過就算了~。。。

這提其實是2N,就是兩次DFS

記錄兩個東西,best跟second best,後面就亂暴力。

code: http://codepad.org/FENcFDlh

tioj 1449 郵局設置問題EXTREME

第50個解題報告,寫點好玩的東西

四邊形不等式

他是一個用來優化DP的一個好工具

DP有一些專用術語: tD / eD

子問題數目為O( n^t )個,每個子問題要依賴於 O( n^e )個子問題

總時間複雜度是O( n^(t+e) )。

這裡碰到的是最常見的2D/1D優化-四邊形不等式-

通常2D/1D的遞移式長得像這樣:C( i, j ) = opt{ C( i, k-1 ) + C( k, j ) + w( i, j ) }

照理來說是O(n^3),但可以優化成為O(n^2)!!!

但有一個必要的條件,C[a,c]+C[b,d] <= C[a,d]+C[b,c](a<b<c<d)

當有了這個條件,便會產生一個可怕的定理:

若i, j 的最佳斷點為K[i][j],則 K[i][j-1]<=K[i][j]<=K[i+1][j]。

遞移式變成:C[i,j]=opt{ C[i,k-1] + C[k,j] } ( s[i,j-1] ≤ k ≤ s[i+1,j] )

複雜度:(s[2,L+1]-s[1,L])+(s[3,L+2]-s[2,L+1])…+(s[n-L+1,n] -s[nL,n-1])=s[n-L+1,n]-s[1,L] ≤ n


接下來就要來證明那個強大的定理。
為了方便書寫,定義:mk[ i, j ] = C[ i, k ]+C[ k, j ],K[ i, j ] = d。

目前擁有兩個關係:
(1) C[a,c]+C[b,d] <= C[a,d]+C[b,c]      和     (2) 若k<d,則C[ i, k ] + C[ k, j ] >= C[ i, d ]+C[ d, j ]

如果 當k<d,則 C[ i+1, k ] + C[ k, j ] >= C[ i+1, d ] + C[ d, j ] ,那 d <= K[ i+1 ][ j ] 成立。

因為C滿足四邊形不等式,那C[ i+1, k ]+C[ i, d ] ≥ C[ i+1, d ]+C[ i, k ](i<i+1<k<d)

-> ( C[ i+1, k ]+C[ i, d ] ) - ( C[ i+1, d ]+C[ i, k ] ) >= 0

-> ( C[ i+1, k ] + C[ k, j ] + C[ i, d ] + C[ d, j ] ) - ( C[ i+1, d ] + C[ d , j ] + C[ i, k ] + C[ k, j ]) >= 0

-> ( ( C[ i+1, k ]+C[ k, j ] )-( C[ i+1, d ] + C[ d , j ] ) )-( ( C[ i, k ]+C[ k, j ] )-(  C[ i, d ]+C[ d, j ] ) ) >= 0

-> ( C[ i+1, k ] + C[ k, j ] ) - ( C[ i+1, d ] + C[ d, j ] ) >= 0

-> C[ i+1, k ] + C[ k, j ] >= C[ i+1, d ] + C[ d, j ] ,QED。

同理可證,K[i][j-1] <= K[i][j],故 K[i][j-1]<=K[i][j]<=K[i+1][j]。

剛剛證的是普遍性的遞移式會符合,但平常碰到實質的題目,要自己重證一下比較好。

這提可以透過遞迴,以O(n^2)的時間複雜度求得對某區段中,設一郵局的最近距離和。
(定義為w[ i ][ j ] )

遞移式:w[ i ][ j ] = w[ i ][ j-1 ] + v[ j ] - v[ ( i + j ) / 2 ]

由這個遞移式就可以推得 w 符合凸四邊形不等式,且符合區域單調性。

所以C也符合四邊形不等式,所以就可以用那個優化變成O(n^2)。


code: http://codepad.org/LSfUIY9m