• <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ù)最小表示法判斷哈希表中的同一地址的雪花是否同構即可,若同構則退出,否則一直找,找到鏈表的末尾,加入該雪花,直到n片雪花都已經hash過,若還沒有找到,說明不存在同構的雪花了.......關于Hash,我是采用將雪花的六條邊長的和模上一個素數(shù)作為關鍵字,當然Hash的方法有很多種,應該有更好的,呵呵.......關于最小表示法可參考周源的國家隊論文---><<淺析“最小表示法”思想在字符串循環(huán)同構問題中的應用>>
                    
            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的函數(shù)出了一點錯,即下面代碼中的pos的起始值錯了.不該為0的,而因從大于表長的某個數(shù)開始,因為我的Hash表,的前面的m個(m即為表長)元素是作為結點的,所以不存值的,但是我寫的時候卻存了值,這就是WA那么多次的原因所在,淚奔.......
            

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


	


            
	    
    




            






            

				
				

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

            

					

            導航
            

					

            統(tǒng)計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



亚洲精品午夜国产va久久|
99久久国产亚洲高清观看2024|
99久久这里只有精品|
亚洲AV无码久久精品成人
|
亚洲av伊人久久综合密臀性色|
国内精品欧美久久精品|
99久久国产综合精品网成人影院
|
久久久久久国产a免费观看不卡
|
欧美午夜A∨大片久久
|
日日躁夜夜躁狠狠久久AV|
国产精品一区二区久久精品涩爱|
青青久久精品国产免费看|
久久久噜噜噜久久中文字幕色伊伊|
精品国产热久久久福利|
精品久久久久久无码人妻蜜桃|
久久国产精品免费一区二区三区|
国产精品VIDEOSSEX久久发布|
国产精品成人精品久久久|
国产日韩久久久精品影院首页|
久久99热这里只有精品国产|
九九久久精品无码专区|
亚洲午夜久久久|
久久久久99精品成人片欧美|
一本大道加勒比久久综合|
久久久精品视频免费观看|
人人妻久久人人澡人人爽人人精品
|
囯产极品美女高潮无套久久久
|
噜噜噜色噜噜噜久久|
久久久久久夜精品精品免费啦|
狠狠狠色丁香婷婷综合久久五月|
久久久精品视频免费观看
|
中文字幕亚洲综合久久|
亚洲国产日韩欧美久久|
久久人人爽人人爽人人AV东京热
|
国产精自产拍久久久久久蜜|
久久婷婷国产剧情内射白浆|
久久99久久99小草精品免视看|
伊人久久亚洲综合影院|
亚洲国产精品久久久久久|
久久强奷乱码老熟女网站|
国产成人无码精品久久久免费
|