hdu 1316不知为何wa
这道题我测试了很多数据，都是正确的，但交上去就是wa！无法理解，还请各位不吝赐教。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MAX 320
using namespace std;
int Fib[501][MAX+1];
void makeFib(void);
void addFib(int *,int *,int *);
//void outputFib(int pi);
int cmpArray(int *,int *);
int findIndex1(int *);
int findIndex2(int *);
int main(){
char a[MAX+1],b[MAX+1];
int arr1[MAX+1],arr2[MAX+1],i;
makeFib();
memset(arr1,0,sizeof(arr1));
memset(arr2,0,sizeof(arr2));
//*
while((scanf("%s%s",a,b))!=EOF && !(a[0]=='0' && b[0]=='0') ){
for(i=0;i<strlen(a);++i)
arr1[i]=a[i]-'0';
arr1[MAX]=strlen(a);
for(i=0;i<strlen(b);++i)
arr2[i]=b[i]-'0';
arr2[MAX]=strlen(b);
int index2=findIndex2(arr2),index1=findIndex1(arr1);
if(index2==1)
index2+=1;
printf("%d\n",index2-index1);
memset(arr1,0,sizeof(arr1));
memset(arr2,0,sizeof(arr2));
}
//*/
return 0;
}
void makeFib(void ){
int i,j;
for(i=0;i<=500;++i){
for(j=0;j<=MAX;++j)
Fib[i][j]=0;
}
Fib[1][MAX]=Fib[2][MAX]=1;
Fib[1][0]=Fib[2][0]=1;
for(i=3;i<=500;++i){
addFib(Fib[i-2],Fib[i-1],Fib[i]);
}
}
void addFib(int *arr1,int *arr2,int *res){
int i,len;
for(i=1;i<=MAX && !arr2[i];++i);
len=i;
for(i=MAX;i>=len;--i){
res[i]+=arr1[i]+arr2[i];
if(res[i]>=10){
res[i]-=10;
res[i-1]+=1;
}
}
//Fib[i][0]存储数字长度信息
res[0]=res[i]?MAX-i+1:MAX-i;
}
/*用来测试是否正确生成了 Fibonacci数，对本题无用
void outputFib(int pi){
int len,i;
for(i=0;i<=MAX && !Fib[pi][i];++i);
for(;i<=MAX;++i){
printf("%d",Fib[pi][i]);
}
printf("\n");
}
*/
int cmpArray(int *target,int *stable){
int tlength=target[0],slength=stable[MAX],i,j;
if(tlength>slength)
return 1;
else if(tlength<slength)
return -1;
else{
for(i=MAX-tlength+1,j=0;j<slength;++i,++j){
if(target[i]>stable[j])
return 1;
else if(target[i]<stable[j])
return -1;
}
return 0;
}
}
/*
int findIndex1(int *data){
int low,high,mid,tmp;
low=1,high=500;
while(low<=high){
mid=(low+high)/2;
tmp=cmpArray(Fib[mid],data);
if(tmp==1)
high=mid-1;
else if(tmp==-1)
low=mid+1;
else
return mid-1;
}
return high;
}
int findIndex2(int *data){
int low,high,mid,tmp;
low=1,high=500;
while(low<=high){
mid=(low+high)/2;
tmp=cmpArray(Fib[mid],data);
if(tmp==1)
high=mid-1;
else if(tmp==-1)
low=mid+1;
else
return mid;
}
return high;
}
*/
//前面是二分搜索，后面是顺序搜索
int findIndex1(int *data){
int i,tmp;
for(i=1;i<=500;++i){
tmp=cmpArray(Fib[i],data);
if(tmp==0 || tmp==1)
return i-1;
}
}
int findIndex2(int *data){
int i,tmp;
for(i=1;i<=500;++i){
tmp=cmpArray(Fib[i],data);
if(tmp==0 )
return i;
if(tmp==1)
return i-1;
}
}
[解决办法]
1 1
字数补丁
