算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
去长春之前的一场。。。 现在把题解补上
250pt
   在二维坐标轴上从0,a走到k,b,走一次在x轴上前进一个单位长度,在y轴上上升或者下降一个单位长度。
   现在已知中间的某段连续区域的走法(只由'U'和'D'构成的不超过50的字符串)。问是否在保证最低点不低于0的情况下成功走到终点。

算法分析:
   计算这段区域的最低点,如果低于0,那就全用'U'补上。然后判断一下剩下的区间就可以了。

srm 557div1 250pt

500pt
   在一个图中,支持一种操作。每次对一个无色点的所有后继染色。但是不能对强联通分支中的点操作。问最多染色几次。
   相当于询问一个有限偏序集的宽度。有定理
      http://en.wikipedia.org/wiki/Dilworth%27s_theorem
   求传递闭包的最小点路径覆盖。二分匹配中可以不去掉强联通的边,因为这样的点在传递闭包中一定会占用一个最大匹配。

srm 557div1 550pt


posted on 2012-10-18 14:00 西月弦 阅读(430) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

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