Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

哈希代码。。。

Posted by 15127412852 at 2012-07-19 10:23:03 on Problem 3349
#include <iostream>
#include <stdio.h>

using namespace std;
const int M=99991;
int n;

struct snow
{
    int f[6];
    int v;
    struct snow *next;
};
snow s[99992];

void init(snow a)
{
    a.v=0;
    a.next=NULL;
}

int hash(int flake[6])
{
    int i,sum;
    sum=0;
    for(i=0;i<6;i++)
    sum=sum+flake[i];
    return sum%M;
}

void insert(snow *temp,int flake[6])
{
    int j;
    if(temp->v==0)
        {
            for(j=0;j<6;j++)
            temp->f[j]=flake[j];
            temp->v=1;
            temp->next=new snow;
            temp->next->v=0;
        }
        else
        {
            temp=temp->next;
            insert(temp,flake);
        }
}

int judge(int a[6],int b[6])
{
    int i,j;
      for(i=0;i<6;i++)
      {
          if(a[0]==b[i])
          {
              for(j=1;j<6;j++)
                  if(a[j]!=b[(j+i)%6])
                  break;
                  if(j==6) return 1;
              for(j=1;j<6;j++)
                  if(a[6-j]!=b[(i+j)%6])
                  break;
                  if(j==6) return 1;
          }
      }
      return 0;

}

int search(snow *temp,int flake[6])
{
    while(temp->v)
    {
        if(judge(temp->f,flake)==1)
        return 1;
        else
        temp=temp->next;
    }
    if(temp->v==0)
    return 0;
}

int main()
{
    int i,j,ok;
    int flake[6];
    snow *temp;
    for(i=0;i<99992;i++)
    init(s[i]);
    scanf("%d",&n);
    ok=0;
    for(i=0;i<n;i++)
    {
        for(j=0;j<6;j++)
        {
        scanf("%d",&flake[j]);
        }
        if(ok==0)
        {
        temp=&s[hash(flake)];
        if(search(temp,flake)==0)
        insert(temp,flake);
        else
            ok=1;
        }
    }
    if(ok==0)
    printf("No two snowflakes are alike.\n");
    else
    printf("Twin snowflakes found.\n");
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator