Posted on 2012-01-30 01:40
C小加 閱讀(1605)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告
哈希。把
a1*x13+a2*x23的所有情況存儲在哈希表中，然后用a3*x3
3+a4*x4
3+a5*x5
3去表中查找和為0的情況。用數(shù)組暴力的話會超內(nèi)存。
這個題很久以前做過，雖然AC了但是錯的。之前做的時候覺得有一組數(shù)據(jù)超int了（老是RE），而且當(dāng)時認(rèn)為只有這一組數(shù)據(jù)超了，所以當(dāng)時就把這組數(shù)據(jù)進(jìn)行特殊化處理了。后來小牛找出了問題我才意識到根本沒有超出int，我去掉特殊化處理后提交TLE，不是RE，我開始糾結(jié)當(dāng)時到底是怎么做的。
我重新檢查了一遍代碼，發(fā)現(xiàn)我的哈希算法加上那組特殊數(shù)據(jù)，時間復(fù)雜度O（n*m），n達(dá)到100萬，m達(dá)到1萬。這時間傷不起啊。后來想想哈希還可以優(yōu)化，于是我就改了一下哈希算法，復(fù)雜度降低到了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;
}