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
沒有留言:
張貼留言