2015年2月2日 星期一

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的結果,這部分應該就容易多了,我就不解釋了。