為生存而奔跑

:: 首頁 :: 聯系 :: 聚合

:: 管理

271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我參與的團隊

隨筆分類

隨筆檔案

相冊

Girl

搜索

積分與排名

積分 - 328403
排名 - 74

閱讀排行榜

評論排行榜

矩陣題目 zz

pku
3070 Fibonacci

http://acm.pku.edu.cn/JudgeOnline/problem?id=3070
矩陣二分最基礎也是最經典的題目，構造方法很多，由于F[n] = F[n-1] + F[n-2];
|       0         1         |   |       F[n-2]     |           |         F[n-1]       |
|                             |   |                     |   =     |                       |
|       1         1         |   |       F[n-1]     |           |         F[n]         |
然后只要求01矩陣的m次就可以相應得到各項的值。

3735 Training little cats http://acm.pku.edu.cn/JudgeOnline/problem?id=3735
如果有n只貓，就構造一個(n+1)*(n+1)的矩陣，最后一列作為增加的數量，然后進行矩陣二分。
具體構造如下：
先令初試矩陣為單位陣，
每次讀到"g"，就在每只貓相應行的最后一格執行自增操作。
每次讀到"e"，就將相應貓所對應的行全部清零。
讀到"s"，就將相應的兩行兌換。
比賽時做了很多優化，可就是TLE。因為該矩陣是稀疏矩陣，也就是說矩陣中有很多0，所以相乘的時候判斷一下兩個數是否有一個為0，如果是就不相乘了，效率高了一倍以上。

1977 Odd Loving Bakers http://acm.pku.edu.cn/JudgeOnline/problem?id=1977
每次都是winner才有權利給他喜歡的人畫上一個記號，于是構造一個n*n的矩陣，第i行第j列表示如果j是winner，j是否會在i上畫記號（0 or 1）那么矩陣就是一個01矩陣，進行二分的時候可以采用二進制位運算加速，有一點要注意的就是，如果要求是場的話，二分次數只要k-1就夠了，原因題目里已經講了：Before each celebration those bakers with an odd number of chalk marks on their house will be chosen as winners。

3420 Quad Tiling http://acm.pku.edu.cn/JudgeOnline/problem?id=3420
算蠻經典的矩陣二分了，首先推出遞推式，方法很多，我采用了最笨的辦法，直接枚舉所有狀態來后解方程，得出遞推式后進行矩陣二分，但是由于遞推式中有減項，所以二分取模的時候需要處理一下，將負數加上m。

3233 Matrix Power Series http://acm.pku.edu.cn/JudgeOnline/problem?id=3233
等比矩陣求和，有經典算法，假定原矩陣為A，階數為n，那么構造一個階數為2n的矩陣，如下
| A   E |         其中O代表O矩陣，E代表單位矩陣，這樣，求出的K次矩陣的右上n子矩陣正好是
| O   E |         等比矩陣的K項和，這種構造法比我實現的兩次二分快了4倍左右。

http://acm.pku.edu.cn/JudgeOnline/problem?id=2778
http://acm.pku.edu.cn/JudgeOnline/problem?id=2440

hdu
http://acm.hdu.edu.cn/showproblem.php?pid=2243
http://acm.hdu.edu.cn/showproblem.php?pid=1757
http://acm.hdu.edu.cn/showproblem.php?pid=2429
http://acm.hdu.edu.cn/showproblem.php?pid=2276
http://acm.hdu.edu.cn/showproblem.php?pid=2238
zju
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2853

fzu
http://acm.fzu.edu.cn/problem.php?pid=1683
http://acm.fzu.edu.cn/problem.php?pid=1692

posted on 2009-08-18 11:19 baby-fly 閱讀(760) 評論(0) 編輯收藏引用所屬分類: Algorithm

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 二分搜索找上下界算法導論上的歸并排序 PKU 2184 dp PKU 2392 多重背包 PKU 2823 Sliding Window 單調隊列 HDU 3415 單調隊列 t CRecordSet KMP字符串模式匹配詳解 HDU 3450 樹狀數組離散化

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理