95 条题解
-
0
notblack LV 10 @ 2009-09-02 22:09:59
这题真是卡时间又卡空间....
时间上因为
F[N]=F[N div 2]+F[N div 2 -1]+...+F[1]
当你很兴奋地想要开3000000的数组，和N^2的算法。那你还是去睡觉吧。我们必须找到一些优化。
当N=2*i+1时，F[N]=F[N-1].
当N=2*i时，F[N]=F[N-1]+F[N div 2].
这样就达到O(n)的时间。而且当N=2*i+1时，F[N]=F[N-1]. 也就是数组里一半的数是相同的，所以我们只要开1500000的数组就可以了，不然MLE等着你。
最好加上压位高精，不加能不能过我也没试。
另外不要兴奋过度，因为有多组数据，否则就是“格式错误”等你啦。
其实几组数据都无所谓，我们一不做二不休全部算出来，然后读表就可以了。核心代码就这么短，再写个高精加法就AC了！
f[0][0]:=1; f[0][1]:=1;
for i:=1 to maxn do add(f,f[i shr 1],f[i]); -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 9ms
├ 测试数据 03：答案正确... 9ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：18ms啊，AC 啦！
天啊，地啊~~~~~~~~总结一下（楼下大牛们的题解）：
1. 高精不用说了，压9位，数组开1500000*7
2. 因为2*k与2*k+1的值相同（自己先算出前几个的值，就可以找到规律）
f[0]:=1;
f[i]:=f+f[i shr 1];
这里的i代表偶数，输出时只要输出n shr 1，推的时候只推偶数值，具体看程序程序：
const maxn=1500001;
th=1000000000;
type arr=array[0..7] of longint;
var
f:array[0..maxn] of arr;
n,i,max:longint;procedure add(var s:arr;a,b:arr); //高精加
var i,sum,t:longint;
begin
i:=1;
t:=0;
while (i -
0
-
0
LP.Fighting LV 10 @ 2009-08-16 19:02:26
我X...
压8位...存一半...不然内存溢出...
难怪通过率那么低...
f[i]=f+f[i div 2] -
0
编译通过...
├ 测试数据 01：答案正确... 150ms
├ 测试数据 02：答案正确... 25ms
├ 测试数据 03：答案正确... 150ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：325ms第一次 开了个3000000*50的数组交上去 运行超时
然后再次提交 还是不行....第二次 想了想 其实我还是做麻烦了f[i]:=1+f[i div 2]+f[i div 2-1]+..f[1]
其实可以改成f[i]:=f
if i是偶数 then f[i]:=f[i]+f[i div 2]
提交 还是错了...第三次
后来看了看楼下们的题解
因为第2*i个与2*i+1个是相等的 数组可以压缩一半
又发现要高精压9位（偶滴神啊！！！！）
就这样把数组压到 1500000*7总算过了 呼呼(～ o ～)~zZ
-
0
ufo172849z LV 10 @ 2009-08-03 21:40:55
此题看来不能交打表程序，一个裸的case要83.4MB。
预处理然后直接输出吧。 -
0
zhouliecheng LV 10 @ 2009-07-25 08:52:44
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 119ms
├ 测试数据 03：答案正确... 103ms
这是dragon...
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 41ms
这是puppy....靠...活活被急死...
notblack
LV 10
@ 2009-09-02 22:09:59
