SRM 453

Posted on 2009-11-19 00:16 王之昊 阅读(151) 评论(0)  编辑 收藏 引用
    这场很悲剧的是tc的服务器挂了.有人说这应该是tc头一回吧
    结果是这场比赛没做成.今天把题目再看了一遍,这场的主题是比赛的计分.
   
    250分比赛的规则是胜者得2分,负者得0分,平局各得1分.有n(n<=5)个队,每两个队之间要打两场比赛.之后会有一个积分榜.那么求有多少种积分榜榜首为m.注意只关心那个序列,不关心谁排第一,谁排第二.
    由于只有5个队,所以枚举每两个队的比分情况(有三种2:0 , 1:1, 0:2)大牛们清一色的dfs.果然dfs写的直观简洁

   500分比赛的规则是胜者得w分,负者不得分,平局各得d分.每两队之间可以比赛任意场次.然后给你一个n个队比赛的最终积分榜。让你判断这个积分榜是否合法。如果合法。求出最少比赛场次。
    这道题是div2的第一题的加强版(那题中w=2,d=1)。咋看一下没啥想法。只知道单看每个队的分数fi必须满足 w * x + d * y = fi 然后很自然的会先把最少的w减掉(因为w可以任意构造,在其他队加0不影响),如果这步都办不到,显然不合法。那么剩下的分数就都能整除d 了。我们先考虑剩下的 d  都是实打实的平局。怎么判它是否合法 ? 排个序,如果第一大的比剩下所有的总和还要大,显然不行。否则就能够构造出一种可行方法。

  这里简单证明一下, 换一种说法。有n个队任意比赛,给出每个队最终比赛场次。问数据是否真实。
  假设 n个队 的比赛场次 a1 >= a2 >= a3... >= an   sum = a1 + a2+..+an   a1 <= sum - a1 ; sum必为偶数
  我们要证明满足上面的条件的数据都可能是真的。现在来反证
  假设我们找到一个sum值最小的反例。sum >= 1
  0  如果只有一个队,违背了上面假设的 a1 <= sum - a1,所以不会出现这种情况
  1  如果只有两个队 a1 >= a2 && a1 <= a2 所以 a1 == a2  所以两个队也不会出现反例
  2  如果有三个队以上, 考虑前三个 a1, a2, a3    
         X如果 a2 > a3. 那么 a1-1, a2-1, a3, ... an将会是一个更小的反例. 矛盾
         Y如果 a1 > a2 = a3, 那么 a1-1, {a2-1, a3, ... ,an}将会是一个更小的反例, 矛盾{..}需要重新排序
         Z如果 a1 = a2 = a3,  那么  a1 ,{a2-1, a3-1, .... an}将会是一个更小的反例, 矛盾,可以证明原sum >= 2*a + 2
 
  证的很罗嗦,希望早日看到 tc 的 报告出来
 
   然后接下去就是枚举到底有多少平局。从刚刚得到的一个最基本的局面开始枚举。我们可以知道几场平局==几场胜局的分,每次减掉一个最单元的这个分开始枚举,取一个最优的即可

  1000分一如继往的不会


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


posts - 26, comments - 7, trackbacks - 0, articles - 17

Copyright © 王之昊