刚开始想都不用想用了暴力 当然超时。
根据题目要求10000k内存
一般64m内存即可以通过
利用hash函数建立，时间通过。但内存超出了。。。代码1
1 2 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 short hash1[25000010]; //存放hash函数的对应关系的数据 8 9 int main() 10 { 11 int a[5],t; 12 int temp; 13 long long sum; 14 scanf("%d",&t); 15 while(t--) 16 { 17 sum=0; 18 memset(hash1,0,sizeof(hash1)); 19 for(int i=0;i<5;i++) 20 scanf("%d",a+i); 21 for(int i=-50;i<=50;i++) 22 { 23 if(i==0) 24 continue; 25 for(int j=-50;j<=50;j++) 26 { 27 if(j==0) continue; 28 temp=a[0]*i*i*i+a[1]*j*j*j; 29 if(temp<0) 30 temp+=25000001; 31 hash1[temp]++; 32 } 33 } 34 for(int i=-50;i<=50;i++) 35 { 36 if(i==0) continue; 37 for(int j=-50;j<=50;j++) 38 { 39 if(j==0) continue; 40 for(int z=-50;z<=50;z++) 41 { 42 if(z==0) continue; 43 temp = -(a[2]*i*i*i+a[3]*j*j*j+a[4]*z*z*z); 44 if(temp<0) 45 temp+=25000001; 46 if(temp>=0&&temp<25000001) 47 sum+=hash1[temp]; 48 } 49 } 50 } 51 printf("%d\n",sum); 52 } 53 return 0; 54 } 55 56 57
处理冲突使用链地址法代码2
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<string.h> 6 #include<stdlib.h> 7 #include<algorithm> 8 #include<map> 9 using namespace std; 10 const int p = 19373; 11 const int a = 2* 50*50*50*50; 12 typedef struct Node 13 { 14 int value,num; 15 struct Node * next; 16 }node; 17 node * res[p];//结构体指针数组 18 int main() 19 { 20 int T,x1,x2,x3,x4,x5,a1,a2,a3,a4,a5; 21 int i ,j,k; 22 //node* res[p]; 23 for(i = 0; i < p; i++) 24 res[i] = new node;//创建哈希点 25 while(cin>>T) 26 { 27 while(T--) 28 { 29 int t ,x; 30 for(i = 0; i< p; i++)//哈希点初始化 31 { 32 res[i]->next = NULL; 33 res[i]->num = 0; 34 } 35 cin>>a1>>a2>>a3>>a4>>a5; 36 for(i = -50;i <= 50 ; i++)//枚举x1，x2 37 { 38 if(i == 0)continue;//注意 所有的x 不能为0 39 for(j = -50; j <= 50; j++) 40 { 41 if(j == 0) continue; 42 x = a1*i*i*i + a2*j*j*j; 43 int sum = x >= 0?x:-x;//取模要用绝对值 44 sum %= p; 45 node* p1;//这个地方注意不要开成节点了，下面会让它指向哈希点下一个位置，指针就行了，不然会超内存 46 node* p2 = new node;// 47 p1 = res[sum]->next; 48 int flag = 0; 49 while(p1)//沿着哈希点找，如果找到就标记flag = 1，找不到就把这个数插进去 50 { 51 if(p1->value == x) 52 { 53 flag = 1; 54 p1->num++; 55 delete p2; 56 break; 57 } 58 p1 = p1->next; 59 } 60 if(!flag)//没有找到，用p2 保存这个数的信息，插入到哈希表中 61 { 62 p2->value = x; 63 p2->num= 1; 64 p2->next = res[sum]->next; 65 res[sum]->next = p2; 66 } 67 } 68 } 69 long long ans =0; 70 for(i = -50; i <= 50; i++) 71 { 72 if(i == 0) continue; 73 for(j = -50; j <= 50; j++) 74 { 75 if(j == 0) continue; 76 for(k = -50; k <= 50; k++) 77 { 78 if(k == 0) continue; 79 x = a3*i*i*i + a4*j*j*j + a5*k*k*k; 80 int sum = x >0? x:-x; 81 if(sum > a) continue;//优化的地方，如果大于 a 就不用找了 82 sum %= p; 83 84 node* p1 = res[sum]->next; 85 while(p1) 86 { 87 if(p1->value == -x) 88 { 89 ans += p1->num; 90 break; 91 } 92 else 93 p1 = p1->next; 94 } 95 96 } 97 } 98 } 99 cout<<ans<<endl; 100 } 101 } 102 return 0; 103 }
最优代码：
1 2 #include<iostream> 3 #include<algorithm> 4 #include<cstdio> 5 #define N 101 6 7 using namespace std; 8 9 int A[N*N],B[N*N],C[N],len1,len2,len3; 10 11 bool cmp(int x,int y) 12 { 13 if(x>y) return true; 14 return false; 15 } 16 17 void work() 18 { 19 int i,j,k,key; 20 sort(A,A+len1); 21 sort(B,B+len2,cmp); 22 long long ans=0; 23 for(k=0;k<len3;k++) 24 { 25 key=-C[k]; 26 i=0;j=0; 27 while(i<len1&&j<len2) 28 { 29 if(key>A[i]+B[j]) i++; 30 else if(key<A[i]+B[j]) j++; 31 else 32 { 33 int p,q; 34 p=q=1; 35 while(A[i]==A[i+1]&&i+1<len1){p++;i++;} 36 while(B[j]==B[j+1]&&j+1<len2){q++;j++;} 37 ans+=p*q; 38 i++;j++; 39 } 40 } 41 } 42 cout<<ans<<endl; 43 } 44 45 int main() 46 { 47 int test,a1,a2,a3,a4,a5,x1,x2,x3,x4,x5; 48 scanf("%d",&test); 49 while(test--) 50 { 51 scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5); 52 len1=0; 53 for(x1=-50;x1<=50;x1++) 54 { 55 if(x1==0) continue; 56 for(x2=-50;x2<=50;x2++) 57 { 58 if(x2==0) continue; 59 A[len1++]=a1*x1*x1*x1+a2*x2*x2*x2; 60 } 61 } 62 len2=0; 63 for(x3=-50;x3<=50;x3++) 64 { 65 if(x3==0) continue; 66 for(x4=-50;x4<=50;x4++) 67 { 68 if(x4==0) continue; 69 B[len2++]=a3*x3*x3*x3+a4*x4*x4*x4; 70 } 71 } 72 len3=0; 73 for(x5=-50;x5<=50;x5++) 74 { 75 if(x5==0) continue; 76 C[len3++]=a5*x5*x5*x5; 77 } 78 work(); 79 } 80 return 0; 81 }