2015年1月31日 星期六

Codeforces Round #289 (Div. 2) (pD ~ pF)

problem D --- Restoring Numbers

題意:你有個長度為 $n$ 的陣列 $a$ 以及長度為$m$ 的陣列 $b$以及一個正整數 $k$,並且有個 $n \times m$ 表格 $w$,並把格子 $v_{i,j}$ 填入 $a_i + b_j$。如今你已忘了陣列 $a$ 和 $b$以及數字 $k$,但還留有表格 $w$,請給出一組能得到表格 $w$ 的 $a, b$以及 $k$,或者輸出無解。

數據範圍:$1 \le n,m \le 100, 0 \le w_{i,j} \le 10^9$

tag:[ 數學 ]

先想想簡單版的題目:沒有 $mod k$ 這件事且填入的數可正可負。

題目若變成這樣,我們只要令 $a$ 為 $w$ 的第一行(column),並令 $b$為 $w$ 的第一列並再把所有數減去 $w_{0,0}$,再用這裡得到的 $a$ 和 $b$ 去構造回 $w$ 表格,若吻合就得到答案,若不吻合就無解(why?列一些代數式可得到此結論)。

再看回來原來的題目,若我們使用同樣的做法會怎樣?是否能只修改一些地方就能得到答案呢?

先不考慮構造出來的 $a$ 和 $b$ 可能有負值的問題(實際上若有負值,輸出答案時 mod 最後求出來的 $k$ 後取正就好了),原本我們要考慮的是藉由構造出來的 $a, b$是否能滿足 $a_i + b_j = w_{i,j}$,但現在我們要的是:能否存在 $k$ 使得所有 $a_i+b_j \equiv w_{i,j}$ (mod $k$),再換成更好懂的條件: $k \mid a_i + b_j - w_{i,j}$。
於是我們就得到,$k$ 為所有 $a_i + b_j - w_{i,j}$ 的公因數時,用這樣的 $a,b$ 構造出的來表格mod $k$ 後會和 $w$ 一樣,由於實際上還必須使得k大於所有 $w$ 裡的數,所以我們可以直接令 $k$ 為那些數的最大公因數。並且若其大於 $w$ 裡所有數就有解,否則就無解。

最後要注意一個 special case:$w_{i,j}$ 都剛好為 $a_i + b_j$。(想想看會發生什麼事?)

Problem E --- Pretty Song

題意:給一個字串求所有此字串所有 substring 的母音比例總和(母音為AEIOUY)

數據範圍:字串長度不超過 $5 \times 10^5$

tag:[ dp ][ 數學 ]

看到這個問題大概就會想到把 sigma 求和的式子轉換一下可能可以換成比較好算的式子。但這題的式子很直白,我們可以不介由式子,直接把所求想像成每個母音會對一些 substring 貢獻一些值,例如說,若第一個字母是母音,並且它被包含在長度 $1$ ~ $|s|$ 的子字串各恰一個裡,那第一個字母就會貢獻給總和 $1/1 + 1/2 + ... + 1/|s|$。再觀察仔細些,你會發現若第二個字母是母音,將會貢獻給總和 $(1/1 + 1/2 + ... + 1/|s|) + (1/2 + 1/3 + ... + 1/(|s|-1))$。
實際上,對於所有$ 2 \le i \le |s|/2$,第 $i$ 個字母會比第 $i-1$個字母多貢獻 $1/i + 1/(i+1) + ... + 1/(|s| - i + 1)$的值(Why?),並考慮到第 $i$ 個字母和第 $|s| +1-i$個字母的貢獻的值一樣的對稱關係,我們就藉由先dp好調和級數求解了。

P.S. 實際上求和的式子可以直接 dp 後計算,請參考官方 Blog 解答

Problem F --- Progress Monitoring

題意:給一個長度為 $n$的 DFS 序列問有多少 tree可以產生這樣的 DFS 序列(同一層 DFS 裡由編號小的先走訪)

數據範圍:$n \le 500$,第一個數一定為 $1$

tag:[ dp ][ 區間型dp ]


有沒有發現 tag 和上一場 Codeforces pE 一樣呢~那我可不可以不要寫這題的題解了啊Orz

就大略解釋一下同個區間我們要記錄什麼狀態。

實際上同個區間我用了兩個狀態:1. 若此區間第一個點為root,有多少種可能 2.若此區間為拜訪額外的root後所得到的序列,有多少種可能

若第一個dp值記作dp1(L1, R1),第二個記作dp2(L2, R2) (區間為[L1,R1] or [L2,R2])

我們可以列出狀態轉移式:
dp1(L1, R1) = dp2(L1+1, R1)
dp2(L2, R2) = dp1(L2, R2) + dp1(L2, k) * [b(L2+1) $\lt$ b(k+1)] * dp2(k+1,R2) for k from L2 to R2-1
([]的意思是裡面成立的話值為 $1$,否則為 $0$)

若很相信這類的 dp 能解它的話這題應該不會很難才對?

在這裡提供另外一題和本題和像但難度差了十萬八千裡的題目!


這題連題目名稱都很潮XD

大意是:給你一個 tree 的 BFS 走訪序列以及 DFS 走訪序列,求有多少種 tree 能產生這樣的序列。

歡迎想出這題的人 PO 出作法和大家分享XD