poj3274 哈希

时间:2022-06-25 14:49:37

这题终于让我AC了,其过程之艰辛我不想再回忆了,看了各种代码,一定要注意指针空和非空的问题,再一个要注意边界。

 #include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define mod 9967
int gird[+][];
int K;
int cmp(int a,int b){
int i;
for(i=;i<K;++i){
if(gird[a][i]!=gird[b][i])
return ;
}
return ;
}
void change(int num,int cnt){
int CNT=;
while(num){
gird[cnt][CNT++]=num%;
num=num/;
}
for(int i=;i<K;++i)
gird[cnt][i]+=gird[cnt-][i];
for(int i=;i<K;++i){
gird[cnt][i]-=gird[cnt][];
}
gird[cnt][]=;
return;
}
int sign[mod];
struct node{
node *next;
int pos;
}p[mod];
int main(){
int n,i,j;
int mmax;
int value;
int ttt;
while(~scanf("%d%d",&n,&K)){
memset(gird,,sizeof(gird));
memset(sign,,sizeof(sign));
node *tmp;
node *op;
for(i=;i<mod;++i)
p[i].next=NULL;
mmax=;
p[].next=NULL;
p[].pos=;
sign[]=;
for(i=;i<=n;++i){
scanf("%d",&ttt);
change(ttt,i);
value=;
for(j=;j<K;++j){
value+= ( gird[i][j]*j );
}
value=int(fabs(value))%mod;
if(sign[value]==){
p[value].pos=i;
sign[value]=;
continue;
}else if(sign[value]==){
tmp=(node *)malloc(sizeof(node));
tmp->next=NULL;
tmp->pos=i;
int ss=;
op=&p[value];
while(op!=NULL){
if( cmp(op->pos,i)== ){
ss=;
if( (i-op->pos) > mmax ){
mmax=i- (op->pos);
break;
}
}
op=op->next;
}
if(ss==) continue;
op=&p[value];
while(op->next!=NULL){
op=op->next;
}
op->next=tmp;
}
}
printf("%d\n",mmax);
/*
for(i=0;i<=n;++i){
for(j=0;j<K;++j){
printf("%d ",gird[i][j]);
}
printf("\n");
}
*/ }
return ;
}