dingpwen程序的优化,如果他的程序能通过的话不这么做也无所谓.
#include <iostream>
using namespace std;
#define MAXN 1018
int main()
{
long a[MAXN];
int n;
//预处理
a[0] = 0;
a[1] = 1;
for(int i=2; i<MAXN; i+=2)
{
int k = i/2;
a[i] = a[k];
a[i+1] = a[k] + a[k+1];
}
while(cin>>n) cout<<a[n]<<endl;
return 0;
}
再问： 不好意思，数据给错了，n是10的18次方，不是1018,1018的话，这个题就不是ACM的题目了
再答： 不知道ACM允不允许使用__int64数据类型，这个数据类型刚好够10^18，如果可以用可以试试下面的代码，如果不能ac的话就要考虑有没有数学方法了。。#include <iostream>
using namespace std;
__int64 seq(__int64 n)
{
if(n==0) return 0;
else if(n==1) return 1;
else if(n%2==0) return seq(n/2);
else return seq(n/2)+seq(n/2+1);
}
int main()
{
__int64 n;
while(cin>>n) cout<<seq(n)<<endl;
return 0;
} 哦，我是防止万一把seq函数的返回值给了个__int64，如果序列中的结果连long都没达到的话，这里改成int就行了，由于用的递归，虽然给了128M空间，但防止万一还是尽量用小一点的数据结构 如果不能用__int64的话就用数组来模拟大数运算 ---------测试了下貌似大数还是会超时。。。我再看下
再问： 可以用，但还是超时，这个谁都知道，我的做法是先打出1000000以内的，然后递归的时候只递归到1000000以内，明显减少了很多时间，可是依然超时，望指教
再答： 嗯 稍等 好像有数学方法 结果是有规律的 我正在看
再问： 好的，谢谢你
再答： #include <iostream>
using namespace std;
int main()
{
__int64 n;
while(cin>>n)
{
if(n==0)
{
cout << 0 << endl;
continue;
}
else if(n==1)
{
cout << 1 << endl;
continue;
}
// 把行k计算出来并找到对应行元素位置
int k = 0; //k<60
__int64 l = 2, r = 4;
while(r < n)
{
k++;
l = l * 2;
r = r * 2;
}
__int64 pos = n - l;
__int64 len = r - l + 1;
//如果位置处于后半，则计算对应前半的位置
if(pos > (len / 2)) pos = len - pos - 1;
if(pos == 0)
{
cout<<1<<endl;
continue;
}
//开始按规律处理
__int64 vall, valr, posl, posr;
vall = valr = 1;
posl = 0;
posr = len - 1;
__int64 bpos = len / 2;
__int64 bval = vall + valr;
while(bpos != pos)
{
if(pos < bpos)
{
valr = bval;
posr = bpos;
}
else if(pos > bpos)
{
vall = bval;
posl = bpos;
}
bpos = (posl + posr) / 2;
bval = vall + valr;
}
cout<<bval<<endl;
}
return 0;
} 不知道为什么提交会报编译错误。。我这里可以执行啊超过了字数限制，你回复一下我把原理贴出来
再问： 好的！！！！
再答： 求出前面的一些数看一下的话： 0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13 8 11 3 10 7 11 4 9 5 6 1 ... 除去a[0]和a[1]看剩下的： 0 1 //a[0]-a[1]，第k=0行，不符合规律 1 2 1 //a[2]-a[4]，第k=1行 1 3 2 3 1 //a[4]-a[8]，第k=2行 1 4 3 5 2 5 3 4 1 //a[8]-a[16]，第k=3行 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 //a[16]-a[32]，第k=4行 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13 8 11 3 10 7 11 4 9 5 6 1 //a[32]-a[64]，第k=5行 ...... 令数组b保存着上述第k行里的数据，仔细观察数组b发现如下规律： [1] 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 [2] 9 7 12 5 13 8 11 3 10 7 11 4 9 5 6 [1] 首先数组关于中心的2对称，且2=1+1 现在我们只看左半部分： [1] 6 5 9 4 11 7 10 [3] 11 8 13 5 12 7 9 [2] 3在1和2正中间，且3=1+2 [1] 6 5 9 [4] 11 7 10 [3] 11 8 13 5 12 7 9 [2] 4在1和3正中间，且4=1+3 [1] 6 5 9 [4] 11 7 10 [3] 11 8 13 [5] 12 7 9 [2] 5在3和2正中间，且5=3+2 .... 规律不用我说了吧 由于由数组a转数组b数据量至少减少一半 然后数组b只看一半，数据量又减少一半 最后又是二分，速度应该是很快的
再问： 网上提交的那些ce的是你吗？ 我用你的程序提交过了，这是代码 你把__int64改为longlong就可以了 我先看看你的规律
再答： ac了吗，说实话竞赛题我已经有好多年没做过了。。手都生了。。
