首页 > 代码库 > hash练习

hash练习

/*COGS 610 */#include<iostream>#include<cstdio>#include<cstring>#define mod 23333#define maxn 200010using namespace std;int a[maxn],n,c,head[maxn],cnt[maxn],num,ans;struct node{    int v,pre;}e[maxn];void Insert(int x){    int ha=(x%mod+x/mod)%mod;    for(int i=head[ha];i;i=e[i].pre)        if(e[i].v==x){            cnt[i]++;            return;        }    num++;e[num].v=x;    e[num].pre=head[ha];    head[ha]=num;cnt[num]++;}int Query(int x){    int ha=(x%mod+x/mod)%mod;    for(int i=head[ha];i;i=e[i].pre)        if(e[i].v==x)return cnt[i];    return 0;}int main(){    freopen("dec.in","r",stdin);    freopen("dec.out","w",stdout);    scanf("%d%d",&n,&c);    for(int i=1;i<=n;i++)        scanf("%d",&a[i]);    for(int i=1;i<=n;i++){        int s=a[i]+c;        Insert(s);    }    for(int i=1;i<=n;i++)        ans+=Query(a[i]);    printf("%d\n",ans);    return 0;}
/*COGS 1176*/#include<iostream>#include<cstdio>#include<cstring>#define maxn 500010#define ha 119#define HA 31#define mod 233333#define MOD 100007using namespace std;int n,m,num,head[maxn],l,ans,cnt[maxn];char s[250];struct node{    int v,pre;}e[maxn];void Insert(int x,int y){    for(int i=head[x];i;i=e[i].pre)        if(e[i].v==y){            cnt[i]++;return;            }    num++;e[num].v=y;    e[num].pre=head[x];    head[x]=num;cnt[num]++;}int Query(int x,int y){    for(int i=head[x];i;i=e[i].pre)        if(e[i].v==y)return cnt[i];    return 0;}int main(){    freopen("mtest.in","r",stdin);    freopen("mtest.out","w",stdout);    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%s",s);        l=strlen(s);        int t=0,T=0;        for(int j=0;j<l;j++){            t=t*ha+s[j]-A;t%=mod;            T=T*HA+s[j]-A;T%=MOD;        }        Insert(t,T);    }    scanf("%d",&m);    for(int i=1;i<=m;i++){        scanf("%s",s);        l=strlen(s);        int t=0,T=0;        for(int j=0;j<l;j++){            t=t*ha+s[j]-A;t%=mod;            T=T*HA+s[j]-A;T%=MOD;        }        ans+=Query(t,T);    }    printf("%d\n",ans);    return 0;}
/*COGS 1406 虽然没有hash但是学了学输出优化 */#include<cstdio> using namespace std;int a[121],x,c[11];int init(){    char s=getchar();int x=0;    while(s!=EOF&&(s<0||s>9))s=getchar();    if(s==EOF)return -1;    while(s>=0&&s<=9){x=x*10+s-0;s=getchar();}    return x;}void Printf(int x){    int r=0;if(x==0)r++;    while(x){c[++r]=x%10;x/=10;}    while(r--)putchar(c[r+1]+0);}int main(){    freopen("AgeSort.in","r",stdin);    freopen("AgeSort.out","w",stdout);    while((x=init())!=-1)a[x]++;    for(int i=0;i<=120;i++)        for(int j=1;j<=a[i];j++){            Printf(i);putchar( );        }    return 0;}

 

hash练习