Posted on 2012-01-30 01:40
C小加 阅读(1592)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
哈希。把
a1*x13+a2*x23的所有情况存储在哈希表中，然后用a3*x3
3+a4*x4
3+a5*x5
3去表中查找和为0的情况。用数组暴力的话会超内存。
这个题很久以前做过，虽然AC了但是错的。之前做的时候觉得有一组数据超int了（老是RE），而且当时认为只有这一组数据超了，所以当时就把这组数据进行特殊化处理了。后来小牛找出了问题我才意识到根本没有超出int，我去掉特殊化处理后提交TLE，不是RE，我开始纠结当时到底是怎么做的。
我重新检查了一遍代码，发现我的哈希算法加上那组特殊数据，时间复杂度O（n*m），n达到100万，m达到1万。这时间伤不起啊。后来想想哈希还可以优化，于是我就改了一下哈希算法，复杂度降低到了O（n），最终也顺利AC。
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
const int MAX=100003;
const int MAXSUM=12500000;
int a[1003];
void g()
{
for(int i=-50;i<=50;i++)
{
a[i+50]=i*i*i;
}
}
template <class T>
class hash
{
private:
int pos;
int next[MAX];
int head[MAX];
int key[MAX];
int cnt[MAX];
public:
int count;
void search(const int x);
bool search1(const int x);
void push(const int x);
void clear();
};
template <class T>
inline bool hash<T>::search1(const int x)
{
int temp=abs(x)%MAX;
int t=head[temp];
while(t!=-1)
{
if (x==key[t])
{
cnt[t]++;
return true;
}
t=next[t];
}
return false;
}
template <class T>
inline void hash<T>::search(const int x)
{
int temp=abs(x)%MAX;
int t=head[temp];
while(t!=-1)
{
if (x==-key[t])
{
count+=cnt[t];
}
t=next[t];
}
}
template <class T>
inline void hash<T>::push(const int x)
{
if(search1(x)) return;
int temp=abs(x)%MAX;
if (head[temp]!=-1)
{
next[pos]=head[temp];
}
head[temp]=pos;
key[pos]=x;
cnt[pos]=1;
pos++;
}
template <class T>
void hash<T>::clear()
{
count=0;
pos=0;
memset(next,-1,sizeof(next));
memset(head,-1,sizeof(head));
memset(cnt,0,sizeof(cnt));
}
hash<int> h;
int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
memset(a,0,sizeof(0));
g();
while(T--)
{
h.clear();
int a1,a2,a3,a4,a5;
int i,j,k;
int n;
scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5);
for(i=-50;i<=50;i++)
{
for(j=-50;i!=0&&j<=50;j++)
{
if(j==0) continue;
n=a1*a[i+50]+a2*a[j+50];
h.push(n);
}
}
for(i=-50;i<=50;i++)
{
for(j=-50;i!=0&&j<=50;j++)
{
for(k=-50;j!=0&&k<=50;k++)
{
if(k==0) continue;
n=a3*a[i+50]+a4*a[j+50]+a5*a[k+50];
if(n > MAXSUM || n < -MAXSUM)
continue;
h.search(n);
}
}
}
printf("%d\n",h.count);
}
return 0;
}