poj 3349 Snowflake Snow Snowflaakes(hash)

6603 ワード

データ構造 sh ACM

テーマリンク
Snowflake Snow Snowflaakes
Time Limit: 400 MS

メモリLimit: 65536 K
Total Submissions: 32634

Acceepted: 8623
Description
You may have heard that no two sflaakes are alike.Your task is to write a program to determine whether this really true.Your program will read information about a collection of snowflashes、and search Everatcalyour program will be provided with a meass rement of the length of the six arms.Any pair of snowflashes which have the same lengths of corepoding arms shound fland byyour program as possiblidentical.
Input
The first line of input will contain a single integer n,0 n ≦100000,the number of snowflaakes to follow.This will be followowwed by n ライン、each describing a snowflake.Each snowflake will be described by a line containing six integers(each integer ist 0 and less than 1000000 ms)、the lengths of the s the snowthe the the ardersbut they may begin with any of the six arms.For example,the same snowflake could be described as 1 2 3 4 or 4 3 2 1 6.
Output
If all of the snowflashes are distinct,your program shoud print the message:No ts snowflaakes are.If there is a pair of possibly identical snow akes,your program shound the message.Tfree.Tflas.Tflas.Tfres.
Sample Input

2
1 2 3 4 5 6
4 3 2 1 6 5

Sample Output

Twin snowflakes found.

注意:本題には二つの穴があります.第一に複数のグループを書いて入力してはいけません.第二にc++を提出してはいけません.
nつの雪の花は、どの雪にも腕が6つあります.腕の長さを教えます.二つの雪の六つの腕の長さが同じなら、二つの雪は同じです.同じ雪が二つありますか?
問題はどのように1つの数字を構成するリング(時計回りかそれとも反時計回りか)を一つの数にhashするかにあります.
私のやり方は時計回りか反時計回りか分かりませんので、まずこのリングの12種類の配列を求めます.hashでこの12種類の一つがあったかどうかを判断します.もし現れたら同じ雪を見つけます.
タイムカードが死にそうなので、読み込み最適化をしました.複雑度O(n*(36+36+12)
コードは以下の通りです

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<string.h>
#define inff 0x3fffffff
#define nn 7100000
#define mod 7000009
typedef __int64 LL;
typedef unsigned __int64 LLU;
using namespace std;
int n;
int a[7];
LLU ve[13];
bool use[nn];
LLU ha[nn];
void add(LLU x)
{
    int ix=x%mod;
    int i;
//    int fc=0;
    for(i=ix;;i=(i+1)%mod)
    {
        if(!use[i])
        {
            use[i]=true;
            ha[i]=x;
            return ;
        }
        if(ha[i]==x)
            return ;
//        if(++fc>0)
//            break;
    }
}
bool zhao(LLU x)
{
    int ix=x%mod;
    int i;
//    int fc=0;
    for(i=ix;;i=(i+1)%mod)
    {
        if(!use[i])
            return false;
        if(ha[i]==x)
            return true;
//        if(++fc>0)
//            break;
    }
    return false;
}
bool solve()
{
    int lv=0;
    int i,j;
    LLU ix;
    for(i=0;i<6;i++)
    {
        ix=0;
        for(j=0;j<6;j++)
        {
            ix=(ix*10000007+a[(i+j)%6]);
        }
        if(zhao(ix))
            return true;
        ve[lv++]=ix;
    }
    for(i=0;i<6;i++)
    {
        ix=0;
        for(j=0;j<6;j++)
        {
            ix=(ix*10000007+a[((i-j)+6)%6]);
        }
        if(zhao(ix))
            return true;
        ve[lv++]=ix;
    }
    for(i=0;i<12;i++)
    {
        add(ve[i]);
    }
    return false;
}
inline int read()
{
    char ch;
    bool flag=false;
    int re=0;
    while(!(((ch=getchar())>='0'&&(ch<='9'))||(ch=='-')));
    if(ch!='-')
    {
        re*=10;
        re+=ch-'0';
    }
    else
        flag=true;
    while((ch=getchar())>='0'&&(ch<='9'))
    {
        re*=10;
        re+=ch-'0';
    }
    if(flag)
        re=-re;
    return re;
}
int main()
{
    int i;
    scanf("%d",&n);
    {
        memset(use,false,sizeof(use));
        bool ans=false;
        while(n--)
        {
            for(i=0;i<6;i++)
            {
                a[i]=read();
            }
            if(ans)
                continue;
            ans=solve();
        }
        if(ans)
        {
            puts("Twin snowflakes found.");
        }
        else
            puts("No two snowflakes are alike.");
    }
    return 0;
}

前のコードはあくまでもカードでした.もっと早い方法がありますか?
後から来たやり方は、一つの輪を直接一つの数にhashすることです.具体的には、まず前の方法で一つのリングを12個の数にして、今はこの12個の数を2回のhashで一つの数にします.初めてhashで使ったunsigned long longです.自動的に型を取りますから.二回のhashには三つの方法があります.一つは12個の数の異種値、二つは12個の数の平方和、三つは12個の数の立方和を求めます.
複雑度O(n＊36).hashの数が少ないので、定数は前の方法よりずっと小さいです.
コードは以下の通りです

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<string.h>
#define inff 0x3fffffff
#define nn 1000005
#define mod 1000003
typedef __int64 LL;
typedef unsigned __int64 LLU;
using namespace std;
int n;
int a[7];
bool use[nn];
LLU ha[nn];
void add(LLU x)
{
    int ix=x%mod;
    int i;
    for(i=ix;;i=(i+1)%mod)
    {
        if(!use[i])
        {
            use[i]=true;
            ha[i]=x;
            return ;
        }
    }
}
bool zhao(LLU x)
{
    int ix=x%mod;
    int i;
    for(i=ix;;i=(i+1)%mod)
    {
        if(!use[i])
            return false;
        if(ha[i]==x)
            return true;
    }
    return false;
}
bool solve()
{
    int i,j;
    LLU ix;
    LL fc=0;
    for(i=0;i<6;i++)
    {
        ix=0;
        for(j=0;j<6;j++)
        {
            ix=(ix*10000007+a[(i+j)%6]);
        }
        fc^=ix;
    }
    for(i=0;i<6;i++)
    {
        ix=0;
        for(j=0;j<6;j++)
        {
            ix=(ix*10000007+a[((i-j)+6)%6]);
        }
        fc^=ix;
    }
    if(zhao(fc))
        return true;
    add(fc);
    return false;
}
inline int read()
{
    char ch;
    bool flag=false;
    int re=0;
    while(!(((ch=getchar())>='0'&&(ch<='9'))||(ch=='-')));
    if(ch!='-')
    {
        re*=10;
        re+=ch-'0';
    }
    else
        flag=true;
    while((ch=getchar())>='0'&&(ch<='9'))
    {
        re*=10;
        re+=ch-'0';
    }
    if(flag)
        re=-re;
    return re;
}
int main()
{
    int i;
    scanf("%d",&n);
    {
        memset(use,false,sizeof(use));
        bool ans=false;
        while(n--)
        {
            for(i=0;i<6;i++)
            {
                a[i]=read();
            }
            if(ans)
                continue;
            ans=solve();
        }
        if(ans)
        {
            puts("Twin snowflakes found.");
        }
        else
            puts("No two snowflakes are alike.");
    }
    return 0;
}

衝突円コード