dango

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  11 Posts :: 0 Stories :: 4 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

写了题还是应该来总结一下,否则除了个别刻骨铭心的题以外,都忘掉了。

POJ2155
题目大意:
给一个N*N的矩阵,每次给一个命令取反一个子矩阵,或者查询其中某一点的01状态。(注意每两组output中间要空行,PE了一次)

解题方法;
二维线段树。

解题小结:
原先好像写过二维的线段树,不过都忘得差不多了,这一次算是重新捡起来吧。
这一道题可以用a[rootx][rooty]来记录rootx段到rooty段是否取反,rootx指向行里的一段,rooty指向列里的一段,那么[rootx][rooty]就自然是一个子矩阵了。
最后求(x,y)是否取反,就是一路遍历所有包含x,y的矩阵,记录一下一共取反了多少次(Discuss里说用异或,很不错哈~)
这一题更新和查询都写成x,y版本的,x版本套y版本,就解二维的问题了。
例如在Modify_x里套用Modify_y。

POJ2155
posted on 2011-03-05 17:04 Dango 阅读(804) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理