poj1840 哈希

虽然这题目我曾经在我们学校OJ上做过但是我那时候是用的暴力做的,这次我用的是哈希写的,我写这题目时候开始是在main函数里面写哈希感觉很麻烦很不清晰,然后我换用函数来写,清晰了很多,写完就AC了。用哈希存储前两项的值,然后遍历后三项再去哈希表中寻找这个值在前两项中出现的次数,加起来就OK了。

 #include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define aabs(x) (x)>0?(x):-(x)
#define mod 999983
#define t(x) (x)*(x)*(x)
struct node{
int num;
node *next;
int cnt;
}p[mod];
int sign[mod]; void hash(int res){
int key;
key=(aabs(res)) % mod;
node *op;
if(sign[key]==){
p[key].num=res;
p[key].cnt++;
p[key].next=NULL;
sign[key]=;
return;
}else if(sign[key]==){
op=&p[key];
while(){
if(res==op->num){
op->cnt++;
return ;
}
if(op->next!=NULL){
op=op->next;
}else break;
}
}
node *tmp=(node *)malloc(sizeof(node));
tmp->num=res;
tmp->cnt=;
tmp->next=NULL;
op->next=tmp;
return;
}
int find_hash(int res){
int cnt=;
int key=(aabs(res)) % mod;
if(sign[key]==){
return ;
}else if(sign[key]==){
node *op=&p[key];
while(){
if(res+op->num==){
cnt=op->cnt;
}
if(op->next!=NULL){
op=op->next;
}else break;
}
}
return cnt;
} void init(){
memset(sign,,sizeof(sign));
for(int i=;i<mod;++i){
p[i].next=NULL;
p[i].cnt=;
}
return ;
} int main(){
int a1,a2,a3,a4,a5,x1,x2,x3,x4,x5;
int i,j,key;
int res,cnt;
while(~scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5)){
cnt=;
init();
for(x1=-;x1<=;++x1){
for(x2=-;x2<=;++x2){
if(x1==||x2==) continue;
res=(t(x1))*a1+(t(x2))*a2;
hash(res);
}
} for(x3=-;x3<=;++x3)
for(x4=-;x4<=;++x4)
for(x5=-;x5<=;++x5){
if(x3==||x4==||x5==) continue;
res=t(x3)*a3+t(x4)*a4+t(x5)*a5;
cnt+=find_hash(res);
}
printf("%d\n",cnt);
}
return ;
}
上一篇:以上帝模式管理Windows系统


下一篇:UE4中的集合:TSet容器