不指定 类别: 默认分类 | @ 2016/03/08 16:30 | 评论(0) | 阅读(609)
成昌力
王睿达
吴飞洋
傅永健
李鹏宇
唐启铭
王旭东
石文博
李志恒
夏文文
魏子敬
顾有为
吴圣辉
王妍灵
岳知涵
操润楠
刘傲寒
余鹏
陈鸿恺
刘天威
肖俊阳
曹彬
贺进年
王致远
唐宇奕
甄牧放
唐瑶
李潇洒
郭天霖
李勇志
陈子轩
李笑薇
蔡金宝
马利凯
焦冲
刘叶
刘之兵
王宇飞
韩凌
刘昊(2015)
刘昊(2014)
徐炜烨
郭银杰
周金梦
徐晚雨
芦嘉良
王广任

请于3月13日9:30按时于计算机学院B303参加现场赛。其余未晋级但有兴趣参赛的同学请于周五之前发邮件到412383948@qq.com与我联系。
默认分类 | 引用(0) |
不指定 类别: 默认分类 | @ 2015/03/15 17:50 | 评论(0) | 阅读(704)
      e鸣杯程序设计竞赛现场决赛于3月15日11:00在计算机学院新大楼举行,参赛选手经过5个小时地激烈角逐,最终产生一等奖一队、二等奖两队、三等奖三队。至此,第八届e鸣杯程序设计竞赛圆满结束!
  以下为获奖名单:
  一等奖:   OrzPandora(陆敬浩 陈籽豪 梁曦璘)
  二等奖:   OrzCyy(周靖奇 肖俊阳 张巍)   OrzFzz(段庆  赵菁   王思锦)
  三等奖:   FreeHolding(汪剑杰  廖庆文  孙雅静)  FreeWifi(丁嘉辉 何益升 黄潋哲)  free_dom(方众 陈尧麟 赵一鸣)
默认分类 | 引用(0) |
不指定 类别: 默认分类 | @ 2015/03/15 17:21 | 评论(0) | 阅读(1311)
A
    a和x必然有一个在10^6以内,枚举a或x到10^6的情况即可。

B
    二分搜索answer,然后判定乘积大于answer的有多少个
    判定的大概过程就是把A排序后,一边从左向右枚举i,一边维护另一个j,保证
ai*aj > answer 。这个过程中j显然是单调的。
    要分正负具体讨论,实现起来应该有些复杂。

C:
    虽然是一个环,但可以分奇偶讨论,简单地证明有一条边是用不到的。
    所有枚举断开的那条边,这个问题就变成了一个线性的分配问题。
    这样只要每次从断开的边上的某个点出发,分配的方式也就固定了:
    考虑每条边对答案的贡献,显然就是这条边的两侧看做一个整体,考察他们的整体
供需关系如何。

D:
    用一下必要条件:鸽笼原理。于是可以发现,字符串最长的长度不超过7。(举个
例子,字符串长度为10^6时,那么长度为6的字符串在其中最多出现了10^6 - 7 + 1次,
但长度为6的字符串最多有10^7 - 10^6个,一定会出现重复。而在实际情况中,由于
字符串排列本身的限制条件,导致实际的最长长度还要低于7。 )
    于是直接O(N*7)的暴力枚举,开个exist数组记录即可。
    并且由于数据过于温暖,现场赛还有部分O(N * M)的复杂度的极为粗暴的算法也被
温柔地放过了。

E:
    题解较长,看群内共享。

F:
    用一下等比数列求和公式,发现最后结果为(A^X - 1) / (A - 1),因为题目中给出
的限制条件,gcd(A, M) = gcd(A-1, M) = 1,可以发现/(A - 1)可以处理成某个非0的
乘法逆元,并不影响结果。
    于是考虑X取何值时,A^X % M = 1。由欧拉定理可知,X = phi(M)时为一个可行
解。
    然后可以证明可行解一定是phi(M)的最小的非1的约数。(充分性显然,必要性
可以用反证法,假设存在一个比phi(M)更小的Y,满足A^Y % M == 1,且Y不能够整除
phi(M),那么相当于存在A^(phi(M) % Y) == 1, 而phi(M) % Y又必然小于Y,那么
那么递归下去直到Y=1时,发现矛盾 )
    现场赛时有位数院的同学用BSGS的方法过了这个题,虽然代码跑了30s,也还是被放
过了= =

G:
    判断是否为对角线的依据就是:把这条边所在的两个点删掉以后,整张图是否变成
两个不连通的部分。
    最后只保留非对角线的边,然后dfs一遍,求字典序最小的遍历。

H:
    题解较长,看群内共享。

I:
    根据拓扑关系建树。可以虚拟一个0节点作为根节点,即该节点处于所有无父亲节点
的前面。
    对于每个节点,满足了下面的所有拓扑关系之后,相当于形成了一段相对顺序固定的
子序列。
    例如u节点以下有三个子节点,其三个子节点v1,v2,v3所包含的子树的节点数分别为
2,3,4。而dp(v1), dp(v2), dp(v3)则分别表示v1, v2, v3以下所有拓扑关系全部满足时
的方案数。
    此时u显然是u这个子树中第一个出现在最后生成的子序列中的数,而v1, v2, v3则为
三个相对位置关系并不确定,内部关系已经确定的子序列。
    那么先把第一个子序列v1放下来,再把v2插进去,确定顺序之后,再把v3插进去。
    用组合公式表示就是
    dp[u] = dp[v1] * C( v1 + 1 + v2 - 1, v2 ) * dp[v2] * C( v1 + v2 + v3 + 1 - 1, v3 )
* dp[v3]。
    (这里用到可重复组合的公式,即有n个盒子,放入m个球,每个盒子可以放置任意多个球,
总方案数为C(n + m - 1, m)。)

J:
    略。












默认分类 | 引用(0) |
不指定 类别: 默认分类 | @ 2015/03/15 17:21 | 评论(0) | 阅读(1311)
A
    a和x必然有一个在10^6以内,枚举a或x到10^6的情况即可。

B
    二分搜索answer,然后判定乘积大于answer的有多少个
    判定的大概过程就是把A排序后,一边从左向右枚举i,一边维护另一个j,保证
ai*aj > answer 。这个过程中j显然是单调的。
    要分正负具体讨论,实现起来应该有些复杂。

C:
    虽然是一个环,但可以分奇偶讨论,简单地证明有一条边是用不到的。
    所有枚举断开的那条边,这个问题就变成了一个线性的分配问题。
    这样只要每次从断开的边上的某个点出发,分配的方式也就固定了:
    考虑每条边对答案的贡献,显然就是这条边的两侧看做一个整体,考察他们的整体
供需关系如何。

D:
    用一下必要条件:鸽笼原理。于是可以发现,字符串最长的长度不超过7。(举个
例子,字符串长度为10^6时,那么长度为6的字符串在其中最多出现了10^6 - 7 + 1次,
但长度为6的字符串最多有10^7 - 10^6个,一定会出现重复。而在实际情况中,由于
字符串排列本身的限制条件,导致实际的最长长度还要低于7。 )
    于是直接O(N*7)的暴力枚举,开个exist数组记录即可。
    并且由于数据过于温暖,现场赛还有部分O(N * M)的复杂度的极为粗暴的算法也被
温柔地放过了。

E:
    题解较长,看群内共享。

F:
    用一下等比数列求和公式,发现最后结果为(A^X - 1) / (A - 1),因为题目中给出
的限制条件,gcd(A, M) = gcd(A-1, M) = 1,可以发现/(A - 1)可以处理成某个非0的
乘法逆元,并不影响结果。
    于是考虑X取何值时,A^X % M = 1。由欧拉定理可知,X = phi(M)时为一个可行
解。
    然后可以证明可行解一定是phi(M)的最小的非1的约数。(充分性显然,必要性
可以用反证法,假设存在一个比phi(M)更小的Y,满足A^Y % M == 1,且Y不能够整除
phi(M),那么相当于存在A^(phi(M) % Y) == 1, 而phi(M) % Y又必然小于Y,那么
那么递归下去直到Y=1时,发现矛盾 )
    现场赛时有位数院的同学用BSGS的方法过了这个题,虽然代码跑了30s,也还是被放
过了= =

G:
    判断是否为对角线的依据就是:把这条边所在的两个点删掉以后,整张图是否变成
两个不连通的部分。
    最后只保留非对角线的边,然后dfs一遍,求字典序最小的遍历。

H:
    题解较长,看群内共享。

I:
    根据拓扑关系建树。可以虚拟一个0节点作为根节点,即该节点处于所有无父亲节点
的前面。
    对于每个节点,满足了下面的所有拓扑关系之后,相当于形成了一段相对顺序固定的
子序列。
    例如u节点以下有三个子节点,其三个子节点v1,v2,v3所包含的子树的节点数分别为
2,3,4。而dp(v1), dp(v2), dp(v3)则分别表示v1, v2, v3以下所有拓扑关系全部满足时
的方案数。
    此时u显然是u这个子树中第一个出现在最后生成的子序列中的数,而v1, v2, v3则为
三个相对位置关系并不确定,内部关系已经确定的子序列。
    那么先把第一个子序列v1放下来,再把v2插进去,确定顺序之后,再把v3插进去。
    用组合公式表示就是
    dp[u] = dp[v1] * C( v1 + 1 + v2 - 1, v2 ) * dp[v2] * C( v1 + v2 + v3 + 1 - 1, v3 )
* dp[v3]。
    (这里用到可重复组合的公式,即有n个盒子,放入m个球,每个盒子可以放置任意多个球,
总方案数为C(n + m - 1, m)。)

J:
    略。












默认分类 | 引用(0) |
不指定 类别: 默认分类 | @ 2015/03/08 19:52 | 评论(0) | 阅读(959)
陆敬浩
丁嘉辉
黄旷
祖赫良
陈碧荷
汪剑杰
王思锦
赵知非
周靖奇
郭银杰
刘叶
李潇洒
李俊波
陈谨莹
邓智源
舒时立
李笑薇
史斌华
黄简峰
杨子涵
赖铭
王雷
银钏君
惠紫卿
郭子庆
潘思因

PS:每个姓名对应一支队伍。请于下周周末按时参加现场赛。其余未晋级但有兴趣参赛的同学请于下周五之前法邮件到315842935[at]qq.com与我联系。
默认分类 | 引用(0) |
不指定 类别: 默认分类 | @ 2015/03/08 19:50 | 评论(0) | 阅读(962)
A:
  设n为三角形内球的总个数。
  当n % 3 = 0时,方法比较显然。
  当n % 3 = 1时,只要列以下几个不等式:
  设最后的答案为ans, a = n / 3
  ans <= R / a
  ans <= G / a
  ans <= B / a
  ans * 3 * a + ans * 1 <= R + G + B (想象一下,先把ans确定下来,再去判断能否产生合法解)

  于是ans的最大值显然。


B:
  背包问题,但是要先确定dp的转移拓扑序。
  然后观察两个题,假设i题比j题先做,那么交换一下两个题的顺序,只有满足 Bi * Cj < Bj * Ci 时答案会变得更优。
  于是根据这个关系排序,然后dp。

C:
  会不会有同学一边数字母数,一边吐槽呢 XD


D:  
  

  最优解中显然至少有一个字母从未被交换过。
  于是枚举这个未被交换的数字,然后再暴力算。

E:
  假设蛋糕周长为N
  先考虑一下必要条件:若来了K个客人,那么蛋糕显然需要每隔 N/K 个单位长度就要被切一刀。
  考虑N所有的约数,每2种切法显然只有在同一个地方开始切,可以使得两两之间循环节的契合度最高,也最省代价。
  于是依次枚举N的所有约数,在每个需要切的地方标记一下,最后统计代价总和。

F:  
  简单的分类讨论题。      


G:
  
  题解在群里。


默认分类 | 引用(0) |
不指定 类别: 默认分类 | @ 2015/03/03 22:27 | 评论(0) | 阅读(948)
    为了增强eming杯的趣味性,扩大比赛的影响力并且锻炼同学们的交流能力,今年的比赛制度将会作以下几点革新。

    1.比赛采取与ACM赛制相同的多人组队的形式,为了保证比赛的公平性,对组队做出如下限制:
        (1)参加寒假集训div1训练的同学,只能与至多两名未参加过集训的同学组队。
        (2)其他队伍至多由三人组成,且至多两位成员参加过寒假集训

    2.比赛题目将以代码题,中学数学以及小学数学奥数为主,保证不出现复杂的数据结构以及算法知识。

    3.可以携带任意的纸质资料。
  

    关于其他的比赛细则以及集训队的介绍,与往年相同,请同学们在本大赛主页上参考前几年的信息记录。

    网络赛时间:3月8日12:00至17:00,网址:http://acm.whu.edu.cn/land/contest/list

    现场赛时间:3月15日12:00至17:00 地址:计算机学院B303

    报名网址:http://eming.vipsinaapp.com/?

    报名已截止。比赛账号为15ee+"学号",密码为报名时的手机号。

    请每支队伍任选一位同学的账号统一交题。
    
    
默认分类 | 引用(0) |
不指定 类别: 默认分类 | xioumu @ 2013/12/15 23:30 | 评论(0) | 阅读(3889)
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.
下载文件 (已下载 272 次)
    
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:胜败乃兵家常事,我们明年再会!
默认分类 | 引用(0) |
分页: 1/20 第一页 1 2 3 4 5 6 7 8 9 10 下页 最后页 [ 显示模式: 摘要 | 列表 ]