暑期训练之 Hash

ACWING.137 雪花雪花雪花
https://www.acwing.com/problem/content/139/

#include <bits/stdc++.h>
using namespace std;
const int SIZE=100010;
int head[SIZE],Next[SIZE],snow[SIZE][7],n,tot,P=99991;
int H(int *a){
    int sum=0,mul=1;
    for(int i=0;i<6;i++){
        sum=(sum+a[i])%P;
        mul=(long long)mul*a[i]%P;
    }
    return (sum+mul)%P;
}
bool Equal(int *a,int *b){
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
            bool eq=1;
            for(int k=0;k<6;k++)
                if(a[(i+k)%6]!=b[(j+k)%6]) eq=0;
            if(eq) return 1;
            eq=1;
            for(int k=0;k<6;k++)
                if(a[(i+k)%6]!=b[(j-k+6)%6]) eq=0;
            if(eq) return 1;
        }
    }
    return 0;
}
bool Insert(int *a){
    int val=H(a);
    for(int i=head[val];i;i=Next[i])if(Equal(snow[i],a))return 1;
    tot++;
    memcpy(snow[tot],a,24);
    Next[tot]=head[val];
    head[val]=tot;
    return 0;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        int a[7];
        for(int j=0;j<6;j++) cin>>a[j];
        if(Insert(a)){
            cout<<"Twin snowflakes found."<<endl;
            return 0;
        }
    }
    cout<<"No two snowflakes are alike."<<endl;
    return 0;
}

ACWING.138 兔子与兔子
https://www.acwing.com/problem/content/140/

#include <bits/stdc++.h>
using namespace std;
char s[1000010];
unsigned long long f[1000010],p[1000010];
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    int q;
    p[0]=1;
    cin>>q;
    for(int i=1;i<=n;i++){
        f[i]=f[i-1]*131+(s[i]-'a'+1);
        p[i]=p[i-1]*131;
    }
    for(int i=1;i<=q;i++){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(f[r1]-f[l1-1]*p[r1-l1+1]==f[r2]-f[l2-1]*p[r2-l2+1])
            cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}