2016年10月1日 星期六

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)



沒有留言:

張貼留言