105上 校內賽

題目連結：goo.gl/DJUL8c   [好像用Google直接看會爛掉，建議下載下來，這裡是pdf檔]
我的code連結：goo.gl/n0g2Bo

我的code基本上都是  解法(1) 的做法(也就是我在賽中的寫法)

pA :
基本上開一個陣列維護'a' ~ 'z'出現多少個，之後再判斷是否符合相對應的條件即可。

時間複雜度：O(N)

pB :
開一個dp陣列dp[k][i][j]，代表說轉換了k次後，前i個中，最後是j，最多可以和幾個數字一樣。

那，先預設dp[0][0][0] = 0，
遞迴式可以寫成：dp[k][i][j] = max(dp[k][i-1][j],dp[k-1][i-1][1-j]) + (a[i] == j);

最後尋找長度是i所有符合答案中的max即可

時間複雜度：O(NK)

pC :
先隨便拿一個點作為root，
然後對於在dfs的時候，要維護兩個值：子樹中size最大的 & 自己+所有子樹的size，那，在尋找答案的時候，只要檢查 max(mx, n-sz) <= n/k 即可。作法有點類似 樹重心 。

時間複雜度：O(N)

pD :
基本想法就是，我們要記錄離某個點i中最近的j(a[j]%2==1)，然後用線段樹認真query就好啦。但是，如果要加1 or 拔掉1呢？

那我們就必須知道離這個點最近左右兩邊的1，這個部份我用線段樹實作，點的直就是index，然後求max跟min。

得到這些資訊後，我們就可以認真維護一下了。

時間複雜度：O(Q lg N)

pE :
解法(1)：
枚舉aj，用線段樹查詢適合的ai(1 ~ j-1最小值),ak(j+1 ~ n的最大值)。

時間複雜度：O(N lgN)

解法(2)
做前綴和 & 後綴和 的時候，維護好最小值，認真查詢一番。

時間複雜度：O(N)

pF :
基本上，先開一個dp表格：dp[k][i]代表選了k個後，最後是i的max是多少。

那，dp[k][i] = max(dp[k-1][j] + abs(a[j] - a[i]) ) for j in range(1,i-1)。

如果直接硬做的話，會導致O(KN^2)，那，要怎麼改進呢？

解法(1) ：
把dp[k-1][j]做成treap，其中key值是a[j]，那，再存val的時候，我就可以分兩種：a[j]是正的和a[j]是負的。之後再搜尋的時候，一直用treap維護即可，就可以把 O(N)的查詢時間壓到O(lgN)

時間複雜度：O(NK lgN )

解法(2) ：
先有一個想法：如果a<n> = <1,2,3>，那其實K=2跟K=3的解其實是一樣的。所以變成說，我們要求的數字，其實符合一大一小一大一小。基於這個性質，我們就可以用O(1)的時間最大最小值是多少了(稍微認真維護一下，應該okay)。

時間複雜度：O(NK)