這場只有div 2的, 題目也意外地有6題, 暫時解了5題, 第6題還沒看題目..
做到再補完吧,,
Codeforces Round #277.5 (Div. 2)
A:
頹題, 但一開始是嚇死我了
題目要找出把一個sequence sort好的swap 次序,
我開頭以為要找最短的次序,,,
原來我瞎了看錯題目, 明明就是寫 "you do not have to minimize the number of swaps"...
B: (Greedy)
半頹題
題意如下:
Given n 個男仔, m 個女仔, 每個人有個value, 如果男女value difference <= 1 可以pair up
問最大pair up #
Greedy地 maintain 2支pointer pair up 最大value的就好...
C: (DP? Ad-hoc? Greedy!)
Fuck, 這條才是麻煩, 我從看題目就中伏了幾次
題目求找出長度為S 的數字, s,t, sum of digit = N
問最小的數字和最大的數字是什麼, 沒有則print -1
從數據上, 我最直接當然是想到DP了...其實DP好像也真的能做到的樣子
可惜最後我用了個較constructive的方法 (而且code也有點煩膠)
要我說的話是Greedy的做法
其實就是先把每個位置都填上 N/S (average), 然後看是找最小的數字還是最大的
把頭尾的位置, 一個+1, 一個-1, 直到boundary (0 或者 9) 就移動pointer 去改下一個位置
但中伏位還是很多的, 例如第一個位置不可以是leading zero, 但中間的位置可以是0 吧
由於這個特性, 找最小和最大的數字 不太一樣做法
例如 長度2, 總數為8的答案就是 17 和 80
一個loop就做到了, 所以是O(S)
D: (Graph, DP)
還是很頹的題目
題意是這樣的, Given 一個有向圖 (不肯定是否DAG, 也不重要)
n個node (n <= 3000)
找出「吃屎菱形」的數目, 該形狀定義為:
由A到B的path中, 有兩條path為 ACB 和ADB
那麼(A,B,C,D) 就是一個「吃屎菱形」
C和D的次序不重要 (在數菱形數目的時候)
很直接就想到去DFS了吧 (尢其有上一場某題的經驗...)
話說就是DFS, 說它有DP的成分是因為你需要儲下一些資料而已, 但其實這些資料
不需要什麼子問題就可以計到, 所以又不能說是DP...不管了
總之就是define dp(n,m) 為 n 到 m 長度為 2 的path 的數目
那麼 dp(n,m) choose 2 就是以n,m為end point的「吃屎菱形」數目
話說由於DFS的深度也只有2, 就是說不怕煩的寫for loop 也行
複雜度也是O(n^2)
頹題, 但一開始是嚇死我了
題目要找出把一個sequence sort好的swap 次序,
我開頭以為要找最短的次序,,,
原來我瞎了看錯題目, 明明就是寫 "you do not have to minimize the number of swaps"...
B: (Greedy)
半頹題
題意如下:
Given n 個男仔, m 個女仔, 每個人有個value, 如果男女value difference <= 1 可以pair up
問最大pair up #
Greedy地 maintain 2支pointer pair up 最大value的就好...
C: (DP? Ad-hoc? Greedy!)
Fuck, 這條才是麻煩, 我從看題目就中伏了幾次
題目求找出長度為S 的數字, s,t, sum of digit = N
問最小的數字和最大的數字是什麼, 沒有則print -1
從數據上, 我最直接當然是想到DP了...其實DP好像也真的能做到的樣子
可惜最後我用了個較constructive的方法 (而且code也有點煩膠)
要我說的話是Greedy的做法
其實就是先把每個位置都填上 N/S (average), 然後看是找最小的數字還是最大的
把頭尾的位置, 一個+1, 一個-1, 直到boundary (0 或者 9) 就移動pointer 去改下一個位置
但中伏位還是很多的, 例如第一個位置不可以是leading zero, 但中間的位置可以是0 吧
由於這個特性, 找最小和最大的數字 不太一樣做法
例如 長度2, 總數為8的答案就是 17 和 80
一個loop就做到了, 所以是O(S)
D: (Graph, DP)
還是很頹的題目
題意是這樣的, Given 一個有向圖 (不肯定是否DAG, 也不重要)
n個node (n <= 3000)
找出「吃屎菱形」的數目, 該形狀定義為:
由A到B的path中, 有兩條path為 ACB 和ADB
那麼(A,B,C,D) 就是一個「吃屎菱形」
C和D的次序不重要 (在數菱形數目的時候)
很直接就想到去DFS了吧 (尢其有上一場某題的經驗...)
話說就是DFS, 說它有DP的成分是因為你需要儲下一些資料而已, 但其實這些資料
不需要什麼子問題就可以計到, 所以又不能說是DP...不管了
總之就是define dp(n,m) 為 n 到 m 長度為 2 的path 的數目
那麼 dp(n,m) choose 2 就是以n,m為end point的「吃屎菱形」數目
話說由於DFS的深度也只有2, 就是說不怕煩的寫for loop 也行
複雜度也是O(n^2)
void dfs(int r, int c, int d){ if(d == 2){ dp[r][c]++; return; } for(int i=1; i<=n; i++) if(g[c][i] && i != r) dfs(r,i,d+1); } int main() { scanf("%d%d", &n, &m); for(int i=0; i<m;i++){ scanf("%d%d", &a,&b); g[a][b] = 1; } for(int i=1; i<=n;i++)dfs(i,i,0); for(int i=1; i<=n; i++) for(int j=1; j<=n;j++) ans += (dp[i][j] * (dp[i][j]-1))/2;
E: 沒看題目...
F: (DP, Combinatorics)
最有成功感的一題, 因為最難=.=題意是這樣的:
有一個n x n 的square matrix, 全部都是0 或者 1
然後該matrix 每一row 和每一column 都必定有(和不多於) 兩個1
現在提供了頭m row (m <= n) , 問餘下的rows任填的情況下, 有多少種valid既matrix?
當然又是mod 一個大數
n <= 500
糾結啊...
DP是DP的了, 又想不到狀態...
Combination怎麼數? 曾經不是有些心得的嗎...
又沒什麼頭緒...
在紙上畫呀畫, 突然運氣又到了
不知為什麼會走去想到 "每一column 還需要填'1'的數目" 這件事
而且這個就是重點了!
別管DP的部分, 直接看數combination的話怎樣數呢?
基本上, 「每一個column還需要填 1 的總數」只有{0,1,2}
0 就是說根本不用再填了, 完全不用管, 剩下{1,2}兩種
好像有點煩, 所以直接想全部都是1 的情況:
每一row也一定要有2個1 的, 而我每一個column的「彈藥」也剛好是1
就是說我用完某一個column, 其它row就不能再用了
所以第一row (第一個我要填的row) 是 nC2 的可能性
然後第二row 是(n-2)C2 的可能性..
直到2C2
回到有{1,2} 兩種「彈藥庫」的情況, 把問題換個角度形容吧~
就是有n 個箱子, 有些箱子有一個球, 有些箱子有兩個球,
每次要抽兩個球, 而且不能從同一個箱子抽, 抽完把球扔走
總共抽 n-m次 <--這個其實不重要, 總之直到球抽完就好
有多少種不同的抽法?
我忽發奇想, 由於全部箱子都是一個球的情況上面已經處理到了
有沒有機會把現在這個問題也化為全都是一個球的問題/子問題處理呢...
答案是YES!
對於第一次抽球 (就是填第一個row), 我可能的選擇只有三種 (是說三個類別, 不是只有三個可能性!)
1. 從兩個「裝有一個球的箱子」各抽一個
2. 從兩個「裝有兩個球的箱子」各抽一個
3. 從一個「裝有一個球的箱子」和一個「裝有兩個球的箱子」各抽一個
發現了吧! 「裝有一個球的箱子」和「裝有兩個球的箱子」的數目我是知道的
然後每次抽球只有這三種可能性, 每次抽完會影響到這兩種箱子的數目
然後再抽....變成子問題了! (箱子數目減少了!)
轉化為DP去實作
Define dp(n,m) := 有n 個「裝有一個球的箱子」, m個「裝有兩個球的箱子」, 直到抽到沒球可抽的所有可能抽法總數
dp(n,m) = nC2 * dp(n-2, m) + mC2 * dp(n+2, m-2) + n*m*dp(n, m-1)
當然吧, 每個component都要先查一下是否真的valid, 例如最後的component
雖然好像只要m-1 非負數, 但實際上他代表的是從兩種箱子各抽一個球
所以n 也要 >= 1
最後處理好base case, dp(0,0) = 1 吧 <---這個其實就是說所有row input都provide, 無野填=.=
提交吧! TLE!!! WTF!!!
喊出黎, 我完全唔知點解...
最後終於發現....是這兩句
if(d[N][M]) return d[N][M];
累事啊..
因為...因為題目是要mod一個大數, mod完之後答案的確可以是0的, 那麼這些dp state永遠不能reuse了...當然TLE 啊=.=
把初始值改為-1, 再判定為非-1
if(d[N][M]!=-1) return d[N][M];
AC了!!!!
複雜度呢, top-down要solve recurrence relation的說...
說笑呢...bottom up + logically n <= 500, 所以是 O(n^2)
