近期虽然没有写blog，但是topcoder依然没有落下，本来想把 472 那场补上的。。。
但是900pt的贪心实在是太神了，不忍多想。。。。
250pt
求期望的简单题，不知道为啥好多人没过。。。。
250pt
1 #include<iostream>
2 #include<cstdio>
3 #include<vector>
4 #include<sstream>
5 #include<string>
6 #include<algorithm>
7 using namespace std;
8 int num[1001];
9 class EllysRoomAssignmentsDiv1{
10 public : double getAverage(vector <string> ratings){
11 string ch = "";
12 for(int i = 0; i < ratings.size(); i++)
13 ch += ratings[i];
14 stringstream sin(ch);
15 int len = 0;
16 while(sin >> num[len]) len ++;
17 int R = len % 20 == 0 ? len / 20 : len / 20 + 1;
18 int el = num[0];
19 double ans = 0, cnt = 0;
20 sort(num,num+len);
21 reverse(num,num+len);
22 for(int i = 0; i < len; i+= R){
23 bool flag = 0;
24 double sum = 0;
25 for(int j = i ; j < i + R && j < len; j++){
26 if(el == num[j]) flag = 1;
27 sum += num[j];
28 }
29 if(flag) {ans += el, cnt += 1;if(i + R >= len) ans /= cnt; continue; }
30 if(len - i <= R) {
31 double c = len - i;
32 double p1 = c/R;
33 double p2 = 1-p1;
34 double ans1 = (ans + sum / c) / (cnt + 1);
35 double ans2 = (ans) / cnt;
36 ans = ans1 * p1 + ans2 * p2;
37 } else {
38 ans += sum / R;
39 cnt += 1;
40 }
41 }
42 return ans;
43 }
44 500pt
一个矩阵上有若干个点，现在让你自己设计一个加点的顺序，每一次的局面价值是最远的两个哈密顿距离。让总价值最大。
一开始想贪心，后来发现过不了样例。。。sad。。。
可以从后往前减，然后记忆化搜索，局面数看起来很多，实际很小，至于为什么很小，有待证明。。。。
1000pt
绝b好的一题。。。 一个矩阵上有"."和"#"两种符号。 一次操作可以去掉（水平 / 竖直） 方向上的连续的"#"，问最少几次去完。
最小割。。。一次操作割两次，去掉任何一个割边，都会让这个矩阵的某个横边和竖边联通，真是神思想。。。
许久不敲dinic，居然一次编译通过。。。我真是爱我自己。。。
1000pt
1 #include<vector>
2 #include<string>
3 #include<iostream>
4 #include<cstdio>
5 using namespace std;
6 #define pt(i,j) i*m+j+1
7 const int N = 50 * 50 + 5;
8 int G[N][N], level[N], Q[N];
9 bool bfs(int n){
10 for(int i = 0; i <= n; i++)
11 level[i] = -1;
12 level[0] = 0;
13 Q[0] = 0;
14 int head = 0, tail = 1;
15 while(head < tail){
16 int u = Q[head ++];
17 for(int v = 0; v <= n; v++) if(level[v] == -1 && G[u][v]){
18 level[v] = level[u] + 1;
19 Q[tail ++] = v;
20 }
21 }
22 cout<<"lvl: ";
23 for(int i = 0 ; i <= n; i++) cout<< level[i]<<" ";cout<<endl;
24 return level[n] != -1;
25 }
26 int dfs(int u,int c,int n){
27 if(n == u) return c;
28 int t, res = 0;
29 cout<<"dfs: "<<u<<" "<<c<<endl;
30 for(int v = 0; v <= n ; v ++) if(level[v] == level[u] + 1 && G[u][v]){
31 t = min(c - res, G[u][v]); if(t) t = dfs(v,t,n);
32 res += t; G[u][v] -= t; G[v][u] += t;
33 }
34 if(res == 0) level[u] = -1;
35 cout<<"bk: "<<u<<" "<<res<<endl;
36 return res;
37 }
38
39 class BoardPainting{
40 public : int minimalSteps(vector <string> target){
41 int n = target.size(), m = target[0].size();
42 int len = n * m;
43 int s = 0, t = len + 1;
44 for(int i = 0; i < n; i++)
45 for(int j = 0; j < m; j++) if(target[i][j] == '#'){
46 for(int p = 0; p < 4; p++){
47 int x = i + (p == 0) - (p == 1);
48 int y = j + (p == 2) - (p == 3);
49 if(x>=0 && x < n && y >=0 && y < m && target[x][y] == '#'){
50 G[pt(x,y)][pt(i,j)] ++;
51 } else if(p < 2){
52 G[pt(i,j)][t] ++;
53 } else {
54 G[s][pt(i,j)] ++;
55 }
56 }
57 }
58 /*
59 for(int i = 0; i <= t; i++){
60 for(int j = 0; j <= t; j++)
61 cout<<G[i][j]<<" "; cout<<endl;}
62 */
63 int ans = 0;
64 while(bfs(t)) ans += dfs(0,(int)1e9,t);
65 return ans/2;
66 }
67
posted on 2013-06-01 01:09
西月弦 阅读(608)
评论(1) 编辑 收藏 引用 所属分类:
比赛感言