用户登录:

用户名:
密码:      

文章分类:


最新评论:

userleijiankun 说:膜拜神牛。……
usercss 说:康拓展开和逆康拓展……
usersongrenchu 说:欢迎大家踊……
userAdmin 说:……

有道难题——5月24日练习赛非正式题解

发表时间:2010-05-24 22:26:57  浏览(2655) 评论(6)


  这套题总体来说非常水,但是第三题没有太大把握,实际上是恶搞出来的。

【Problem 1:A+B】
描述 
 计算a加b。 
输入 
 一行,用空格分开的两个整数a和b。
 其中0≤a, b≤10000。 
输出 
 一个整数,为a加b的和。 
样例输入 
 1 2
样例输出 
 3

[解法]不解释了,每每新开一个题站都刷掉的超级水题。

【Problem 2:Power】
描述 
 计算a的b次方对9907取模的值。 
输入 
 第一行有一个正整数T,表示有T组测试数据。
 接下来T行,每行是一组测试数据,包含两个整数a和b。
 其中T<=10000, 0 <=a,b < 2^31。 
输出 
 有T行,依次输出每组数据的结果。 
样例输入 
 3
 1 2
 2 3
 3 4
样例输出 
 1
 8
 81

[解法]快速幂乘法,连高精度都不用。复杂度O(T*Log(b))。

【Problem 3:Sibonacci】
描述 
 菲波那切数列可以用下列的式子表示:
 f(1)=1
 f(2)=1
 f(n)=f(n-1)+f(n-2) (n>=3)
 
 现在我们根据这个规则定义另一种数列 命名为"辛波那切数列", 它是这样定义的:
 s(x)=0 (x<0)
 s(x)=1 (0<=x<1)
 s(x)=s(x-1)+s(x-3.14) (x>=1)

 现在需要计算出s(x) MOD 1000000007的值。 
输入 
 第一行有一个正整数T表示有T组测试数据。
 接下来T行,每行包含一个数x。
 其中 T<=10000, -1000.0<=x<=1000.0 
输出 
 有T行,依次输出每组数据的结果。 
样例输入 
 3
 -1
 0.667
 3.15
样例输出 
 0
 1
 2

[解法]没想到特别好的算法,于是山寨了一下。默认S(x)是分段函数,且以0.01的整倍数为分界点,中间的函数值相同。于是将函数自变量扩大了1000倍取下整作为代表,开一个-1000000..1000000的数组xb,xb[i]=xb[i-1000]+xb[i-3140],然后读入数据x直接输出xb[trunc(x*1000)]。样例及一般数据没有问题,坐等测评结果。

【后记】作为有道难题系列比赛的练习赛,这套题的难度不大,总体上只是为了让大家熟悉该赛事的竞赛环境。顺便BS一下有道的测评平台,又慢又不灵敏,害我连续提交N次。且测评超慢,我开赛不到半小时就交了程序,2小时比赛时间到后仍然没有出结果。倒是很多后交的程序先出了成绩。诡异!

网友评论:

user1  boj 于 2010-05-30 18:04:33 说:回复
你参加那个有道难题了?
资格赛前两场怎么样?
user2  boj 于 2010-05-30 18:08:37 说:回复
刚查到SRC了,原来是下午比赛结束后才做的……
user3  boj 于 2010-05-30 18:16:08 说:回复
你第一场那个“最大和子序列”用的什么算法?
O(n^2)的应该不行吧。讨论区有说O(n)的,怎么办?请指教
user4  Guest 于 2010-05-30 22:14:23 说:回复
本人太菜了,连资格赛都没通过,一年不写程序的后果啊……一直WA到死都不知道哪错了
第三场第三题“火柴游戏”又不会了,请SRC神牛看一看怎么做。
user5  boj 于 2010-05-30 22:17:06 说:回复
刚才忘了登陆。我想弄个DP,但三次方复杂度,太高了。AC的程序时间MS都是几百ms级的,莫非自古华山一条路??
user6  Admin 于 2010-05-30 23:26:04 说:回复
回复boj:前两场满分,罚时多了点。第三次前两题AC,第三题TLE了,正在想方法中。题解想等搞出来第三题后一起发。

Guest 发表评论