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

第二次做比赛,有了viaxl的加入,有点动力

SolvedIDTitle
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)
其实这6道题都很水。。USA的比赛一向没有难度的

pku1245 Programmer, Rank Thyself
一道裸的排序题,不过我还是犯了一个错误。。lna1+lna2+..+lnan,我试图先将a1,a2..an乘起来,不想每注意到越界了。。
代码: 
 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);
82                 team[i].add(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
算是模拟吧,如果题目中没有这句“ Customers who leave without tanning always depart before customers who are currently tanning.”可能会难一点- -,思路直接看代码吧- -
 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 }

pku1251 Jungle Road


这个像什么?最小生成树?对了,直接拍代码吧:
 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

这题稍微烦点,其实也不难
怎么确定最优值?范围才不到100?枚举+动态更新~排下序就发现复杂度O(nm)
怎么画图?自己看着办吧,我是先画边框,再画管道,最后画点
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


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


<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜