有道难题——5月24日练习赛非正式题解
发表时间：2010-05-24 22:26:57 浏览(7699) 评论(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了，正在想方法中。题解想等搞出来第三题后一起发。 |