| |
不指定 类别: 默认分类 | xioumu @ 2013/12/15 23:30 | 评论(0) | 阅读(4137)
e鸣杯程序设计竞赛现场决赛于12月15日13:00在计算机学院新大楼举行,参赛选手经过4个小时地激烈角逐,最终产生1名一等奖、3名二等奖、5名三等奖。至此,第七届e鸣杯程序设计竞赛圆满结束!
  以下为获奖名单:
  一等奖:   谭选择(11)
  二等奖:   张晨(11)  邓凌风(11)  方众(13)
  三等奖:   陈同舟(12)  李彦松(13)  张鹏程(13)   杨志勇(13)  廖禹(11)  


附: 最终比赛排名(打星的为校外同学友情参赛,不参与排名)
attachment.php?fid=28


武汉大学第7届Eming杯复赛解题报告:
A. 按题意直接做
B. N个商店都出售M种货物,每个商店对货物都有标价且折扣方式不同:每Xi件商品折扣为Yi%。现在要在其中一个商店买到M种货物,每种1件,求最低价格。
不是每件商品都能打折,所以打折的一定是价格最高的商品,将每个商店的商品各自排序后,价格最低的M%Xi件不能打折,其他都打折,算出每个商店的价格。
C. 给定一个带有3种括号的序列,判断是否合法。
对于没学过栈的同学其实也很简单。用tp记录当前数组尾部的位置,若新加入的字符与数组尾部字符是匹配的括号,则尾部前移,否则将新加入的字符加入数组,尾部后移。
D.一堆数量为N的糖果,两人轮流取,取的数量必须是2的幂,两人都采用最优策略,先取完者胜。

找规律的同学可能会发现N为3的倍数是后手胜,其他情况先手胜。
证明如下:
所有2的幂都是3K+1或3K+2的形式。当面对一个形如3K+1或者3K+1的局势时,一定可以通过一次操作将局势变成3K的形式。而当面对形如3K的局势,无论怎样操作,通过一次操纵只能将数量变为3K+1或3K+2的形式。
也就是说,如果N是3K的形式,那么后手一定有办法在每次操作结束后把数量变为3K,而先手每次操作结束后数量必定是形如3K+1或3K+2。如果N不是3K的形式,那么就是反过来的情形。
K=0时游戏结束。
E.
下载文件 (已下载 278 次)
    
F.这是一个比较考验基础能力的dp题。
    思路是很自然的,也就是先把所有符合条件的数累计到对应的状态
里,然后再做一次集合dp。
    ( 集合dp指的是用一个N位二进制来表示第i(0<=i是否存在,相关的资料网上有很多 )
    统计可以写得暴力点,直接用dfs搞,比较类似数位dp, 不过不用记
忆化。
    用 dfs( p, equ, mask, zero ) 按位枚举数字进行统计。
    其状态的含义是目前产生的数的前第p位是否与读入的数字相等
(equ == 1则相等),是否到第p位位置都是0(zero == 1则到目前为止
都是0),mask则表示的0到9的数字集合,也就是当前产生的数包含了哪
些数字。
    统计完了以后,剩下的集合dp就是很裸的问题了。
    
    其实包含的两个子问题都很基础,一个是数位dp的雏形,还有一个是
基本的集合dp,建议做这题前先在网上找到两种dp的模板题做一下,切这
题也就不在话下了。

G.首先题目描述中"less than" 应该改成"no more than" ........(发了clarification,woj中已改正)
考虑一开始第一回合,如果说Mov1>=D,那么先手直接获胜
否则显然Mov较大的人占有主动权,就是说,这个人最差也是平局而已
那么Mov较小的人最优的行动方案就是向远离敌人的方向移动,尽量不被敌人追上
然后考虑在什么条件下可以顺利的追杀到另一个人
在追杀的过程中,必然存在一种局面,Mov较大的人尽量的靠近Mov较小的,距离越近越好,但是不能进入敌人的攻击范围
也就是Mov较大的在出击前的最后一步一定是把两者的距离D缩小到比敌人的Mov大1的位置上
然后敌人依然选择反方向逃跑最大距离,只要我的攻击范围>敌人的最大移动范围Mov*2,在他逃跑了最大距离之后,就可以进行击杀
否则就是平局


ps:题目已挂在woj上,题号为1525~1531
pps:因为我们教练目前还在国外,奖状可能得等下个学期才能给各位,期间若需要奖状证明可以发邮件至 acmwhu[at]gmail.com询问。
ppps:胜败乃兵家常事,我们明年再会!

--
hi, 如果还有什么问题,请在下面留言让我们知道 :)
无觅相关文章插件
默认分类 | 引用(0) |