為生存而奔跑

:: 首頁(yè) :: 聯(lián)系 :: 聚合

:: 管理

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

留言簿(5)

我參與的團(tuán)隊(duì)

隨筆分類(lèi)

隨筆檔案

相冊(cè)

Girl

搜索

積分與排名

積分 - 326992
排名 - 74

閱讀排行榜

評(píng)論排行榜

矩陣題目 zz

pku
3070 Fibonacci

http://acm.pku.edu.cn/JudgeOnline/problem?id=3070
矩陣二分最基礎(chǔ)也是最經(jīng)典的題目，構(gòu)造方法很多，由于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次就可以相應(yīng)得到各項(xiàng)的值。

3735 Training little cats http://acm.pku.edu.cn/JudgeOnline/problem?id=3735
如果有n只貓，就構(gòu)造一個(gè)(n+1)*(n+1)的矩陣，最后一列作為增加的數(shù)量，然后進(jìn)行矩陣二分。
具體構(gòu)造如下：
先令初試矩陣為單位陣，
每次讀到"g"，就在每只貓相應(yīng)行的最后一格執(zhí)行自增操作。
每次讀到"e"，就將相應(yīng)貓所對(duì)應(yīng)的行全部清零。
讀到"s"，就將相應(yīng)的兩行兌換。
比賽時(shí)做了很多優(yōu)化，可就是TLE。因?yàn)樵摼仃囀窍∈杈仃嚕簿褪钦f(shuō)矩陣中有很多0，所以相乘的時(shí)候判斷一下兩個(gè)數(shù)是否有一個(gè)為0，如果是就不相乘了，效率高了一倍以上。

1977 Odd Loving Bakers http://acm.pku.edu.cn/JudgeOnline/problem?id=1977
每次都是winner才有權(quán)利給他喜歡的人畫(huà)上一個(gè)記號(hào)，于是構(gòu)造一個(gè)n*n的矩陣，第i行第j列表示如果j是winner，j是否會(huì)在i上畫(huà)記號(hào)（0 or 1）那么矩陣就是一個(gè)01矩陣，進(jìn)行二分的時(shí)候可以采用二進(jìn)制位運(yùn)算加速，有一點(diǎn)要注意的就是，如果要求是場(chǎng)的話，二分次數(shù)只要k-1就夠了，原因題目里已經(jīng)講了：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
算蠻經(jīng)典的矩陣二分了，首先推出遞推式，方法很多，我采用了最笨的辦法，直接枚舉所有狀態(tài)來(lái)后解方程，得出遞推式后進(jìn)行矩陣二分，但是由于遞推式中有減項(xiàng)，所以二分取模的時(shí)候需要處理一下，將負(fù)數(shù)加上m。

3233 Matrix Power Series http://acm.pku.edu.cn/JudgeOnline/problem?id=3233
等比矩陣求和，有經(jīng)典算法，假定原矩陣為A，階數(shù)為n，那么構(gòu)造一個(gè)階數(shù)為2n的矩陣，如下
| A   E |         其中O代表O矩陣，E代表單位矩陣，這樣，求出的K次矩陣的右上n子矩陣正好是
| O   E |         等比矩陣的K項(xiàng)和，這種構(gòu)造法比我實(shí)現(xiàn)的兩次二分快了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 閱讀(757) 評(píng)論(0) 編輯收藏引用所屬分類(lèi): Algorithm

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理