poj 3349 Snowflake Snow Snowflakes(hash)

解题思路

题意：

判断有没有两朵相同的雪花，每朵雪花有六瓣，用比较花瓣长度的方法看是否是一样的，如果对应的arms有相同的长度说明是一样的。给出n朵，只要有两朵是一样的就输出有twin snowflakes，如果任何两个都是不一样的输出相应信息。

 

思路：

       因为数据量很大，要在如此多雪花中找一样的，所以用到了hash，hash函数想不到很好的，只是用他arm的长度和来作为hash函数。还有个问题是如何判断有相同长度和的雪花（假设snowflake[a]和snowflake[b]）是一样的，我用一个数组snowTemp[12]来存两次snowflake[a],

即  snowTemp[0---5]  = snowflake[a][0…5],

snowTemp[6…11]  = snowflake[a][0…5]

然后分别从前往后和从后往前分别找一次snowTemp中有没有与snowflake[b]匹配的。如果有就说明a和b是一样的，否则就是不一样的。

事实证明用getchar比scanf快很多，用gcc比C快很多。

这个题做了三屏，RE,WA,TLE,尝遍n多次后之后终于AC了。而后又由1400多MS到282MS，真是不容易啊~ 哈哈

Ps： 这几天把C语言重头到尾复习了遍，懂了很多，也学到了很多新的知识，《C语言程序设计现代方法》这书很不错。

源程序

 

#include <stdio.h>
#include <conio.h>
#include <time.h>
#define HASHLEN 140000
#define PRIME 139997
#define N 100010

int snowflake[N][6];

struct node
{
    int key;
    struct node *next;
}snow[N];

struct node *hashList[HASHLEN];

int get_int(void)
{
    char ch;
    int num = 0;

    while((ch = getchar())== ' ' || ch == '\n')
        ;
    while(ch >= '0' && ch <= '9')
    {
        num = num * 10 + ch - '0';
        ch = getchar();
    }
    return num;
}

int same(int x, int y)
{
    int i, j, k;
    int snowTemp[12];

    for(i=0; i<6; i++)
    {
        snowTemp[i] = snowflake[x][i];
        snowTemp[i+6] = snowflake[x][i];
    }
    i = 0;
    j = 0;
    while(i < 12)   //从前往后看是否匹配
    {
        while(i < 12 && snowTemp[i] != snowflake[y][j])
            i++;
        k = i;
        while(i < 12 && snowTemp[i] == snowflake[y][j])
        {
            if(j == 5)
                return 1;
            i++;
            j++;
        }
        i = k+1;
        j = 0;
    }
    i = 11;
    while(i >= 0)  //从后往前看是否匹配
    {
        while(i >= 0 && snowTemp[i] != snowflake[y][j])
            i--;
        k = i;
        while(i >= 0 && snowTemp[i] == snowflake[y][j])
        {
            if(j == 5)
                return 1;
            i--;
            j++;
            
        }
        i = k - 1;
        j = 0;
    }
    return 0;
}

int check(struct node *l, int x)
{
    while(l != NULL)
    {
        if(same(l->key, x))
        {
            return 1;
        }
        l = l->next;
    }
    return 0;
}

int main(void)
{
    int i, j, n, k, isSame = 0, sum;
    char ch;
    //clock_t start = clock();
    freopen("in.txt", "r", stdin);
    scanf("%d", &n);

    for(i=1; i<=n; i++)
    {
        sum = 0;
        for(j=0; j<6; j++)
        {
            snowflake[i][j] = get_int();
            sum += snowflake[i][j];
        }
        sum %= PRIME;         //hash值

        snow[i].key = i;
        if(hashList[sum] == NULL)
        {
            hashList[sum] = &snow[i];
        }
        else if(check(hashList[sum], i))
        {
            isSame = 1;
            break;
        }
        else
        {
            snow[i].next = hashList[sum];
            hashList[sum] = &snow[i];
        }
    }
    if(isSame)
        printf("Twin snowflakes found.\n");
    else
        printf("No two snowflakes are alike.\n");
    //printf("Time: %d\n", clock() - start);
    getch();
    return 0;
}