## pku1245-1251 Mid-Central USA 2002 比赛总结

Solved ID Title Ratio(AC/att) Yes Problem A Programmer, Rank Thyself 100.0%(3/3) Problem B Hilbert Curve Intersections 0.0%(0/0) Yes Problem C Magnificent Meatballs 100.0%(2/2) Yes Problem D Safecracker 100.0%(1/1) Yes Problem E Oil Pipeline 50.0%(1/2) Yes Problem F Tanning Salon 100.0%(1/1) Yes Problem G Jungle Roads 100.0%(1/1)

pku1245 Programmer, Rank Thyself

1 Source Code
2
3 Problem: 1245        User: yzhw
4 Memory: 584K        Time: 16MS
5 Language: G++        Result: Accepted
6 Source Code
7 //============================================================================
8 // Name        : A.cpp
9 // Author      : yzhw
10 // Version     :
11 // Copyright   : yzhw
12 // Description : Hello World in C++, Ansi-style
13 //============================================================================
14
15 # include <cstdio>
16 # include <cstring>
17 # include <cmath>
18 # include <algorithm>
19 # include <vector>
20 using namespace std;
21 struct node
22 {
23     char name[15];
24     int accept,time,mean,rank;
25     vector<int> data;
26     void init()
27     {
28         accept=0;
29         time=0;
30         mean=0;
31         data.clear();
32     }
33     void add(int t)
34     {
35         data.push_back(t);
36         if(t)
37         {
38             time+=t;
39             accept++;
40         }
41     }
42     void cal()
43     {
44         if(!accept) return;
45         double total=0;
46         for(int i=0;i<data.size();i++)
47             if(data[i])
48                 total+=log(data[i]);
49         mean=0.5+exp(total/accept);
50     }
51     bool operator<(const node&pos) const
52     {
53         if(accept!=pos.accept) return accept>pos.accept;
54         else if(time!=pos.time) return time<pos.time;
55         else if(mean!=pos.mean) return mean<pos.mean;
56         else return strcmp(name,pos.name)<0;
57     }
58     bool operator==(const node &pos) const
59     {
60         return accept==pos.accept&&time==pos.time&&mean==pos.mean;
61     }
62     void print()
63     {
64         printf("%s%d %-10s%2d%5d%4d",rank<10?"0":"",rank,name,accept,time,mean);
65         for(int i=0;i<data.size();i++)
66             printf("%4d",data[i]);
67         printf("\n");
68     }
69 }team[25];
70 int main() {
71     int n;
72     for(int test=1;scanf("%d",&n)&&n;test++)
73     {
74         for(int i=0;i<n;i++)
75         {
76             scanf("%s",team[i].name);
77             team[i].init();
78             for(int j=0;j<7;j++)
79             {
80                 int t;
81                 scanf("%d",&t);
83             }
84             team[i].cal();
85         }
86         sort(team,team+n);
87         team[0].rank=1;
88         for(int i=1;i<n;i++)
89             if(team[i]==team[i-1])
90                 team[i].rank=team[i-1].rank;
91             else
92                 team[i].rank=i+1;
93         printf("CONTEST %d\n",test);
94         for(int i=0;i<n;i++)
95             team[i].print();
96     }
97     return 0;
98 }

pku1247  Magnificent Meatballs

1 Source Code
2
3 Problem: 1247        User: yzhw
4 Memory: 704K        Time: 0MS
5 Language: G++        Result: Accepted
6 Source Code
7 //============================================================================
8 // Name        : Magnificent.cpp
9 // Author      : yzhw
10 // Version     :
11 // Copyright   : yzhw
12 // Description : Hello World in C++, Ansi-style
13 //============================================================================
14
15 #include <iostream>
16 using namespace std;
17
18 int main() {
19     int data[35],n;
20     while(cin>>n&&n)
21     {
22         data[0]=0;
23         for(int i=1;i<=n;i++)
24         {
25             cin>>data[i];
26             data[i]+=data[i-1];
27         }
28         if(data[n]%2) cout<<"No equal partitioning."<<endl;
29         else
30         {
31             bool flag=false;
32             for(int i=1;i<=n;i++)
33                 if(data[i]==data[n]/2)
34                 {
35                     flag=true;
36                     cout<<"Sam stops at position "<<i<<" and Ella stops at position "<<i+1<<"."<<endl;
37                     break;
38                 }
39             if(!flag) cout<<"No equal partitioning."<<endl;
40         }
41     }
42     return 0;
43 }

pku 1248 Safecracker

1 Source Code
2
3 Problem: 1248        User: yzhw
4 Memory: 696K        Time: 0MS
5 Language: G++        Result: Accepted
6 Source Code
7 //============================================================================
8 // Name        : Safecracker.cpp
9 // Author      : yzhw
10 // Version     :
11 // Copyright   : yzhw
12 // Description : Hello World in C++, Ansi-style
13 //============================================================================
14
15 #include <iostream>
16 #include <cstring>
17 #include <algorithm>
18 using namespace std;
19 bool used[26];
20 int target;
21 char res[6];
22 bool search(int pos,int num)
23 {
24     if(pos==5)
25        return num==target;
26     else
27     {
28         for(int i=25;i>=0;i--)
29             if(!used[i])
30             {
31                 used[i]=true;
32                 res[pos]=i+'A';
33                 switch(pos)
34                 {
35                 case 0:
36                     if(search(pos+1,num+i+1)) return true;
37                     break;
38                 case 1:
39                     if(search(pos+1,num-(i+1)*(i+1))) return true;
40                     break;
41                 case 2:
42                     if(search(pos+1,num+(i+1)*(i+1)*(i+1))) return true;
43                     break;
44                 case 3:
45                     if(search(pos+1,num-(i+1)*(i+1)*(i+1)*(i+1))) return true;
46                     break;
47                 case 4:
48                     if(search(pos+1,num+(i+1)*(i+1)*(i+1)*(i+1)*(i+1))) return true;
49                     break;
50                 }
51                 used[i]=false;
52             }
53         return false;
54     }
55 }
56 int main() {
57     char str[20];
58     while(cin>>target>>str&&(target||strcmp(str,"END")))
59     {
60         memset(used,true,sizeof(used));
61         for(int i=0;str[i]!='\0';i++)
62             used[str[i]-'A']=false;
63         res[5]='\0';
64         if(search(0,0)) cout<<res<<endl;
65         else cout<<"no solution"<<endl;
66     }
67     return 0;
68 }

PKU1250 Tanning Salon

1 Source Code
2
3 Problem: 1250        User: yzhw
4 Memory: 708K        Time: 0MS
5 Language: G++        Result: Accepted
6 Source Code
7 //============================================================================
8 // Name        : Tanning.cpp
9 // Author      : yzhw
10 // Version     :
11 // Copyright   : yzhw
12 // Description : Hello World in C++, Ansi-style
13 //============================================================================
14
15 #include <iostream>
16 #include <cstring>
17 using namespace std;
18
19 int main() {
20     int n;
21     char str[100];
22     bool used[26];
23     while(cin>>n&&n)
24     {
25         int ans=0;
26         cin>>str;
27         memset(used,false,sizeof(used));
28         for(int i=0;str[i]!='\0';i++)
29             switch(used[str[i]-65])
30             {
31             case true:
32                 used[str[i]-65]=false;
33                 n++;
34                 ans++;
35                 break;
36             case false:
37                 if(n)
38                 {
39                     n--;
40                     used[str[i]-65]=true;
41                 }
42                 break;
43             };
44             if(ans==strlen(str)/2)
45                 cout<<"All customers tanned successfully."<<endl;
46             else
47                 cout<<strlen(str)/2-ans<<" customer(s) walked away."<<endl;
48     }
49     return 0;
50 }

1 Source Code
2
3 Problem: 1251        User: yzhw
4 Memory: 696K        Time: 16MS
5 Language: G++        Result: Accepted
6 Source Code
7 //============================================================================
8 // Name        : Jungle.cpp
9 // Author      : yzhw
10 // Version     :
11 // Copyright   : yzhw
12 // Description : Hello World in C++, Ansi-style
13 //============================================================================
14
15 #include <iostream>
16 #include <algorithm>
17 #include <vector>
18 using namespace std;
19 struct node
20 {
21     int a,b;
22     int len;
23     node(int first,int second,int length):a(first),b(second),len(length){}
24     bool operator<(const node &pos) const
25     {
26         return len<pos.len;
27     }
28 };
29 vector<node> edge;
30 int n,set[26];
31 int find(int pos)
32 {
33     if(set[pos]==pos) return pos;
34     else return set[pos]=find(set[pos]);
35 }
36 int main() {
37     while(cin>>n&&n)
38     {
39         edge.clear();
40         for(int i=0;i<n;i++set[i]=i;
41         for(int i=0;i<n-1;i++)
42         {
43             int num;
44             char ori;
45             cin>>ori>>num;
46             while(num--)
47             {
48                 char to;
49                 int len;
50                 cin>>to>>len;
51                 edge.push_back(node(ori-'A',to-'A',len));
52             }
53         }
54         sort(edge.begin(),edge.end());
55         int c=0,ans=0;
56         for(int i=0;i<edge.size()&&c<n-1;i++)
57             if(find(edge[i].a)!=find(edge[i].b))
58             {
59                 set[find(edge[i].a)]=find(edge[i].b);
60                 ans+=edge[i].len;
61                 c++;
62             }
63         cout<<ans<<endl;
64     }
65     return 0;
66 }

pku1249 Oil Pipeline

trick?如果y坐标只有1位的话注意了？

1 Source Code
2
3 Problem: 1249        User: yzhw
4 Memory: 548K        Time: 16MS
5 Language: G++        Result: Accepted
6 Source Code
7 //============================================================================
8 // Name        : Oil.cpp
9 // Author      : yzhw
10 // Version     :
11 // Copyright   : yzhw
12 // Description : Hello World in C++, Ansi-style
13 //============================================================================
14
15 # include <cstdio>
16 # include <vector>
17 # include <cstring>
18 # include <algorithm>
19 using namespace std;
20 vector<int> data[100];
21 int x,y,minx,maxx,miny,maxy;
22 int GetMin(int pos)
23 {
24     int ans=pos/5*5;
25     if(ans==pos) ans-=5;
26     return ans;
27 }
28 int GetMax(int pos)
29 {
30     return (pos/5+1)*5;
31 }
32 int main() {
33     //freopen("ans.txt","w",stdout);
34     int c=0;
35     while(true)
36     {
37
38         scanf("%d%d",&x,&y);
39         if(x==0&&y==0break;
40         for(int i=1;i<=94;i++) data[i].clear();
41         data[x].push_back(y);
42         minx=maxx=x;
43         miny=maxy=y;
44         while(true)
45         {
46             scanf("%d%d",&x,&y);
47             if(x==-1&&y==-1break;
48             data[x].push_back(y);
49             minx=min(minx,x);
50             maxx=max(maxx,x);
51             miny=min(miny,y);
52             maxy=max(maxy,y);
53         }
54         for(int i=minx;i<=maxx;i++)
55             sort(data[i].begin(),data[i].end());
56         int total=0,ans=1;
57         for(y=1;y<=73;y++)
58           if(y==1)
59           {
60             for(int i=minx;i<=maxx;i++)
61                 if(!data[i].empty())
62                     {
63                         if(y>=data[i].front()&&y<=data[i].back()) total=data[i].back()-data[i].front();
64                         else if(y>data[i].back()) total=data[i].back()-data[i].front()+y-data[i].back();
65                         else total=data[i].back()-data[i].front()+data[i].front()-y;
66                     }
67             ans=y;
68           }
69           else
70           {
71               int tmp=total;
72               for(int i=minx;i<=maxx;i++)
73                   if(!data[i].empty())
74                       {
75                           if(y>data[i].front()&&y<=data[i].back());
76                           else if(y<=data[i].front()) tmp--;
77                           else tmp++;
78                       }
79               if(tmp<total)
80                   total=tmp,ans=y;
81           }
82         //print
83         printf("OIL FIELD %d\n",++c);
84         int left=GetMin(minx),right=GetMax(maxx),down=GetMin(miny),up=GetMax(maxy);
85         if(right-left>70||up-down>20) printf("Map is too big to draw for pipeline at %d\n",ans);
86         else
87         {
88             char orimap[100][100];
89             memset(orimap,'.',sizeof(orimap));
90             char *map[100];
91             for(int i=0;i<100;i++)
92                 map[i]=orimap[i];
93             //draw left border&right border
94             for(int i=down;i<=up;i++)
95             {
96                 if((i-down)%5==0)
97                 {
98                     sprintf(map[up-i],"%2d+",i);
99                     sprintf(&orimap[up-i][right-left+2],"+");
100                 }
101                 else
102                 {
103                     sprintf(map[up-i],"  |");
104                     sprintf(&orimap[up-i][right-left+2],"|");
105                 }
106                 map[up-i]+=3;
107                 *map[up-i]='.';
108             }
109             //draw up&down border
110             sprintf(orimap[up-down+1],"  %-5d",left);
111             map[up-down+1]+=7;
112             for(int i=left+1;i<right;i++)
113             {
114                 if((i-left)%5==0)
115                 {
116                     sprintf(map[up-down+1],"%-5d",i);
117                     map[up-down+1]+=5;
118                     *map[up-down]=*map[0]='+';
119                 }
120                 else
121                 {
122                     *map[up-down]=*map[0]='-';
123                 }
124                 map[up-down]++;
125                 map[0]++;
126             }
127             sprintf(map[up-down+1],"%d",right);
128             //draw N-S line
129             for(int i=down+1;i<up;i++)
130                 map[up-i]+=minx-left-1;
131             for(int i=minx;i<=maxx;i++)
132             {
133                 if(!data[i].empty())
134                     for(int j=min(ans,data[i].front());j<=max(ans,data[i].back());j++)
135                         *map[up-j]='*';
136                 for(int j=down+1;j<up;j++)
137                     map[up-j]++;
138             }
139             //draw S-E line
140             for(int i=left+1;i<right;i++)
141                 orimap[up-ans][2+i-left]='*';
142
143             //draw point
144             for(int i=minx;i<=maxx;i++)
145                 for(int j=0;j<data[i].size();j++)
146                     orimap[up-data[i][j]][i-left+2]='@';
147             for(int i=up;i>=down-1;i--)
148                 printf("%s\n",up<10?orimap[up-i]+1:orimap[up-i]);
149         }
150     }
151     return 0;
152 }

posted on 2011-01-21 02:21 yzhw 阅读(383) 评论(0)  编辑 收藏 引用 所属分类: graphdata structstring algorithm

 只有注册用户登录后才能发表评论。 【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！ 相关文章:
 < 2010年10月 >
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

• 随笔 - 183
• 文章 - 2
• 评论 - 27
• 引用 - 0

•

• 积分 - 49511
• 排名 - 449