• <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,然后在哈希解決沖突時根據(jù)最小表示法判斷哈希表中的同一地址的雪花是否同構(gòu)即可,若同構(gòu)則退出,否則一直找,找到鏈表的末尾,加入該雪花,直到n片雪花都已經(jīng)hash過,若還沒有找到,說明不存在同構(gòu)的雪花了.......關(guān)于Hash,我是采用將雪花的六條邊長的和模上一個素數(shù)作為關(guān)鍵字,當(dāng)然Hash的方法有很多種,應(yīng)該有更好的,呵呵.......關(guān)于最小表示法可參考周源的國家隊論文---><<淺析“最小表示法”思想在字符串循環(huán)同構(gòu)問題中的應(yīng)用>>
                    
            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


            小結(jié): 這道題目著實郁悶了我一天,先是TLE,再是WA,然后就在TLE和WA之間徘徊,在WA了N次之后終于AC了,錯的原因竟然是Hash的函數(shù)出了一點錯,即下面代碼中的pos的起始值錯了.不該為0的,而因從大于表長的某個數(shù)開始,因為我的Hash表,的前面的m個(m即為表長)元素是作為結(jié)點的,所以不存值的,但是我寫的時候卻存了值,這就是WA那么多次的原因所在,淚奔.......
            

		
            
			posted on 2009-07-17 20:04 蝸牛也Coding 閱讀(310) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            



            


            

	
            
		
		
            只有注冊用戶登錄后才能發(fā)表評論。
            
		
            
		
				
		
		
		
            
		
            			
		
		
		
		
            
		
            
			
		
            
		
            
			
		
            
		
            
			
            網(wǎng)站導(dǎo)航:
			博客園  
			IT新聞  
			BlogJava  			
			博問  
			Chat2DB  
			管理
			
            		
		
            
		
            
			
				

            


            

            		
		
            
	
            	

            



            

				
				

			
            
			
            
				
					
            
	
            
		
            <2025年7月>
            
	
            日一二三四五六
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789
            

            

					

            導(dǎo)航
            

					

            統(tǒng)計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久久久久国产精品美女|
久久永久免费人妻精品下载|
精品国产乱码久久久久久1区2区|
久久久久久精品免费看SSS|
久久久老熟女一区二区三区|
99久久er这里只有精品18|
国产成人无码精品久久久久免费
|
午夜精品久久影院蜜桃|
99久久国产亚洲综合精品|
久久精品水蜜桃av综合天堂|
亚洲国产精品久久|
久久精品视频一|
97久久精品国产精品青草|
国内精品久久久久影院网站|
无码久久精品国产亚洲Av影片|
久久久久国产一级毛片高清版|
亚洲综合久久夜AV |
青青青伊人色综合久久|
亚洲va国产va天堂va久久|
久久这里有精品视频|
岛国搬运www久久|
国产午夜精品理论片久久影视|
亚洲国产天堂久久久久久|
嫩草影院久久国产精品|
99精品国产在热久久|
久久天天躁狠狠躁夜夜不卡|
欧美性大战久久久久久|
国产激情久久久久影院|
精品久久久久久综合日本|
久久婷婷五月综合97色一本一本
|
久久亚洲AV成人无码|
久久天天躁狠狠躁夜夜av浪潮|
久久久青草久久久青草|
狠狠狠色丁香婷婷综合久久五月
|
精品熟女少妇av免费久久|
亚洲精品乱码久久久久久蜜桃图片
|
久久国产精品无码HDAV|
欧美噜噜久久久XXX|
亚洲va国产va天堂va久久|
久久综合88熟人妻|
久久久精品一区二区三区|