tioj 1134 1.蓋房子問題

爛題，時間複雜度跟預想不符＝＝

據說可以O(n^3)，但O(n^3lgn)就可以在時限內過了

害我想很久，爛題><

http://codepad.org/2NTZ93Va

tioj 1723 Monster Galaxy 「失敗紀念」

留作紀念～：http://codepad.org/iRWmIAiC

寫了好久還是TLE，可是應該也只超出去一點點

但卻不知道要怎麼再壓時間了，可惜～XP

我是用SA+LCP硬做的，實在是壓不成阿XD

tioj 1651 人生還是不停的戰鬥 (RPG-again-)

DP，沒了

http://codepad.org/e3jv9UQO

tioj 1321 好多回文 ndromePali

怎麼覺得字串題用Z function都可以輕鬆解決？

只是奇偶的差別有點複雜就是了，但基本上並不難

code: http://codepad.org/tQ6o7ACP

tioj 1634 然後我哥就起笑了

搞笑提XD

測資是有多少阿＝＝

跑這麼久...

我的想法有點像數學歸納法

如果在2^i之前可以做出 1 到 2^i-1的所有數字

那就可以把2^i的也全數放進去，就這樣。

code: http://codepad.org/GqzcIRk3

tioj 1725 Massacre at Camp Happy

並不是什麼很難的字串提，他只是Z algorithm的基礎應用

但我卻WA了很多次，主要原因在於我一開始的Z_Maker根本是錯的
（放心，我前一篇的code是對的，喔對了！我四月po的似曾相識code是有問題的，所以我才會再po了STRINGS CODE這一篇）

因為我是看著演算法筆記學習的，但事實上他的講法是有問題的

1. 啟始點不可為 0，因為你的z[0]已經設定過了，這樣會產生不可預期的錯誤（以他預設的L, R都是零的情況，應該可以改成不會錯，但沒這必要阿）

2. 在判斷一個後綴是否可能再繼續下去，也要把連最後一個也一樣的情況都要判斷進去，因為如果下一個又一樣，那他的LCP是有可能加長的（聽不懂我講的且是照著演算法筆記學的人，寫完這提後就會有深刻了解）

code: http://codepad.org/guqpPxPc

Strings CODE

這裡是奉上我的code的小地方～


MP: 就是上一篇的內容
（code: http://codepad.org/JhbPTUVc）


KMP: MP加上一個優化：若 b[ i + 1] 跟 b[f[i] + 1] 相同時，比對b[ i+1]失敗，可跳過 b[ f[i]+1 ]
（code: http://codepad.org/SLlkwDJR）


SA, RA: 這部份跟之前在似曾相似裡的東西一模一樣，但code寫的不清不楚的，所以重寫一份
（code: http://codepad.org/QFHlMA4F）

LCP: 就是包括求h[]以得height[]最後再用ST做出O(nlgn)-O(1)的RMQ
（code: http://codepad.org/7hPyaKjm）

第一次寫完一題字串提：tioj 1306
（code: http://codepad.org/e8ke7V1f）

如果有人可以的話，寫完這提後，希望可以借看一下code，感謝> <

tioj 1698 Problem H 神殿裡的觸手

這幾題中最簡單的吧！

沒有任何的陷阱跟怪東西

就是一個Kruskal+找bridge

code: http://codepad.org/O6a4XRME

tioj 1697 Problem G 古墨西哥密碼

奸詐的題目，時間卡好緊＝＝


題目特別解析：（普通解析可以看這裡XDD）

1. 找出 2L～2R 的質數表

2. 以1.的bool表建出一個有向圖（如果x then y成立，則由x連到y）

//簡單的部份到這裡為止

3. 這時你想要解的是：
            找出A～B，使得可以在剛剛的有向圖中以<=K條路徑覆蓋A~B所有點


4. 但你只會算『在一個有向圖中最少要幾條簡單路徑覆蓋所有點』
（這裡要使用的技巧是二分圖匹配，而要解決這個問題，只需要把每一個點拆成入點和出點即可且入點和出點無任何關係，以此做最大匹配(x)，所求的答案便是n-x，原因的話是因為沒有被匹配到的點，象徵著簡單路徑的終點（二分圖左半邊）和起點（二分圖右半邊））


5. 所以你便想用枚舉的方式，但發現時間複雜度O(V*V*V*E)，TLE。這時，你發現可以用雙指針，而且可以將他放入二分圖匹配的步驟之中，瞬間將時間複雜度將為O(V*E)。


6. 最重要的一件事！在Bipartite的時候要從G[p].size()-1~0，不能反過來喔，原因應該跟機率有關，不討論了，但極重要，不這樣寫100%TLE。




code: http://codepad.org/a7gksiSK

tioj 1694 Problem D 你的重生之旅

我真的很喜歡ABCLS的題目XD

雖然code很長，而且我寫了超久（+ debug）

我開了四個重要的陣列，a, b, c, d

a[i]: 第 1 ~ i 塊自己的逆序數對和（nlgn）

b[i][j]: 第 i 個對第 1~j 塊的逆序數對和（n*sqrt(n) -> 要想一下）

c[i][j]: sigma( k = 1 ~ i )第 k 塊對第 k+1~j 塊的逆序數對和（n*sqrt(n)）

d[0][i]: 第 i 個對自己所屬的塊中的右邊的逆序數對（n*sqrt(n)）

d[1][i]: 第 i 個對自己所屬的塊中的左邊的逆序數對（n*sqrt(n)）

For every query:

用 a 和 b 做出完全包住 『所問的範圍』 的方塊的逆序數對數量O(1)

用 c 和 d 扣掉多出來不在『所問的範圍』的那些逆序數對 O(sqrt(n))

再用神祕的方法O(L) sort 兩坨多出來的，並將他們的逆序數對數加回來O(sqrt(n))

最重要的是，每一塊的數量！

由於我寫的code使得時間複雜度為 

T( 5Qx + 4n^2/x + nlgx + n + 0.5*(n^2) / (x^2) )（x為每一塊的數量）

有些不重要可以劃掉 -> T( 5Qx + 4n^2/x )要最小，用算幾不等式

可以得到想要最小時， x = sqrt( 4/5 ) * n / sqrt( q )

code: http://codepad.org/Q1v7RMu8

tioj 1624 快樂設置道路

重新見識到我的debug功力之爛＋＋

爛到透光了，一切敗在sort的位置中

其實就三維DP啦，不是很重要的題目

寫這篇是要說，當把東西移掉時，要記得全部都改
（頭腦要清楚才行）

code: http://codepad.org/NACX8veI

tioj 1493 三個農夫

按時間戳記做出一個BIT

剩下就只是些很麻煩的判斷

1. 兩個規則

2. 不能刪超過

code: http://codepad.org/6omTGYug

tioj 1637 我愛台灣

維持stack嚴格遞減?!

看想法啦，而且東西都丟在stack裡好像記憶體變很小

預估有6000K，但出來只有28K

code: http://codepad.org/Ey9tiX3a

tioj 1443 遞迴問題

說真的，好久沒寫程式了，一直努力怕被當的說> <

終於暑假了，今天寫了不錯的怪題?!

這題其實就是給 n ，問 lg(n+1) 的整數部分
（這部份我是印出一大堆東西後判斷出來的）

本來一直怕會有誤差（n大約是100000位吧）

所以寫別的作法，如大數之類的，但100%超時＝＝

最後決定亂寫，直接用換底XD ((居然沒有以二為底的log OoO


code: http://codepad.org/cFB4BO4y

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

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

tioj 1401 功夫城堡

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

所以就分開來作啦

分開來就簡單很多了

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

code: http://codepad.org/uKdchYE4

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

tioj 1137 4.收費站設置問題

其實我本來看不懂題目的＝＝


敘述有點怪怪的+ +


後來原來是要叫我們找AP


就用，dfn 跟 low一次解決


最下面的點：不行（不是會產生迴圈就是沒有下面的節點）


中間的點：如果有子節點可以走到上面不行（會產生迴圈）


最上面的點：如果只有一顆子樹不行（就跟最下面的點一樣）


SO::


若沒有子節點-> 不行


若全部子節點都走到上面-> 不行


若為root且子樹少於2 -> 不行




code: http://codepad.org/FOPjxS0v