poj 3349_Snowflake Snow Snowflakes_hash

发布于 2019-04-24  5 次阅读


题目大意

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

思路

将全部数平方后散列存在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;
}
]]>