SRM648

這場 SRM 雖然我拿了 -25 分...但還是照寫題解XD
都怪我一剛開始 850 想歪，並且剩 25 分鐘時才去開 550，剩一分多鐘才把 code 寫完而且沒能de 到某個蠢 bug @@

250 --- AB

題意：請構造出一個由 A 和 B 組成長度為 $L$ 的字串，使得 A 在 B 的左邊的組數恰好為 $K$，沒有的這樣的字串存在則回傳空字串

數據範圍：小小的

tag：[ greedy ]

= = = = = = = = = = = = = =

若 A 的數量固定，可以想像所有 A 在所有 B 的左邊時組數會最多，並且數量為 $k*(L-k)$　($k$ 為 A 的數量)。故組數最多的情況發生在 $k = L/2$。

接著我們可以發現，若存在某個A在某個B的左邊相鄰位置，我們把這兩個相鄰的 AB 交換後，可使 A 在 B 的左邊的組數減 $1$，並且若當前組數不為 0，總是可以找到這樣的相鄰的 AB。

有以上結論，應該就能解出這題了。

550 --- KitayutaMart

題意：一個商店裡有 $K$ 種商品，你所買的第 $k$ 個第 $i$ 種商品要花費 $i \times 2^{k-1}$ 元，你總共要買 $N$ 個商品，希望最貴的一項商品價錢最少，請輸出此價錢 mod $10^9 + 7$

數據範圍： $1 \le N, K \le 10^9$

tag：[ 數學 ][ 二分搜 ]

= = = = = = = = = = = = = =

我的思考邏輯如下：

首先注意到，若某項商品買了比另外一項商品多了至少30個則一定比較貴，所以買的任兩種商品的數量差一定不超過 $30$。

於是我們就可以估計出，最貴的那項商品所買的商品數範圍，一定落在 [$N/K - 100$,N/K + 100] 之間 (對不起我的腦帶無法快速算出更精確的範圍，就隨便給一個一定會對的區間...)。

接著我想對所有可能的 $k$ 試試看，最貴的商品是否可能是第 $k$ 個某商品，由於同種商品的第 $k$ 個的價錢是嚴格遞增的，自然而然的就想到要使用二分搜，於是，在二分搜時我們要判斷：價錢不超過第 $k$ 個第 $i$ 種商品的有幾個，我們能因此找到最小的 $x$ 滿足價錢不超過第 $k$ 個第 $x$ 種商品的個數為 $N$ 個以上，接著我們再計算價錢恰巧和第 $k$ 個第 $x$ 種商品一樣的有幾個，就能知道有第 $N$ 個商品的價錢是否和第 $k$ 個第 $x$ 種商品一樣。

我們剩下兩個問題要解決：1.價錢不超過第 $k$ 個第 $i$ 種商品的有幾個  和 2.價錢恰巧和第 $k$ 個第 $x$ 種商品一樣的有幾個。

第二個問題應該是比較簡單的。我們知道所有的整數數對 $(a, b)$ 若 $a$ 為正且 $b$ 介於 $1$ 和 $k$ 之間，則恰對應到一個價錢是 $a * 2^{b-1}$ 的商品，所以我們只要枚舉所有可能的 $i$ 使得 $(x*2^i, k-i+1)$ 仍是合法的數對，就能知道第二個問題的答案了，數量一定不超過 $30$ 個。

而知道了第二個問題的答案，離解第一個問題也不遠了，因為同樣是第 $k$ 個同種商品，且價錢不超過第 $k$ 個第 $i$ 種商品的個數就是 $i$。於是用類似解第二個問題的方法也可解第一個問題。

850 --- Fragile

題意：有編號的 $N$ 個點所形成的無向圖，有多少種橋的個數是 $K$？所謂的橋是指移除後圖的連通塊個數會增加的邊。

數據範圍：小小的

tag：[ 數學 ][ dp ]

= = = = = = = = = = = = = =

這種題目還蠻常見的，各種各式各樣的圗的技術問題，舉例來說，也有問題是問你 $N$ 個點的樹 (tree) 有幾種？或問你 $N$ 個點的連通圖有幾種？甚至問你 $N$ 個點的強連通有向圖有幾種？

之前有在網路上看到一篇投影片是在介紹各種類似的問題，不過我一時間找不到...

這題由於數據範為小小的，所以你使用高複雜度的 dp 都是可解的，大不了花個十幾分鐘跑完程式後把結果印在 code 裡(例如 Petr 的 code)。我自己賽後想到的式O($N^5$)

不過根據我對 writer 的 code的考據，他使用了最高為O($N^4$)的時間複雜度作了總計三次 dp。

(以下所謂的圗都是有編號的 (labeled))

第一次：求出 $N$ 個點的所有點都連通的圖有幾種。時間複雜度為O($N^2$)。

$dp1[i]$ 紀錄點數為 $i$ 的連通塗有幾種。

首先我們知道 N 個點的圗共有 $2^{N*(N-1)/2}$ 種，意即每個邊可選或不選。而若能扣掉部連通的圗的個數，就可以求出連通的圗的個數了。所以我們就枚舉和邊號 $1$ 的點連通的點數，從 $1$ 枚舉到 $N-1$，個數分別是 $dp1[i] * 2^{(N-i)*(N-i-1)/2} * C(N-1, i-1)$

第二次：求出 $N$ 個點的所有點都連通且有 $K$ 個橋的圗有幾種。O($N^4$)。

$dp2[i][j]$ 紀錄 $i$ 個點 $j$ 個橋的種類數。

$j = 0$ 的時，我們一樣試著用 $dp1[i]$ 去扣掉所有 $j$ 非 $0$ 的值。

對於 $j$ 不為 $0$ 的情形，我們使用一種 counting 的技巧 --- 讓同一張圖重複算好多次，但被算到的次數是一樣的，就可以把結果除以同張圖被算到的次數來得到答案。

實際上就是，我們計算編號 $x$ 和編號 $y$ 的點中間有橋的個數，若此座橋移除後，和點 $x$ 連通的點數有 $u$  個且含有 $r$ 座橋，則和點 $y$ 連通的點有就有 $i-u$ 個以及有 $j-r-1$ 座橋，這是我們可以 $O($1$)$求得的東西而且不管 $x$ 和 $y$ 是選哪兩個點結果都一樣，最終同一個圖都恰被算到 $j$ 次(因為 $j$ 座橋恰被枚舉到一次)。把我上面所述的綜合起來，會發現是個 O($N^4$) 的式子。

第三次：求出 $N$ 個點恰 $K$ 個橋的圗有幾種(即最終答案)。 O($N^4$)。

已經有了第二次dp的結果，這部分應該就容易多了，我就不解釋了。