有道难题——5月24日练习赛非正式题解
发表时间:2010-05-24 22:26:57 浏览(7656) 评论(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小时比赛时间到后仍然没有出结果。倒是很多后交的程序先出了成绩。诡异!
【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小时比赛时间到后仍然没有出结果。倒是很多后交的程序先出了成绩。诡异!
网友评论:
1 boj 于 2010-05-30 18:04:33 说: | 回复 | |
---|---|---|
你参加那个有道难题了?
资格赛前两场怎么样? | ||
2 boj 于 2010-05-30 18:08:37 说: | 回复 | |
刚查到SRC了,原来是下午比赛结束后才做的…… | ||
3 boj 于 2010-05-30 18:16:08 说: | 回复 | |
你第一场那个“最大和子序列”用的什么算法?
O(n^2)的应该不行吧。讨论区有说O(n)的,怎么办?请指教 | ||
4 Guest 于 2010-05-30 22:14:23 说: | 回复 | |
本人太菜了,连资格赛都没通过,一年不写程序的后果啊……一直WA到死都不知道哪错了
第三场第三题“火柴游戏”又不会了,请SRC神牛看一看怎么做。 | ||
5 boj 于 2010-05-30 22:17:06 说: | 回复 | |
刚才忘了登陆。我想弄个DP,但三次方复杂度,太高了。AC的程序时间MS都是几百ms级的,莫非自古华山一条路?? | ||
6 Admin 于 2010-05-30 23:26:04 说: | 回复 | |
回复boj:前两场满分,罚时多了点。第三次前两题AC,第三题TLE了,正在想方法中。题解想等搞出来第三题后一起发。 |