pku 3349

2009年7月17日

题目链接:PKU 3349 Snowflake Snow Snowflakes

分类:哈希+最小表示

题目分析与算法模型
         先hash,然后在哈希解决冲突时根据最小表示法判断哈希表中的同一地址的雪花是否同构即可,若同构则退出,否则一直找,找到链表的末尾,加入该雪花,直到n片雪花都已经hash过,若还没有找到,说明不存在同构的雪花了.......关于Hash,我是采用将雪花的六条边长的和模上一个素数作为关键字,当然Hash的方法有很多种,应该有更好的,呵呵.......关于最小表示法可参考周源的国家队论文---><<浅析“最小表示法”思想在字符串循环同构问题中的应用>>
        
Code:

  1#include<stdio.h>
  2#include<string.h>
  3#include<math.h>
  4#define max 250000
  5#define prime 129997
  6bool finish;    
  7int n,i,j,sum,he,len,pos;    
  8char ch;
  9struct node
 10{
 11    int next,zhi[7];
 12}hash[max];
 13void init()
 14{
 15    for(i=0;i<max;i++)hash[i].next=-1;
 16}
 17bool compare(int a[],int b[])
 18{
 19    bool res;
 20    int p1=0,p2=0,p3=0,t1[15],t2[15],t3[15],q1=0,q2=0,q3=0;
 21    for(i=0;i<6;i++)
 22    {
 23        t1[i]=a[i];
 24        t1[i+6]=a[i];
 25        t2[i]=b[i];
 26        t2[i+6]=b[i];
 27        t3[i]=a[5-i];
 28        t3[i+6]=a[5-i];
 29    }
 30    while(1)
 31    {
 32        if(p1>5||p2>5)
 33        {
 34            res=false;
 35            break;
 36        }
 37        if(q1-p1>=6)
 38        {
 39            res=true;
 40            break;
 41        }
 42        if(t1[q1]==t2[q2])
 43        {
 44            q1++;
 45            q2++;
 46        }
 47        else if(t1[q1]>t2[q2])
 48        {
 49            p1=q1+1;
 50            q1=p1;
 51            q2=p2;
 52        }
 53        else 
 54        {
 55            p2=q2+1;
 56            q2=p2;
 57            q1=p1;
 58        }
 59    }
 60    p2=0;q2=0;
 61    if(res)return res;
 62    while(1)
 63    {
 64        if(p3>5||p2>5)
 65        {
 66            res=false;
 67            break;
 68        }
 69        if(q3-p3>=6)
 70        {
 71            res=true;
 72            break;
 73        }
 74        if(t3[q3]==t2[q2])
 75        {
 76            q3++;
 77            q2++;
 78        }
 79        else if(t3[q3]>t2[q2])
 80        {
 81            p3=q3+1;
 82            q3=p3;
 83            q2=p2;
 84        }
 85        else 
 86        {
 87            p2=q2+1;
 88            q2=p2;
 89            q3=p3;
 90        }
 91    }
 92    return res;
 93}
 94void Hash(int kk)
 95{
 96    int now=kk%prime;
 97    while(hash[now].next!=-1)
 98    {
 99        if(compare(hash[pos].zhi,hash[hash[now].next].zhi))
100        {
101            finish=true;
102            return;
103        }
104        else now=hash[now].next;
105    }
106    hash[pos].next=-1;
107    hash[now].next=pos;
108    pos++;
109}
110int main()
111{
112    scanf("%d",&n);
113    finish=false;
114    pos=130000;
115    init();
116    while(n--)
117    {
118        sum=0;
119        for(i=0;i<6;i++)
120        {
121            hash[pos].zhi[i]=0;
122            ch=getchar();
123            while(!(ch>='0'&&ch<='9'))ch=getchar();
124
125            while((ch>='0'&&ch<='9'))
126            {
127                hash[pos].zhi[i]*=10;
128                hash[pos].zhi[i]+=ch-'0';
129                ch=getchar();
130            }
131            sum+=hash[pos].zhi[i];
132           }
133        if(!finish)Hash(sum);
134    }
135    if(finish)printf("Twin snowflakes found.\n");
136    else printf("No two snowflakes are alike.\n");
137    return 0;
138}
139


小结: 这道题目着实郁闷了我一天,先是TLE,再是WA,然后就在TLE和WA之间徘徊,在WA了N次之后终于AC了,错的原因竟然是Hash的函数出了一点错,即下面代码中的pos的起始值错了.不该为0的,而因从大于表长的某个数开始,因为我的Hash表,的前面的m个(m即为表长)元素是作为结点的,所以不存值的,但是我写的时候却存了值,这就是WA那么多次的原因所在,泪奔.......

posted on 2009-07-17 20:04 蜗牛也Coding 阅读(328) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜