精選CF大水題十題，之是以說是大水題應該比一般的水題難一點也就大一點。
一、cf 144 D Missile Silos http://www.codeforces.com/problemset/problem/144/D
spfa但要掃描點掃描邊
二、cf 141 C Queue http://www.codeforces.com/problemset/problem/141/C
構造題，我的方法是先構造一個合法序列然後再為為剩下的值指派，構造的身高在n以内。
三、cf 138B Digits Permutations http://www.codeforces.com/problemset/problem/138/B
貪心，先枚舉末尾為10的各種組合，然後找前面最多的9個數，要注意無法枚舉到10的時候。
四、cf 137E Last Chance http://www.codeforces.com/problemset/problem/137/E
線段樹，v<2*c，先統計cnt[i][k]表示長為i的字首中原音和輔音的個數，然後兩i，j，如果2cnt[i-1][2]-cnt[i-1][1]<=2cnt[j][2]-cnt[j][1]就是個好子串。
這樣對arr[i] = 2cnt[i-1][2]-cnt[i-1][1]進行排序，然後找比它大的最大下标。
五、cf 128A Statues http://www.codeforces.com/problemset/problem/128/A
搜尋。因為石像每次都要向下滾一格，那麼可想而知後面幾s它們都在哪裡。先預處理出後面9s哪裡可以走哪裡不可以走，然後進行搜尋。
六、cf 128B String http://www.codeforces.com/problemset/problem/128/B
優先隊列應用。題意是要讓我們找第k大的子串，因為k<=10萬，是以可以用優先隊列進行模拟，最開始先存入1個字元，因為最大的肯定是1個字元，然後出隊再将出隊的那個字元的下個合并，比如abc，先進a,b,c，然後a先出，接着ab進，就這樣反複模拟...
七、cf 128C Games with Rectangle http://www.codeforces.com/problemset/problem/128/C
組合數學+DP。樸素的O(n*m*k)的DP很好想，但是複雜度太高TLE。先要想清楚，這題長和寬實際上是互相獨立的，那麼就可以用乘法原理，将長邊算出來的方案數*寬邊算出來的方案數。算長邊的方案數可以用O（n*k)的DP計算。狀态轉移方程:dp[i][j] = dp[i-2][j-1] + 2*dp[i-3][j-1]+3*dp[i-4][j-1]...(n-1)*dp[i-n][j-1]，然後進行優化，像這種可以從前面連續的狀态轉移過來的dp似乎都可以加個sum，然後dp[i][j] = sum + dp[i-1][j-1];
八、cf 218B. Special Offer! Super Price 999 Bourles! http://www.codeforces.com/problemset/problem/219/B
構造題。我一開始是從小往打構造，馬上發現錯了。然後就從大往小構造，方法是每次都把最後一位變成9，如果最後一位是9那麼不調整，如果不是9那麼前一位要減一，直到小于最小的數。
九、cf 218C. Color Stripe http://www.codeforces.com/problemset/problem/219/C
貪心或者DP，我是用貪心。先特判k==2的情況，這時候就兩種情況要麼奇數位為A偶數位為B，要麼奇數位為B偶數位為A，答案是兩種中轉變次數較小的。k ！= 2的時候，就從前往後周遊，找一整塊相同的字母，然後把第2,4...變成和後面一個不一樣的字母即可，因為顔色大等于3，那麼肯定可以找到一種和目前顔色不一樣又和後面一個顔色不一樣，而這樣顯然是最優方案。這題有人用O(n*m*m)的DP去寫，我覺得很神奇，這樣最多的運算量是3億多。
十、cf 218D. Choosing Capital for Treeland http://www.codeforces.com/problemset/problem/219/D
樹形DP。這題有個很巧妙的轉換，那就是把邊的方向轉變成邊權，如果正向那麼邊權威0，如果反向，那麼邊權為1.經過這樣轉換，問題就變成求以某點為根到其他各點的邊權總和，然後求邊權總和最小的那些點。這類樹形DP很經典，做法是先以某點為根向葉子節點周遊，然後再以前面那點為根向下更新答案。
本文ZeroClock原創，但可以轉載，因為我們是兄弟。