青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(317) 評論(0)  編輯 收藏 引用


只有注冊用戶登錄后才能發表評論。
網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


<2010年11月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美中文字幕视频| 欧美成人精品在线视频| 国产精品久久久久国产a级| 欧美日韩精品一区二区| 欧美午夜片欧美片在线观看| 国产精品jizz在线观看美国| 国产精品视频久久久| 国产日韩1区| 亚洲国产成人精品女人久久久| 亚洲另类自拍| 性刺激综合网| 亚洲国产成人av| 日韩一区二区精品视频| 亚洲欧美日韩在线| 免费观看亚洲视频大全| 国产精品成人在线观看| 黄色成人91| 亚洲永久在线| 欧美大学生性色视频| 国产乱码精品一区二区三| 亚洲视频免费观看| 久久精品30| 欧美日韩一区二| 黄色成人在线网站| 亚洲影视九九影院在线观看| 欧美1区3d| 亚洲欧美卡通另类91av| 欧美福利电影在线观看| 国产亚洲二区| 亚洲一区二区三区久久| 欧美激情一区二区久久久| 一区二区高清在线| 欧美成人日韩| 激情成人在线视频| 午夜宅男欧美| 99热免费精品| 欧美岛国激情| 在线精品视频在线观看高清| 久久av一区二区三区| 一区二区动漫| 欧美日韩综合在线免费观看| 亚洲精品欧洲| 欧美高清视频一区二区| 久久久夜精品| 精东粉嫩av免费一区二区三区| 午夜日韩在线观看| 亚洲少妇自拍| 国产精品久久激情| 亚洲一区二区三区涩| 亚洲精品九九| 欧美黄色aaaa| 99在线热播精品免费| 亚洲风情亚aⅴ在线发布| 卡一卡二国产精品| 亚洲国内精品在线| 亚洲日本在线观看| 欧美色图五月天| 亚洲免费在线看| 一区二区欧美在线| 国产精品久久午夜| 欧美亚洲一区三区| 欧美亚洲系列| 韩国v欧美v日本v亚洲v| 老色批av在线精品| 免费观看在线综合| 一区二区三区高清在线观看| 日韩视频在线观看| 国产精品一二三视频| 久久激情综合网| 久久亚洲精品网站| 91久久香蕉国产日韩欧美9色| 亚洲大胆女人| 欧美区在线播放| 亚洲在线视频一区| 性18欧美另类| 亚洲三级电影在线观看 | 亚洲已满18点击进入久久| 中文一区二区| 亚洲欧美久久久| 欧美一区影院| 亚洲福利在线观看| 亚洲日本一区二区三区| 欧美午夜在线| 久久免费高清| 欧美精品1区2区| 性色一区二区| 久久午夜色播影院免费高清| 99综合视频| 久久国产综合精品| 一区二区高清视频| 午夜精品亚洲一区二区三区嫩草| 亚洲大片在线| 亚洲一区二区三区精品在线观看| 国产一区二区日韩| 99精品欧美| 亚洲福利一区| 午夜精品一区二区三区在线| 亚洲精品婷婷| 欧美一区二区三区久久精品| 一本色道久久综合亚洲二区三区| 欧美在线免费观看亚洲| 国产精品99久久99久久久二8 | 欧美精品99| 久久夜色精品国产欧美乱极品| 欧美日韩国产免费| 欧美成人一区二区三区| 国产女人aaa级久久久级| 91久久国产综合久久91精品网站| 国产日韩综合一区二区性色av| 亚洲欧洲另类| 91久久综合亚洲鲁鲁五月天| 欧美在线看片a免费观看| 性欧美xxxx大乳国产app| 欧美精品在线一区| 欧美黑人在线观看| 激情久久久久| 欧美伊人久久久久久久久影院| 亚洲免费在线视频一区 二区| 欧美大香线蕉线伊人久久国产精品| 久久综合亚州| 国产一区二区黄| 亚洲在线1234| 午夜精品网站| 国产精品美女久久久久久久| 99国产精品久久| 亚洲一区二区毛片| 欧美三日本三级少妇三2023| 亚洲精品久久久久| 99精品热6080yy久久 | 黑人巨大精品欧美一区二区小视频| 一区二区三区国产| 亚洲欧美变态国产另类| 国产精品va在线播放我和闺蜜| 亚洲人成网站999久久久综合| 亚洲高清久久网| 免播放器亚洲| 亚洲人成高清| 亚洲一区二三| 国产精品久久久久久久久久尿 | 亚洲精品在线免费观看视频| 亚洲精品久久久久久久久久久久 | 91久久亚洲| 欧美成人资源| 亚洲精品美女在线观看播放| 日韩一区二区高清| 欧美日韩蜜桃| 亚洲影院色无极综合| 久久国产日本精品| 在线观看三级视频欧美| 免费91麻豆精品国产自产在线观看| 亚洲电影免费观看高清完整版| 亚洲另类在线一区| 国产精品国产福利国产秒拍| 欧美一级网站| 欧美激情五月| 亚洲欧美在线观看| 一区在线观看| 欧美激情在线播放| 在线一区二区三区四区| 久久精品国产v日韩v亚洲| 亚洲电影在线观看| 欧美美女日韩| 午夜精品剧场| 亚洲国产精品久久久久| 亚洲欧美日韩天堂| 亚洲东热激情| 国产精品久久久久久福利一牛影视| 久久大香伊蕉在人线观看热2| 亚洲高清三级视频| 午夜精品在线观看| 亚洲激情av| 国产精品一二三视频| 免费美女久久99| 亚洲欧美日韩精品久久| 亚洲福利免费| 欧美在线综合| 99成人精品| 狠狠色丁香久久婷婷综合_中| 欧美激情视频给我| 久久精品卡一| 亚洲一区二区视频在线观看| 欧美xart系列高清| 新67194成人永久网站| 亚洲另类一区二区| 亚洲大胆在线| 国产真实久久| 国产精品久久久久久久第一福利| 蜜臀av在线播放一区二区三区| 性久久久久久久久久久久| 亚洲久色影视| 亚洲风情在线资源站| 久久综合九色九九| 香蕉亚洲视频| 在线视频你懂得一区| 91久久线看在观草草青青| 国产一区二区成人久久免费影院| 国产精品九九| 欧美日韩视频在线| 欧美激情1区| 欧美大片网址|