近期雖然沒有寫blog，但是topcoder依然沒有落下，本來想把 472 那場補(bǔ)上的。。。
但是900pt的貪心實(shí)在是太神了，不忍多想。。。。
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
一個(gè)矩陣上有若干個(gè)點(diǎn)，現(xiàn)在讓你自己設(shè)計(jì)一個(gè)加點(diǎn)的順序，每一次的局面價(jià)值是最遠(yuǎn)的兩個(gè)哈密頓距離。讓總價(jià)值最大。
一開始想貪心，后來發(fā)現(xiàn)過不了樣例。。。sad。。。
可以從后往前減，然后記憶化搜索，局面數(shù)看起來很多，實(shí)際很小，至于為什么很小，有待證明。。。。
1000pt
絕b好的一題。。。 一個(gè)矩陣上有"."和"#"兩種符號(hào)。 一次操作可以去掉（水平 / 豎直） 方向上的連續(xù)的"#"，問最少幾次去完。
最小割。。。一次操作割兩次，去掉任何一個(gè)割邊，都會(huì)讓這個(gè)矩陣的某個(gè)橫邊和豎邊聯(lián)通，真是神思想。。。
許久不敲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
西月弦 閱讀(620)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
比賽感言