雖然我說這場偏簡單，但因為我英文太差加上我太輕視題目，把 D 的解的輸出方式搞錯，最後與第二名擦身而過 OAQ
點我連到官方 Editorial
Problem A --- DNA Alignments
題意：給一個由 ACGT 四個字母組成的字串 $s$，請問有多少同樣長度字串 $t$，使得 $p(s,t)$ 最大。令 $q(s,t,i)$ 為把 $t$ 的 前 $i$ 個字母移到最後面後，和 $s$ 同位置是相同字母的個數，則 $p(s,t) = \sum_{i=0}^{n-1}{q(s,t,i)}$。答案請 mod $10^9+7$
數據範圍：字串長度不超過 $10^5$
tag：[ 數學 ][ 貪心 ]
= = = = = = = = = = = = = = = = = = = =
$p(s,t)$ 其實就是兩個字串的字母頻率向量的内積。何謂字母頻率向量？假設共有 $k$ 個字母，那字母頻率向量就有 $k$ 維，且第 $i$ 維的值就是第 $i$ 個字母出現的次數。何謂向量？請去翻高中課本 >_<
於是此問題就變成，給定一個四維向量 $v$，請找一個各維度和為 $n$ 的向量使得兩項量內積最大。這問題看起來很 greedy 對吧？只要把數字都加在 $v$ 中數值最大的那些維度就可以了(證明略)。所以值最大的維度若有 $r$ 個，答案就是 $r^n$。
Problem B --- Cube
題意：在平面上有 $n$ 個穩定的點。一個點 $(x, y)$ 若是穩定的，有兩種可能：(1) $y$ 座標為 $0$。 (2) $(x-1, y-1), (x, y-1), or (x+1, y-1)$ 也存在點。現在我們要把所有點拔掉，一次只能拔一個，並且拔的過程中，所有點仍是穩定的。為了把題目變難一點，我們把他變成兩人遊戲，把所有可能的操作對應到一個 $n$ 位數的 $n$ 進位數，由位數高到位數低依序代表點的編號先拔到後拔，先手會希望對應到的數字愈大愈好，後手則希望對應到的數字愈小愈好。他們都很聰明，請輸出答案 mod $10^9 + 9$。
數據範圍：所點 $xy$ 座標絕對值不超過 $19^9$，且 $y$ 座標非負。 $1 \leq n \leq 10^5$。
tag： [ 圖論 ] [ 貪心 ]
= = = = = = = = = = = = = = = = = = = =
這題一看完就覺得很greedy，算是資料結構模擬題吧，輪到先手是就拔所有可以拔的點中編號最大的，後手則拔可以拔的點中編號最小的，每次拔完只要檢查附近的點可不可以拔的狀態有沒有改變。
說是這樣說，可是寫起來其實挺麻煩的，並需儲存很多資訊，對 STL 地使用不熟悉的會感到很苦手吧。
是說最近拔點的題目也太多了...
是說最近拔點的題目也太多了...
Problem C --- Pluses everywhere
題意：給一個可以有很多 $0$ 開頭的 $n$ 位數，請把所有在當中插入 $k$ 個加號的運算式的結果加起來。
數據範圍：$0 \leq k \lt n$
tag：[ 數學 ]
= = = = = = = = = = = = = = = = = = = =
就只是個數學題，切入點就是考慮原始數字的每個位數，在所有可能的運算式中，會被當作 $i$ 位數幾次。
要解這題，首先你一定要會經過 O(n) 預處理後，O(1) 算出 $C^i_j$ 的值($0 \leq i \leq n)。我這裡就不解釋怎麼做了 0.0。會做這個後，再考慮我前面所說的切入點，會發現可以 O(n^2) 算出答案，但這樣還不夠快。所以我們就要想辦法省略一些計算。幸運的是，在算每個數字貢獻的和的時候，我們會發現他們的公式很像！已知某個位數貢獻的值，就可以 O(1) 算出相鄰的位數貢獻的值。所以整題的複雜度是 O(n)。
這類的題目其實蠻多的，雖然樸素加總很花時間，但實際上有很多重複的運算可以省略。所以這題我也是一看到題目就知道解題方向了
Problem D --- Shop
題意：有 $k$ 個數 $a_1$ 至 $a_k$，你有 $n$ 種可能操作，每個操作都有兩個數字 $i$ 和 $b$。操作有三種類型，第一種：把第 $i$ 個數字改成 $b$。第二種：把第 $i$ 個數字加上 $b$。第三種：把第 $i$ 個數字乘以 $b$。請在當中選至多 $m$ 個操作，執行順序任意，使得所有操作結束後，所有數字的乘積最大。並構造出一組解。
數據範圍： $1 \leq a_i \leq 10^6$，$0 \leq m \leq n \leq 10^5$。
tag：[ 貪心 ]
= = = = = = = = = = = = = = = = = = = =
首先你會發現，最好的操作方式一定是選了某些操作後，先執行第一種的所有選到的操作，在執行第二種的所有選到的操作，最後在執行第三種的所有選到的操作，證明略。
接下來我們就要比較選哪些操作比較好啦，是否能有個直接比較的基準呢？先想像若只有第三種操作，我們就不需要考慮 $i$，只要單純的比較 $b$ 的大小就好了，這是最簡單的。若只考慮第二種操作的話呢？首先可以發現，若 $i$ 相同，當然是 $b$ 愈大預先取。但 $i$ 若不同呢？我們就得把 $a_i$ 的值也考慮進去，於是會發現，若原本是 x，加上 $b$ 後會變成 $(x+b)/x$ 倍！而且我們已經知道對於同一個 $i$，若要使用某個操作，一定會把所有相同 $i$ 中 $b$ 比該操作大的操作先執行完。於是我們就能算出使用該操作之前的 $a_i$ 的值了。所以每個第二種操作，我們都可以把他等價於乘以某個值的操作，而且這樣就可以和第三種操作做比較了！
這題最困難的部分就是，要如何把第一種操作和第二種操作混合考慮。
其實若只有第一種和第三種，做法也和只有第二種和第三種類似，因為對於第一類操作中相同 $i$ 的操作，我們至多選一個，且一定是選 $b$ 值最大的那個，由於我們是在最初時就採用第一種操作，所以我們也可以把他等價於，乘以某個定值。
現在正式來把第一種和第二種操作一起考慮。我們會發現若第一種操作的 $b$ 值為 $b_1$，第二種操作的 $b$ 值為 $b_2$，若 $b1 - a_i > b_2$ 這第一種操作的優先度會比較高，否則就是第二種操作的優先度比較高！於是，我們實際上可以把第一種操作的一組 $(i, b)$，當成是第二種操作的 $(i, b - a_i)$ (請仔細體會這句話的涵義)，於是我們就把他轉換成只有第二種和第三種操作的 case 了。
直接舉個例子，假設測資如下：
1 2 5
2
1 1 3 ---(1)
1 1 4 ---(2)
2 1 1 ---(3)
2 1 3 ---(4)
3 1 2 ---(5)
首先，第一種操作我們只需要考慮 $b$ 最大的那個，於是可以把 (1) 捨棄，現在剩下：
1 1 4 ---(2)
2 1 1 ---(3)
2 1 3 ---(4)
3 1 2 ---(5)
接著，我們把(2)當成第二種操作來用，原本的 $b$ 是 $4$，減掉 $a_i$ 後變為剩下 $2$，這群操作變成：
2 1 2 ---(2)
2 1 1 ---(3)
2 1 3 ---(4)
3 1 2 ---(5)
最後，若尚未執行任何操作，$a_1$ 是 $2$，若有執行第二類操作，會優先選 (4)，由 $2$ 變成 $5$ 是變成 $2.5$ 倍，於是 (4) 會等價於 $3 1 2.5$，現在操作群變成：
2 1 2 ---(2)
2 1 1 ---(3)
3 1 2.5 ---(4)
3 1 2 ---(5)
接著考慮 (2)，由於若選 (2)，一定有選 (4)，故執行 (2) 之前 $a_i$ 的值會是 $5$，執行完後變成 $7$，等價於乘以 $7/5$。最後把 (3) 也如法炮製，最後變成如下：
3 1 7/5 ---(2)
3 1 8/7 ---(3)
3 1 2.5 ---(4)
3 1 2 ---(5)
於是就可以簡單的 greedy 了！
這題時做上有蠻多地方可能寫錯的，例如說，在比較兩分數的大小，若直接分子乘對方分母去比較，會超過 long long，我的 AC code 是直接轉型成 long double 來比較。不過這不是我賽內錯的地方，我賽內錯的地方是，我操作編號直接由小到大輸出 = =，但應該要按照編號的種類輸出 ...因為我在看 output format 時讀入我腦內的是，請把用到的操作的編號由小到大輸出，因為我只去看 output format 的最後一行："in the order in which they appear in the input"，我每次讀題目都太隨便了 OAQ
Problem E --- Cycling City
題意：給一個 $n$個點 $m$條編的簡單無向圖，請給出 $3$ 條點起點和終點相同的簡單路徑，使得這三條簡單路徑，除了起點終點以外，沒有任何共用點。
數據範圍：$1 \leq n,m \leq 10^5$
tag：[ 圖論 ] [ 三連通 ]
= = = = = = = = = = = = = = = = = = = =
若把找 $3$ 條簡單路徑改成找兩條的話，就是個普通 BCC 問題。但如果是三條呢？等著看 Editorial 吧＠＠
看完 Editorial 後，發現我原本根本理解錯題目了 ... 由於我英文很差，所以往往會自動把看讀到的東西去 match 到我比較熟悉的東西，所以就理解錯啦，理解成起點和終點有固定在 $1$ 和 $n$，其實若有仔細看 Sample 就知道絕對不是這樣嘛 = = (現在上面的題意已更正)
如果起點鐘點可以任意選定的話，要怎麼做呢？或許會有個直覺 --- 完全不存在這樣的三條 path 若且唯若此張圖是仙人掌(Cactus)！所謂的仙人掌就是每個雙連通元件都是單獨一條編或單獨一個 cycle 的圗。雖然我說是直覺，可是其實我直接被 Editorial 捏答案了，至少我看完解答後覺得很直覺啦！若是仙人掌，則一定沒有這樣的三條 path是容易證的，另外一個方向的證明稍為難一點，以下稍為題一下證明的輪廓 (同時也能找到一組答案)：
若對 BCC 熟悉的人就會知道，這三條 path 一定是在 BCC 的同一個連通元件裡。現在我們要試圖在一個不是單獨一條邊也不是單獨一個 cycle 的連通元件內找這樣的三條 path。
步驟一：在此連通元件中找到任意一個 cycle。
步驟二：在這個cycle上找到一個有連出不在 cycle 上的邊(記做 $e$)的點(記做 $x$)。(想想看為什麼一定找的到？)
步驟三：從該點延著 $e$ 找到一個簡單 path 又走回原本的 cycle 上非 $x$ 的點 $y$(此 path 只和 cycle交於 $x$ 和 $y$)。 (想想看為什麼一定走的回來？)
於是步驟三找到的 path，以及 $x$ 和 $y$ 把原本的 cycle 切出來的兩條 paths 合起來就是此題所要的一組答案了！我想證明應該不難吧？而且我怎麼印象這個問題在台大的張振華教授所開得圗論課裡面有提到 @@。
看完 Editorial 後，發現我原本根本理解錯題目了 ... 由於我英文很差，所以往往會自動把看讀到的東西去 match 到我比較熟悉的東西，所以就理解錯啦，理解成起點和終點有固定在 $1$ 和 $n$，其實若有仔細看 Sample 就知道絕對不是這樣嘛 = = (現在上面的題意已更正)
如果起點鐘點可以任意選定的話，要怎麼做呢？或許會有個直覺 --- 完全不存在這樣的三條 path 若且唯若此張圖是仙人掌(Cactus)！所謂的仙人掌就是每個雙連通元件都是單獨一條編或單獨一個 cycle 的圗。雖然我說是直覺，可是其實我直接被 Editorial 捏答案了，至少我看完解答後覺得很直覺啦！若是仙人掌，則一定沒有這樣的三條 path是容易證的，另外一個方向的證明稍為難一點，以下稍為題一下證明的輪廓 (同時也能找到一組答案)：
若對 BCC 熟悉的人就會知道，這三條 path 一定是在 BCC 的同一個連通元件裡。現在我們要試圖在一個不是單獨一條邊也不是單獨一個 cycle 的連通元件內找這樣的三條 path。
步驟一：在此連通元件中找到任意一個 cycle。
步驟二：在這個cycle上找到一個有連出不在 cycle 上的邊(記做 $e$)的點(記做 $x$)。(想想看為什麼一定找的到？)
步驟三：從該點延著 $e$ 找到一個簡單 path 又走回原本的 cycle 上非 $x$ 的點 $y$(此 path 只和 cycle交於 $x$ 和 $y$)。 (想想看為什麼一定走的回來？)
於是步驟三找到的 path，以及 $x$ 和 $y$ 把原本的 cycle 切出來的兩條 paths 合起來就是此題所要的一組答案了！我想證明應該不難吧？而且我怎麼印象這個問題在台大的張振華教授所開得圗論課裡面有提到 @@。
沒有留言:
張貼留言