为生存而奔跑
   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

随笔分类

随笔档案

相册

搜索

  •  

积分与排名

  • 积分 - 319831
  • 排名 - 75

最新评论

阅读排行榜

评论排行榜
矩阵题目 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 阅读(743) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理