注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

北京冬令营Day1试题、算法  

2012-01-17 21:04:33|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
今天是来自北京航天航空大学的杨博洋出的题。

2012 年 北京市信息学竞赛冬令营
一试
好好学习,天天向上
题目名称 源代码文件 输入文件 输出文件 数据组数 总分
算不出的等式 calculator.* calculator.in calculator.out 10 100
最多的方案 fib.* fib.in fib.out 10 100
连连看 clear.* clear.in clear.out 10 100
算不出的算式
背景:
曾经有一个老掉牙的游戏放在我面前 , 我没有珍惜 。 直到这个
游戏停产才追悔莫及 。 人世间最痛苦的事情莫过于此 , 如果上天给我
一个再玩一次的机会,我一定要,通关!
题目描述:
如果你真的很想玩这个游戏,那么就先看看我的题目吧,搞不定
这些的话是没办法通关的哟 。 第一关其实很简单 , 只有一个关闭的有
密码锁的大门 。 这大门上写着一个奇怪的算式 , 估计是要你利用它算
出密码来开门吧(果然是老掉牙的情节 ) 。
传说中这个式子中的 p 和 q 是两个奇质数,等号右边算出来应该
就是密码了吧,你是真的算不出来么?
sum([int(k*p/q) for k in range(1,(q+1)/2)])+sum([int(k*q/p) for k in range(1,(p+1)/2)])
输入:
只有一行,两个奇质数,分别表示 p,q 。
输出:
一个数 , 表示算式结果。
样例输入:
5 7
样例输出:
6
HINT:p,q 在 32 位整型范围内。

最多的方案
题目描述:
第二关和很出名的斐波那契数列有关 , 地球上 的 OIe r 都知道 : F 1 =1,
F 2 =2, F i = F i-1 + F i-2 , 每一项都可以称为斐波那契数 。 现在给一个正整 数
N ,它可以写成一些斐波那契数的和的形式。如果我们要求不同的方
案中不能有相同的斐波那契数 , 那么对一个 N 最多可以写出多少种方
案呢?
输入:
只有一个整数 N 。
输出:
一个方案数
样例输入:
16
样例输出:
4
Hint : 16=3+13=3+5+8=1+2+13=1+2+5+8
对于 30% 的数据, n<=256
对于 100% 的数据, n<=10^18

连连看
题目描述:
凡是考智商的题里面总会有这么一种消除游戏。不过现在面对的
这关连连看可不是 QQ 游戏里那种考眼力的游戏。我们的规则是 , 给
出一个闭区间 [a,b] 中的全部整数,如果其中某两个数 x,y (设 x>y ) 的
平方差 x 2
-y 2
是一个完全平方数 z 2
, 并且 y 与 z 互质 , 那么就可以将 x
和 y 连起来并且将它们一起消除 , 同时得到 x+y 点分数 。 那么过关的
要求就是 , 消除的数对尽可能多的前提下 , 得到足够的分数 。 快动手
动笔算一算吧。
输入:
只有一行,两个整数,分别表示 a,b 。
输出:
两个数,可以消去的对数,及在此基础上能得到的最大分数。
样例输入:
1 15
样例输出:
2 34
对于 30% 的数据, 1<=a,b<=100
对于 100% 的数据, 1<=a,b<=1000


得分什么的我没有统计清楚,我知道:
300:两个(标程+范浩强)
200+:一些(罗剑桥260分)
100+:很多
0+:大部分

算法呢?
第一题:经典题。可以用超级扩展欧几里德。
最牛的方法是直接套公式:
(p-1)(q-1)/4      p!=q
(p*p-1)/4            p=q
第二题:记忆化暴搜。
开个map,从大到小进行dfs即可。注意:要剪枝(若剩下的数加起来也不够,果断return)。
第三题:最大匹配。
莫名其妙地,如果能消去就把两个数之间连一条边,那么这是一个二分图!
于是,KM即可。

这些题我2个小时左右写完了,看了一会儿英语阅读。数据稍微有点问题,不过最后改过来了。
人大附中的孩子表现基本还行。
薛钟行威武!祝福他。
  评论这张
 
阅读(1959)| 评论(23)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017