poj 3349_Snowflake Snow Snowflakes_hash

发布于 2019-04-25  893 次阅读


题目大意

在一堆数列中找出是否存在有两个数列中每一个数都在另一个数列中有相同数

思路

将全部数平方后散列存在hash中,以6个数加起来为值
O(n)
注意读入时要long long

#include 
#define M 9999877
int h[M+1];
long long a[7];
long long k;
int insert(int x)
{
    int i=x;
    while (h[i]!=-1&&h[i]!=k) i=(i+1)%M;
    h[i]=k;
}
int find(int x)
{
    int i=x;
    while (h[i]!=-1&&h[i]!=k) i=(i+1)%M;
    if (h[i]==k) return true;
    else return false;
}
int main()
{
    int n,ans=0;
    scanf("%d",&n);
    for (int i=1;i<=M;i++)
        h[i]=-1;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=6;j++)
            scanf("%I64d",&a[j]);
        long long x=(a[1]*a[1])%M;
        x=(a[2]*a[2]+x)%M;
        x=(a[3]*a[3]+x)%M;
        x=(a[4]*a[4]+x)%M;
        x=(a[5]*a[5]+x)%M;
        x=(a[6]*a[6]+x)%M;
        k=a[1]+a[2]+a[3]+a[4]+a[5]+a[6];    
        if (find(x)==true)
        {
            printf("Twin snowflakes found.");
            return 0;
        }
        insert(x);
    }
    printf("No two snowflakes are alike.");
    return 0;
}
]]>