點我連到官方 Editorial
比完這場我有一個關於閱讀題目的小感想：當題目敘述裡面出現我沒見過的名字時(如：Tavas、Karafs)，會使我讀題目讀得很不順，每看到那些名字就會卡一下...
Problem A --- Tavas and Karafs
題意：有一個無限長的等差數列，首項為 $A$，公差為 $B$。共有 $n$ 組詢問，每組詢問包含三個正整數 $l, t, m$ 。對於每個詢問，請找出最大的 $r$，使得我們能執行至多 $t$ 次中括號內操作 --- [ 在數列裡把至多 $m$ 個相異數減 $1$ ]，使得數列第 $l$ 至第 $r$ 個數都不超過 $0$。
數據範圍：$1 \leq A, B \leq 10^6$ ， $1 \leq n \leq 10^5$
tag：[ 貪心 ] [數學]
關鍵字：度序列= = = = = = = = = = = = = = =
引理：無論是否為等差序列，一個序列 $h_1, h_2, ... , h_n$ 能滿足題目的條件的衝要條件為：$\max (h_1, h_2, ... , h_n) \leq t$ 以及 $\sum{h_i} \leq m * t$。
由於對於任意詢問，若把 index $x$ 選為右界能滿足題目條件，則對於所有 index $i$ 滿足 $l \leq i \leq x$，也一定能滿足條件。所以就可以使用 binary search 了。
數據範圍有特別設計，讓你 binary search 時的運算不會超過 long long，不過你還是得小心一點，binary search 時的右界不能設太大。
關於這個引理的證明，可以使用數學歸納法，請直接參考 tutorial 吧。
我覺得這題的概念和簡單二分圗的度序列判別很像，證明也很像。我們可以把引理的問題想像成這樣：
有一個二分圗，已知二分圗其中一邊有 $t$ 個點，每個點的度數 (degree) 都是 $m$；令一邊則有 $n + m*t - \sum{h_i}$ 個點，當中的 $n$ 個點度數分別是 $h_1 \sim h_n$ ，剩下的點度數都是 $1$。而這樣的圗會是簡單圗的充要條件就是 $\max (h_1, h_2, ... , h_n) \leq t$。
給定二分圗或一般圗的度序列問是否否存在一個簡單圗滿足這樣的度序列，是可以很有效率解決的問題，有興趣的話可以 google 看看可參考 wiki：degree sequence、Havel - Hakimi algorithm。
二分圗度序列判定的題目：CEOI 2010 Bodyguards
Problem B --- Tavas and Malekas
題意：有兩個字串 $s$ 和 $p$ ，已知 $s$ 字串的 index $y_1$ , $y_2$ , ... , $y_m$ 開始長度和 $p$ 字串一樣長的 substring 和 $p$ 一樣 (有可能還有其他一樣的位置，不一定全列給你)，問 $s$ 有多少種可能？
數據範圍：字串長度皆不超過 $10^6$。
tag： [ 字串比對 ]
= = = = = = = = = = = = = = =這題就只是個字串比對的練習題，我覺得沒有比較特別的地方。
除了某些位置的字母題目已給定，其他位置都可以'a' ~ 'z' 隨便填，答案會是 $26^K$，$K$ 是無法從題目得知字元是什麼的位置數。
所以這題的解題分成兩部分： 1. 快速的填入所有已知的位置 (要填下一個子字串時，直接忽略已經填過字母的位置) 2. 重新驗證所有 $y_i$ 開始的子字串是否和 $p$ 一樣，這部分可以用任意字串比對的方法做到。
Problem C --- Tavas and Pashmaks
題意：有一個競賽包含游泳 $x$ 距離和跑步 $y$ 距離，有 $n$ 位參賽者，給定這 $n$ 位參賽者的泳速和跑步速度，請問在我們不知道 $x$ 和 $y$ 的實際值的狀況下，有哪些人可能第一名 (和其他人同時到達算是並列第一)，輸出請按照所有人的邊號輸出。
數據範圍： $1 \leq n \leq 10^5$，所有速度為不大於 $10^4$ 的正整數。
tag：[ 計算幾合 ]
關鍵字：三項鐵人
= = = = = = = = = = = = = = =這題...我以前見過更複雜的版本(POJ 1755 Triathlon，有三項運動，可以輕鬆搜到一堆題解)，兩項運動的也有見過其他類題但找不到了。我想這題題解講的非常仔細我就不說了。
是說賽中我想都沒想，只憑記憶覺得似乎和凸包有關，就亂猜了一個做法結果 WA 了 OAQ。
Problem D --- Tavas in Kansas
題意：有一個無向圗，每個點有一個整數權重， Tavas 和 Nafas 用這個圖玩一個遊戲。Tavas位於 $s$ ， Nafas 位於 $v$。遊戲如下：兩人輪流， Tavas 先，輪到的人要選一個值 $x$，並標記所有與自己的點距離不超過 $x$ 且尚未標記的點，並獲得所標記的所有點的權重和當做分數，至少要標記一個點。直到所有點都被標記後遊戲結束。在所有人採最佳策略下，誰會嬴(或平手)。
數據範圍：圖的點數不超過 $2000$，邊數不超過 $10^5$，圖是連通的。點的權重絕對值不超過 $10^9$。
tag： [ 最短路 ] [ dp ]
= = = = = = = = = = = = = = =這題的圖啊根本是多餘資訊，我們只要保留每個點的到 $s$ 、 $t$ 的最短路距離的值就夠了，把這些距離離散化後，就可以開二為記憶體來 dp 。最直覺得 dp 是 O(n^3)，當可以改進成 O(n^2)，細節請參考官方 Editorial 吧，還蠻詳細的。
我有一個建議：當不知道要怎麼改進複雜度時，把 dp 時的轉移式寫下來用眼睛觀察可能就嘿知道要怎麼改進了。(雖然說這題我讀完題就知道怎麼改進複雜度了，但最後有些地方要開 long long但我只用 int 就爆炸了 OAQ。)
Problem E --- Tavas on the Path
題意：給一個樹，每個邊都有個值。定義一個 fuction $T$，input 為一個 01 字串 $s$，$s$ 有 $m$ 個連續的 $1$ 的區塊，第 $i$ 個區塊有 $e_i$ 個 $1$，則 T 的 output 為 $\sum_i{f_{e_i}}$ ($f_i$ 是給定的值)。現在有 $q$ 個 query，每個 query包含三個樹 $v, u, l$，請回答兩端點為 $v, u$ 的路徑上，若邊的值 $\geq l$ 則視為 '1'，否則視為 '0'，把這些字元按照路徑上的順序接起來，代入 function $T$，請輸出 output。
數據範圍：$1 \leq q \leq 10^5$，$2 \leq n \leq 10^5$，$| f_i | \leq 1000$，$1 \leq$ 邊的長度 $\leq 10^9$。
關鍵字：[ 樹鍊剖分 ]
= = = = = = = = = = = = = = =這題看完大概就知道他是樹鍊剖分的題目，英文叫做 heavy-light decomposition。請 google 可以查到非常多資訊。
簡單來說，就是把 tree 拆成很多 path，讓每個詢問都只會通過 O( log n ) 個 path，並在每個 path 上用線段樹解決部分問題。也就是說，你如果會用線段樹解決 Tree 退化成 Path 的狀況，就可以用樹鍊剖分來多一個 $log$ $n$ 解決問題了。細節請參考官方 Editorial。
沒有留言:
張貼留言