SPOJ 4580 ABCDEF

给一个大小于100的集合S
求满足下两式的六元组个数。。


d!=0。。。
化一下,a*b+c=(e+f)*d。。
现用Hash把所有efd枚举一下,Hash存下结果。。
然后枚举abc就OK了。。
O(n^3)
这提示我一般的找个数的题目,如果适当Hash都可以降低复杂度。。。
Code:
#include<cstdio>
#include<cstring>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int size=100007;
class Hash
{
struct node
{
int x,s;
node*next;
}*H[size],Data[1000000],*Now;
node* new_node(int x,int s,node*n)
{
Now->x=x;Now->s=s;Now->next=n;
return Now++;
}
int Code(int x)
{
if(x<0)x=-x;
return x%size;
}
public:
Hash()
{
Now=Data;
memset(H,0,sizeof(H));
}
void ins(int x)
{
int h=Code(x);
for(node*p=H[h];p;p=p->next)
if(p->x==x)
{p->s++;return;}
node*q=new_node(x,1,H[h]);
H[h]=q;
}
int find(int x)
{
int h=Code(x);
for(node*p=H[h];p;p=p->next)
if(p->x==x)
return p->s;
return 0;
}
};
class solve
{
int n,A[100];
void init()
{
scanf("%d",&n);
REP(i,n)
scanf("%d",A+i);
}
void work()
{
Hash H;
REP(i,n)REP(j,n)REP(k,n)if(A[k])
H.ins((A[i]+A[j])*A[k]);
int ans=0;
REP(i,n)REP(j,n)REP(k,n)
ans+=H.find(A[i]*A[j]+A[k]);
printf("%dn",ans);
}
public:
solve()
{
init();
work();
}
};
int main()
{
solve now;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>