bon

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

poj 3349

本来不想看discuss了,不过因为这道题拖太久了,所以还是看了一下^_^,不过算法还是自己想的。
之前程序已经做好了,但一直WA,估计不是算法的错,而是程序的错。

这道题给了两个启示:
1. 点的哈希函数:我是把坐标值(六个整数值)求和模149997,哈希表长度是150000。严蔚敏的《数据结构》指出:模的数可以选为质数或不包
    含小于20的质因数的合数。另外这个数要尽量接近哈希表长度,这样才能有效利用哈希表的空间,而不会使得数据集中在前面。

2. 有大量输入时(100000×6个整数),每个整数最长有7位,这时用getchar()输入字符再转成整数会比scanf()输入整数快很多!(2438ms VS 610ms)

3. 这道题的数据可以是这样:1 2 3 1 5 6 与 1 5 6 1 2 3是同一朵雪花,但我之前的程序没有判断出来。具体看下面程序里的equal函数。

  1 #include <iostream>
  2 #include <set>
  3 
  4 using namespace std;
  5 
  6 const int maxn=150000;
  7 struct node{
  8     node(){idx=-1;next=NULL;}
  9     node(int id){idx=id;next=NULL;}
 10     int idx;
 11     node *next;
 12 }table[maxn];
 13 
 14 int a[100010][6];
 15 int n;
 16 int hash(int *a)
 17 {
 18     //a[6]=0;
 19     __int64 sum=0;
 20     for(int i=0;i<6;i++) sum+=a[i];//*a[i]);
 21     return sum%149997;
 22 }
 23 
 24 void init()
 25 {
 26     for(int i=0;i<n;i++){
 27         table[i].idx=-1;
 28         table[i].next=NULL;
 29     }
 30 }
 31 
 32 bool equal(int i,int j)
 33 {
 34     //if(a[i][6]!=a[j][6]) return false;
 35     int x,yy=0,y;
 36     int flag=0;
 37     while(yy<6){
 38         while(yy<6 && a[j][yy]!=a[i][0]) yy++;
 39         if(yy==6return false;
 40         y=yy;
 41         for(x=0;x<6;x++){
 42             if(a[i][x]==a[j][y]){
 43                 y++;
 44                 if(y==6) y=0;
 45             }
 46             else break;
 47         }
 48         if(x==6return true;
 49         y=yy;
 50         for(x=0;x<6;x++){
 51             if(a[i][x]==a[j][y]){
 52                 y--;
 53                 if(y==-1) y=5;
 54             }
 55             else break;
 56         }
 57         if(x==6return true;
 58         yy++;
 59     }
 60     return false;
 61 }
 62 
 63 // 读入字符并转成整数
 64 void readNumber(int i)
 65 {
 66     char ch;
 67     //ch=getchar();
 68     ch=getchar();
 69     while(ch==' ') ch=getchar();
 70     int x=0;
 71     while(ch!=' ') {x*=10;x+=ch-'0';ch=getchar();}
 72     a[i][0]=x;
 73 
 74     ch=getchar();
 75     while(ch==' ') ch=getchar();
 76     x=0;
 77     while(ch!=' ') {x*=10;x+=ch-'0';ch=getchar();}
 78     a[i][1]=x;
 79 
 80     ch=getchar();
 81     while(ch==' ') ch=getchar();
 82     x=0;
 83     while(ch!=' ') {x*=10;x+=ch-'0';ch=getchar();}
 84     a[i][2]=x;
 85 
 86     ch=getchar();
 87     while(ch==' ') ch=getchar();
 88     x=0;
 89     while(ch!=' ') {x*=10;x+=ch-'0';ch=getchar();}
 90     a[i][3]=x;
 91 
 92     ch=getchar();
 93     while(ch==' ') ch=getchar();
 94     x=0;
 95     while(ch!=' ') {x*=10;x+=ch-'0';ch=getchar();}
 96     a[i][4]=x;
 97 
 98     ch=getchar();
 99     while(ch==' ') ch=getchar();
100     x=0;
101     while(ch!=10 && ch!=' ')
102     {
103         x*=10;
104         x+=ch-'0';
105         ch=getchar();
106     }
107     a[i][5]=x;
108     if(ch==' '){
109         ch=getchar();
110         while(ch!=10) ch=getchar();
111     }
112 }
113 
114 bool solve()
115 {
116     scanf("%d",&n);
117     getchar();
118     //init();
119     int i,flag=0;
120     node *tmp,*tmp2;
121     for(i=0;i<&& !flag;i++){
122         //scanf("%d%d%d%d%d%d",&a[i][0],&a[i][1],&a[i][2],&a[i][3],&a[i][4],&a[i][5]);
123         readNumber(i);
124         int code=hash(a[i]);
125         if(table[code].idx==-1){
126             table[code].idx=i;
127         }else{
128             //flag=0;
129             tmp2=NULL;
130             tmp=&(table[code]);
131             while(tmp!=NULL){
132                 if(equal(i,tmp->idx)) {flag=1;break;}
133                 tmp2=tmp;
134                 tmp=tmp->next;
135             }
136             if(!flag) tmp2->next=new node(i);
137         }
138     }
139     //printf("%d\n",i);
140     /*
141     int aa,bb,cc,xx,yy,zz;
142     
143     if(i<n){
144         for(;i<n;i++) scanf("%d%d%d%d%d%d",&aa,&bb,&cc,&xx,&yy,&zz);
145     }
146     */
147     if(flag) return true;
148     return false;
149 }
150 
151 int main()
152 {
153     //freopen("in.txt","r",stdin);
154     if(solve()) printf("Twin snowflakes found.\n");
155     else printf("No two snowflakes are alike.\n");
156     return 1;
157 }
158 
159 
160 

posted on 2008-05-24 11:34 bon 阅读(1005) 评论(1)  编辑 收藏 引用 所属分类: Programming Contest

Feedback

# re: pku 3349 2009-06-24 17:07 sum
大哥超时 勒  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Google PageRank 
Checker - Page Rank Calculator