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


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2009年8月>
            
	
            日一二三四五六
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



波多野结衣AV无码久久一区|
亚洲av成人无码久久精品|
久久精品国产黑森林|
久久久精品国产|
久久精品国产99国产精品澳门|
99久久精品国产综合一区|
色综合久久夜色精品国产|
国产亚洲精品自在久久|
久久久久久一区国产精品|
日韩乱码人妻无码中文字幕久久|
丰满少妇人妻久久久久久4|
精品久久久久久久久免费影院|
久久精品国产亚洲av麻豆色欲|
久久久久九九精品影院|
久久久久成人精品无码中文字幕
|
久久午夜羞羞影院免费观看|
色综合色天天久久婷婷基地|
国内高清久久久久久|
天天影视色香欲综合久久|
国产精品久久久久久久久鸭|
国产精品久久久久免费a∨|
热综合一本伊人久久精品|
国产午夜精品理论片久久
|
亚洲精品NV久久久久久久久久|
69久久精品无码一区二区|
亚洲国产精品高清久久久|
亚洲伊人久久成综合人影院
|
99久久国产综合精品成人影院|
亚洲国产精品久久久天堂|
狠狠色婷婷久久一区二区|
久久婷婷午色综合夜啪|
久久最新免费视频|
亚洲国产香蕉人人爽成AV片久久|
爱做久久久久久|
99精品伊人久久久大香线蕉|
国产成人久久激情91|
久久se精品一区精品二区|
青青热久久综合网伊人|
欧美精品一区二区精品久久|
亚洲综合久久综合激情久久|
观看 国产综合久久久久鬼色 欧美 亚洲 一区二区
|