2015 UESTC Winter Training #7【2010-2011 Petrozavodsk Winter Training Camp, Saratov State U Contest】

2015 UESTC Winter Training #7

2010-2011 Petrozavodsk Winter Training Camp, Saratov State U Contest

据说这套题写出3题就是金牌水平了。。。

Problem D. Group Stage

足球比赛,现在有n(2<= n <=100)支球队。要从中选拔m(1<= m <=n-1)支球队,每支球队互相比赛一场,即比赛n*(n-1)/2场,胜者得3分,平局各得1分。最后从大到小列出排名,如果有队伍恰好得分相同,并且必须从中选出几支球队,那么采用抽签的方式选取。问:

  1. 球队排名在最后一名(有很多并列)仍然可能被选中的最小得分
  2. 球队排名在第一名(还是有很多并列)仍然可能不被选中的最大得分。

代码很短,就是一个公式,但是公式竟然推了两个小时

先看第一问,排名在最后一名,仍然被选中,也就是说,得分从大到小排序后第m支到第n支球队得分相同,并且得分一定要最小。显然他们都输给前m-1支队伍,然后互相比赛均为平局时最小。想想,假如相互比赛时有一个人胜利了,它该场比赛得分为3,就比得分1的平局得分更多。那么我们输出n-m即可。

再看第二问,排名在第一名,仍不一定被选中,也就是,得分从大到小排序后第1支到第m+1支球队得分相同,并且得分最大。对于每个球队,要战胜第m+2支到第n支球队,得分为(n-m-1)*3。在前m+1支球队互相比赛中,每个球队,胜m/2场,如果m是奇数,再平局一场,得分为m/2*3+m%2这时的得分最大。

 

 

Problem E. Map Coloring

这道题还没有写,据说用到 DP 和 最大权匹配。

Problem J. Taxi

有n个男孩,m个女孩(均小于2011,其中m<=3n)要乘出租车回各自的家,每个出租车最多乘4人,并且每个出租车上必须有一个男孩(男孩可以坐完全程),他们回家的方向相同,并且家在同一条街上。每个人的姓名以及家的距离已给出dis<=10000。问出租车最小的总费用是多少,并输出需要的出租车数以及任意一种费用最小方案。

动态规划,先将男孩和女孩分别按照家的距离从大到小排序,设dp[i][j]为前i个男孩和前j个女孩乘坐出租车的最小费用。

dp[i][j]=min{ dp[i-4][j] + 4个男孩的最远路程,dp[i-3][j-1] + 3男1女中的最远路程,

dp[i-2][j-2]+2男2女中的最远路程,dp[i-1][j-3]+1男3女中的最远路程}

最后一辆出租车可能载不满客,需要特殊判断一下。

dp的每一步记录一下前驱,最后递归输出即可。

上一篇:freeCodeCamp:Repeat a string repeat a string


下一篇:2015-2016 Petrozavodsk Winter Training Camp, Nizhny Novgorod SU Contest (5/9)