gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 3349--Snowflake Snow Snowflakes
  1#include <stdio.h>
  2
  3const int KEY = 149997 ;
  4const int MAXN = 100000 ;
  5
  6struct HashItem
  7{
  8    __int64 len[6] ;
  9    HashItem *next ;
 10    HashItem(){
 11        next = NULL ;
 12    }
 13} ;
 14
 15HashItem hash[KEY], g_Temp[MAXN] ;
 16int g_Pos = 0 ;
 17
 18unsigned long l[6] ;
 19
 20void Copy( HashItem *p )
 21{
 22    for ( int i = 0 ; i < 6 ; ++i )
 23        p->len[i] = l[i] ;
 24}
 25
 26bool Judge(HashItem *p)
 27{
 28    int i , j , cnt ;
 29    bool equal ;
 30    for ( i = 0 ; i < 6 ; ++i )
 31    {
 32        cnt = 0 ;
 33        equal = true ;
 34        j = i ;
 35        while ( cnt != 6 )
 36        {
 37            if ( p->len[cnt] != l[j] )
 38            {
 39                equal = false ;
 40                break ;
 41            }
 42            cnt++ ;
 43            j = ( j + 1 ) % 6 ;
 44        }
 45        
 46        if ( equal )
 47            return true ;
 48    }
 49    
 50    for ( i = 0 ; i < 6 ; ++i )
 51    {
 52        cnt = 0 ;
 53        equal = true ;
 54        j = i ;
 55        while ( cnt != 6 )
 56        {
 57            if ( p->len[cnt] != l[j] )
 58            {
 59                equal = false ;
 60                break ;
 61            }
 62            cnt++ ;
 63            j-- ;
 64            if ( j == -1 )
 65                j = 5 ;
 66        }
 67        if ( equal )
 68            return true ;
 69    }
 70    
 71    return false ;
 72    
 73}
 74
 75bool Insert()
 76{
 77    unsigned long value = 0 ;
 78    int i ;
 79    
 80    for ( i = 0 ; i < 6 ; ++i )
 81    {
 82        value += l[i] ;
 83    }
 84    
 85    unsigned int pos = value % KEY ;
 86    
 87    HashItem *ptr = hash[pos].next ;
 88    
 89    while ( ptr )
 90    {
 91        if ( Judge( ptr ) )
 92            return true ;
 93        ptr = ptr->next ;
 94    }
 95    
 96    ptr = &g_Temp[g_Pos++] ;
 97    
 98    Copy( ptr ) ;
 99    ptr->next = hash[pos].next ;
100    hash[pos].next = ptr ;
101    
102    return false ;
103}
104
105int main()
106{
107    int n , i ;
108    bool isSame = false ;
109    
110//    freopen("in.txt", "r", stdin) ;
111    scanf("%d", &n) ;
112    while ( n-- )
113    {    
114        for ( i = 0 ; i < 6 ; ++i )
115            scanf("%ld", &l[i]) ;
116        if ( !isSame )
117        {
118            isSame = Insert() ;
119        }
120        if ( isSame )
121            break ;
122    }
123    
124    if ( isSame )
125    {
126        printf("Twin snowflakes found.\n") ;
127    }
128    else {
129        printf("No two snowflakes are alike.\n") ;
130    }
131    
132    return 0 ;
133}
posted on 2008-11-11 00:39 巫 阅读(290) 评论(0)  编辑 收藏 引用 所属分类: Hash应用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理