题目大意:
对于给定的a1,a2,a3,a4,a5[-50,50]。让你求出方程a1·x1^3+a2·x2^3+a3·x3^3+a4·x4^3+a5·x5^3=0的解([-50,50]范围内)的个数。
思路:
对于给定的a1,a2,a3,a4,a5[-50,50]。让你求出方程a1·x1^3+a2·x2^3+a3·x3^3+a4·x4^3+a5·x5^3=0的解([-50,50]范围内)的个数。
思路:
如果只是简单地枚举范围内的所有的数,那么,100^5=10^10肯定是超时了。优化方法:用列表法首先写出x^3的所有可能值(100个),再求出所有a1·x1^3 + a2·x2^3+ a3·x3^3的可能值(n^3),并排序(n^3)*(log(n^3))。和所有a4·x4^3+ a5·x5^3的可能值(n^2),然后枚举所有a4·x4^3+ a5·x5^3的可能值,二分查找a1·x1^3 + a2·x2^3+ a3·x3^3的可能值中是否存在对应解(n^2)*(log(n^3))。
总时间复杂度为:(n^3)(log(n^3))。
然后写到一半发现,二分还是慢,哈希表更快,而且不需要排序,只需要O(n^3)。
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#define N 110
#define MOD 1000000
using namespace std;
int a[6]={0};
int x[N]={0};
int s[N*N*N]={0};
int hash[N*N*N]={0};
int next[N*N*N]={0};
/*int find(int x)
{
int ss=0;
for(int i=0;i<=MOD;i++)
{
if(x==s[i])ss++;
}
return ss;
}*/
int my_find(int x)
{
int u=(((long long)x*(long long)x)%MOD)+1;
u=hash[u];
int z=0;
while(u)
{
if(s[u]==x)
{
z++;
}
u=next[u];
}
return z;
}
void ceshi()
{
for(int i=0;i<1000000;i++)
{
cout<<hash[i]<<" ";
}
}
int main()
{
int n=0;
for(int i=-50;i<=50;i++)
{
if(i==0)continue;
x[n]=i*i*i;
n++;
}
for(int i=1;i<=5;i++)cin>>a[i];
int l=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
{
int v=0;
s[l]=a[1]*x[i]+a[2]*x[j]+a[3]*x[k];
v=((long long)s[l]*(long long)s[l])%MOD+1;
next[l]=hash[v];
hash[v]=l;
l++;
}
}
}
int sum=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int t=a[4]*x[i]+a[5]*x[j];
sum=sum+my_find(-t);//在s数组中查找是否有-t.
}
}
//ceshi();
cout<<sum;
}