• <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>
            

    
            

            




            







												


        
			
			


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


	


            
	    
    




            






            

				
				

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

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久国产精品二国产精品|
精品多毛少妇人妻AV免费久久
|
久久精品亚洲精品国产欧美|
久久精品三级视频|
狠狠精品久久久无码中文字幕|
九九精品99久久久香蕉|
久久久久久国产精品免费免费|
亚洲精品高清国产一线久久|
久久精品女人天堂AV麻|
好属妞这里只有精品久久|
久久久久久国产a免费观看黄色大片|
国产精品18久久久久久vr|
蜜桃麻豆www久久国产精品|
99久久精品费精品国产一区二区|
久久久免费观成人影院|
日韩精品国产自在久久现线拍|
亚洲va中文字幕无码久久不卡|
久久精品一区二区影院
|
久久国产成人|
97久久天天综合色天天综合色hd|
手机看片久久高清国产日韩|
国产999精品久久久久久|
国产三级久久久精品麻豆三级
|
国产精品狼人久久久久影院|
欧洲精品久久久av无码电影|
久久综合久久美利坚合众国|
美女久久久久久|
人妻少妇精品久久|
久久无码一区二区三区少妇|
天天爽天天爽天天片a久久网|
久久久久久亚洲AV无码专区|
无码国内精品久久人妻蜜桃|
久久久久久国产精品无码下载|
久久午夜无码鲁丝片午夜精品|
2021国产成人精品久久|
66精品综合久久久久久久|
久久免费精品视频|
国产成人99久久亚洲综合精品|
久久国产精品免费一区|
色婷婷综合久久久久中文字幕|
狠狠色丁香久久婷婷综合图片|