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分一如继往的不会