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



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



国产呻吟久久久久久久92|
久久精品无码免费不卡|
久久久噜噜噜www成人网|
热99RE久久精品这里都是精品免费|
久久久久一区二区三区|
久久精品国产国产精品四凭|
久久青青国产|
久久水蜜桃亚洲av无码精品麻豆
|
久久青草国产手机看片福利盒子|
jizzjizz国产精品久久|
久久国产乱子伦精品免费午夜|
久久影院午夜理论片无码
|
秋霞久久国产精品电影院|
国内精品伊人久久久久AV影院|
久久婷婷色香五月综合激情|
久久久久亚洲AV无码去区首|
亚洲欧洲精品成人久久奇米网|
色8久久人人97超碰香蕉987|
国产亚洲欧美成人久久片|
久久无码专区国产精品发布|
中文字幕成人精品久久不卡|
久久WWW免费人成一看片|
色综合久久88色综合天天 |
久久亚洲欧美日本精品|
午夜精品久久久久久久无码|
99久久国产主播综合精品|
狠狠色丁香婷婷综合久久来|
久久久久国产日韩精品网站|
99久久精品国产毛片|
国内精品久久久久久久久|
久久乐国产精品亚洲综合|
人妻久久久一区二区三区|
热久久国产精品|
无码人妻精品一区二区三区久久|
久久亚洲国产成人精品性色|
久久综合久久综合九色|
三级三级久久三级久久|
久久精品国产亚洲av麻豆色欲|
久久久无码精品亚洲日韩京东传媒|
亚洲中文字幕无码久久精品1|
国内精品久久久久久99|