QuXiao

每天进步一点点!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  50 随笔 :: 0 文章 :: 27 评论 :: 0 Trackbacks

明明是一道难度不大的题,我却做了N天才做出来,惭愧惭愧!看到题的第一想法就是如果A控制了B,就把B所占有的股份传给A以及A的母公司,并且这样递归下去。可自己编程会发生股份重复计算的情况,解决方法是当将B的股份更新到A上时(通过母公司的关系找到A),如果之前A已经直接或间接控制了B,那么如果再加就算是重复计算了。但在判断A是否直接或间接控制B时,又要判断是否有环。

后来在网上找到了一种解法:当发现A控制B时,将B的股份传给A,如果发现增加股份之后,A中的股份[A][i] > 50 并且A还没有控制i,则将(A, i)加入队列。一直循环操作,直至队列为空为止。

官方的解题报告中,其实就是我一开始想的递归的方法,他在更新(A, B)时:

  1. 如果A已经控制B,退出
  2. 若没有,control[A][B] = 1
  3. 将B的股份传给A
  4. 枚举已控制了A的i,递归更新(i, B)
  5. 枚举A的股份[A][k],如果大于50,递归更新(A, k)
posted on 2011-01-22 16:23 quxiao 阅读(217) 评论(0)  编辑 收藏 引用

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