POJ3349 Snowflake Snow Snowflakes 自己写个哈希模板

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 03 月 18 日

http://acm.nyist.net/JudgeOnline/problem.php?pid=130

很悲剧,只能说悲剧,花了一个下午思考一个模板,想着能经常用来着,结果第一次用POJ上一直TLE。。。汗死。最重要的是自己机器上测试十万组数据十分的快,只有0.7秒左右。。。然后就在NYOJ上提交,过了……这就浪费1天时间,悲剧。如果有幸有高人看到,一定请指正

ps:看到这个的童鞋请慎用。。。因为这是第一次写的哈希模板,很不理想很不理想……~ T T,POJ上解决1840,1186都超时,想死啊有木有?有木有!!!第一次写的模板真不好用。。


#include <cstdio>  
#include <cstring>  
#include <time.h>  
using namespace std;  
#define hashPrime 1444409   //哈希取余素数      
#define hashTableNums 1444505   //哈希表长度  
#define initNum -1          //哈希表初始化值  
int hashTableKeys[hashTableNums];//哈希表键值  
int hashTableValues[hashTableNums];//键值相对应的数据  
//哈希表初始化  
void hashTableInit(){  
    if(initNum==0) {  
        memset(hashTableKeys,0,sizeof(hashTableKeys));  
        memset(hashTableValues,0,sizeof(hashTableValues));}  
    else for (int i=0;i<hashTableNums;i++){  
        hashTableKeys[i]=initNum;  
        hashTableValues[i]=initNum;}  
}  
//哈希规则  
int hashTableRules(int hashKey){  
    return hashKey%hashPrime;  
}  
//向哈希表中添加数据  
int hashTableAdd(int hashKey,int hashValue){  
    int hashTablePos=hashTableRules(hashKey);  
    bool first=1;  
    for (int i=hashTablePos;;i++){  
        i %=hashTableNums;  
        if(i == hashTablePos && first==0) { return -1;}  
        first=0;  
        if(hashTableKeys[i] == initNum){   
            hashTableKeys[i]=hashKey;hashTableValues[i]=hashValue; return i;}  
    }  
}  
//查找哈希表  
int hashTableFind(int hashKey){  
    int hashTablePos=hashTableRules(hashKey);  
    bool first=1;  
    for (int i=hashTablePos;;i++){  
        i %=hashTableNums;  
        if(i == hashTablePos && first==0) { return -2;}  
        first=0;  
        if(hashTableKeys[i] == hashKey) return i;  
        if(hashTableKeys[i] == initNum) return -1;  
    }  
}  
int snows[100019][7];  
bool isSame(int a, int b) {    
    for(int i=0;i<6;i++)    
    {    
        if(/*顺时针方向*/    
          (snows[a][1] == snows[b][i+1] &&    
           snows[a][2] == snows[b][(i+1)%6+1] &&    
           snows[a][3] == snows[b][(i+2)%6+1] &&    
           snows[a][4] == snows[b][(i+3)%6+1] &&    
           snows[a][5] == snows[b][(i+4)%6+1] &&    
           snows[a][6] == snows[b][(i+5)%6+1])    
           ||    
            /*逆时针方向*/    
           (snows[a][1] == snows[b][i+1] &&    
            snows[a][2] == snows[b][(i+5)%6+1] &&    
            snows[a][3] == snows[b][(i+4)%6+1] &&    
            snows[a][4] == snows[b][(i+3)%6+1] &&    
            snows[a][5] == snows[b][(i+2)%6+1] &&    
            snows[a][6] == snows[b][(i+1)%6+1])    
           )    
        return true;    
    }    
    
    return false;    
}    
int main()  
{  
    freopen("1.txt","r",stdin);  
    hashTableInit();  
    memset(snows,0,sizeof(snows));  
    int n=0;  
    int flag=0;  
    scanf("%d",&n);  
    for (int i=0;i<n;i++)  
    {     
        for (int j=1;j<=6;j++)  
        {   
            scanf("%d",&snows[i][j]);  
        }  
        snows[i][0]=(snows[i][1]+snows[i][3]+snows[i][5]) ^ (snows[i][2]+snows[i][4]+snows[i][6]) ;  
        int nowpos=hashTableAdd(snows[i][0],i);  
        int serchpos=hashTableFind(snows[i][0]);  
        if(nowpos!=serchpos){  
            int first=1;  
            for (int k=serchpos;;k++)  
            {  
                k %=hashTableNums;  
                if(k == serchpos && first==0) break;  
                if( hashTableKeys[k]==initNum ) break;  
                if(k==nowpos) break;  
                if(snows[hashTableValues[nowpos]][0] ==snows[hashTableValues[k]][0]){  
                    if(isSame(hashTableValues[nowpos],hashTableValues[k])){  
                        flag=1;  
                        break;}  
                }  
            }     
        }  
        if(flag){  
            printf("Twin snowflakes found.\n");  
            break;  
        }  
    }  
    if(!flag){  
        printf("No two snowflakes are alike.\n");  
    }  
    printf("%f",(double)clock()/CLOCKS_PER_SEC);  
}  

 

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日