第二次做比賽，有了viaxl的加入，有點動力
其實這6道題都很水。。USA的比賽一向沒有難度的
pku1245 Programmer, Rank Thyself一道裸的排序題，不過我還是犯了一個錯誤。。lna
1+lna
2+..+lna
n，我試圖先將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簡單數(shù)學(xué)，看下奇偶性就可以了
代碼：
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這題稍微煩點，其實也不難
怎么確定最優(yōu)值？范圍才不到100？枚舉+動態(tài)更新～排下序就發(fā)現(xiàn)復(fù)雜度O(nm)
怎么畫圖？自己看著辦吧，我是先畫邊框，再畫管道，最后畫點
trick?如果y坐標(biāo)只有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==0) break;
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==-1) break;
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 }