解題區/解題區 - UVa

UVa 1063 - Marble Game

Problem

旋轉盤面，讓每顆球落入屬於自己的洞，請問至少需要幾次旋轉。

  • 球不能翻過牆壁、不能跨越其他球、不能飛過空洞。
  • 球不能離開盤面
  • 每一格最多只有一顆球
  • 當球落入空洞時，這個空洞相當於被填滿，其他的球可以經過這個被填滿的洞，但無法再次落入該洞。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
4 3 1
0 1 
1 0 
1 2 
2 3 
2 1 
3 2 
1 1 1 2
3 2 2
0 0 
0 1 
0 2 
2 0 
2 0 1 0
2 0 2 1
0 0 0

Sample Output

1
2
3
Case 1: 5 moves 
Case 2: impossible

Solution

首先有可能落錯空洞，模擬時必須特別小心這種非法的旋轉。在一次操作中，有可能在落入空洞的瞬間，下一個球剛好可以通過這個填滿的洞。

將每個球的座標壓成狀態，進行 Bfs 搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include <stdio.h>
#include <queue>
#include <map>
#include <string.h>
#include <algorithm>
using namespace std;
int N, W;
struct state {
    vector< pair<int, int> > xy;
    bool operator<(const state &a) const {
        for (int i = 0; i < xy.size(); i++)
            if (xy[i] != a.xy[i])
                return xy[i] < a.xy[i];
        return false;
    }
    int isComplete() {
        int ok = 1;
        for (int i = 0; i < xy.size() && ok; i++)
            ok &= xy[i].first < 0;
        return ok;
    } 
};
int g[4][4][4];
pair<int, int> goal[64];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int isValid(int x, int y) {
    return x >= 0 && y >= 0 && x < W && y < W;
}
state eraseGoal(state u) {
    for (int i = 0; i < u.xy.size(); i++) {
        if (u.xy[i] == goal[i])
            u.xy[i] = pair<int, int>(-1, -1);
    }
    return u;
}
state rotateMap(state u, int dir, int& ok) {
    ok = 1;
    int update = 1, tx, ty, x, y;
    int used[4][4] = {}, usedg[4][4] = {};
    for (int i = 0; i < u.xy.size(); i++) {
        x = u.xy[i].first, y = u.xy[i].second;
        if (x == -1)	continue;
        used[x][y] = 1;
        x = goal[i].first, y = goal[i].second;
        usedg[x][y] = i+1;
    }
    do {
        update = 0;
        for (int i = 0; i < u.xy.size(); i++) {
            while (u.xy[i].first >= 0) {
                x = u.xy[i].first, y = u.xy[i].second;
                tx = x + dx[dir], ty = y + dy[dir];
                if (isValid(tx, ty) && !g[x][y][dir] && usedg[tx][ty] && usedg[tx][ty] != i+1)
                    ok = 0;
                if (isValid(tx, ty) && !g[x][y][dir] && (!used[tx][ty] || goal[i] == make_pair(tx, ty))) {
                    used[x][y] = 0, used[tx][ty] = 1;
                    u.xy[i] = pair<int, int>(tx, ty);
                    update = 1;
                    if (goal[i] == pair<int, int>(tx, ty)) {
                        u.xy[i] = pair<int, int>(-1, -1);
                        used[tx][ty] = 0, usedg[tx][ty] = 0;
                    }
                } else {
                    break;
                }
            }
        } 
    } while (update);
    return u;
}
void print(state u) {
    int used[4][4] = {}, x, y;
    for (int i = 0; i < u.xy.size(); i++) {
        x = u.xy[i].first, y = u.xy[i].second;
        if (x == -1)
            continue;
        used[x][y] = i+1;
    }
    for (int i = 0; i < W; i++) {
        for (int j = 0; j < W; j++)
            printf("%d ", used[i][j]);
        puts("");
    }
    puts("--");
}
int bfs(state init) {
    state u, v;
    queue<state> Q;
    map<state, int> R;
    int f;
    
    init = eraseGoal(init);
    Q.push(init), R[init] = 0;
//	print(init);
    if (init.isComplete())
        return 0;
    
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        int step = R[u];
        
//		print(u);
//		printf("step %d\n", step);
        for (int i = 0; i < 4; i++) {
            v = rotateMap(u, i, f);
            v = eraseGoal(v);
            if (!f || R.count(v))		continue;
            if (v.isComplete())
                return step + 1;
            R[v] = step + 1;
//			print(v);
            Q.push(v);
        }
//		puts("--------------");
//		getchar();
    }
    return -1;
}
int main() {
    int x, y, tx, ty, M;
    int sx, sy, ex, ey;
    int cases = 0;
    while (scanf("%d %d %d", &W, &N, &M) == 3 && N+W+M) {
        state init;
        memset(g, 0, sizeof(g));
        
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &x, &y);
            init.xy.push_back(pair<int, int>(x, y));
        }
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &x, &y);
            goal[i] = pair<int, int>(x, y);
        }
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
            for (int j = 0; j < 4; j++) {
                tx = sx + dx[j], ty = sy + dy[j];
                if (tx == ex && ty == ey)
                    g[sx][sy][j] = 1;
                tx = ex + dx[j], ty = ey + dy[j];
                if (tx == sx && ty == sy)
                    g[ex][ey][j] = 1;
            }
        }
        
        int step = bfs(init);
        
        printf("Case %d: ", ++cases);
        if (step < 0)
            puts("impossible");
        else
            printf("%d moves\n", step);
        puts("");
    }
    return 0;
}
/*
3 1 5
1 2
1 0
2 1 2 2
0 0 1 0
0 1 1 1
0 2 1 2
1 1 2 1
4 3 1
0 1 
1 0 
1 2 
2 3 
2 1 
3 2 
1 1 1 2
3 2 2
0 0 
0 1 
0 2 
2 0 
2 0 1 0
2 0 2 1
*/
Read More +
解題區/解題區 - UVa

UVa 1049 - Remember the A La Mode

Problem

販售冰淇淋。

已知每一種口味的冰淇淋、不同種的冰淇淋脆皮的庫存量，也已知冰淇淋口味與脆皮之間搭配獲得的利益。

求出在兜售完畢的情況下，最大獲益、最小獲益分別為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2 3 
40 50 
27 30 33 
1.11 1.27 0.70 
-1 2 0.34 
4 4 
10 10 10 10 
10 10 10 10 
1.01 -1 -1 -1 
-1 1.01 -1 -1 
-1 -1 1.01 -1 
-1 -1 -1 1.01 
0 0

Sample Output

1
2
Problem 1: 91.70 to 105.87 
Problem 2: 40.40 to 40.40

Solution

保證在兜售完畢的情況下，相當於 maxflow 流滿，那麼可以套用最少費用流來找到最少利益。為了解決最大獲益，取個補數來套用最少費用流模型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <stdio.h>
#include <string.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;
#define MAXN 2048
#define MAXM 1048576
struct Node {
    int x, y, cap;
    double cost;// x->y, v
    int next;
} edge[MAXM];
class MinCost {
public:
    int e, head[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
    int dis[MAXN];
    int n;
    const int INF = 0x3f3f3f3f;
    void Addedge(int x, int y, int cap, int cost) {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].next = head[x], head[x] = e++;
        edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
        edge[e].next = head[y], head[y] = e++;
    }
    pair<int, int> mincost(int s, int t) {
        int mncost = 0;
        int flow, totflow = 0;
        int i, x, y;
        while(1) {
        	for (int i = 0; i < n; i++)
        		dis[i] = INF;
            int oo = dis[0];
            dis[s] = 0;
            deque<int> Q;
            Q.push_front(s);
            while(!Q.empty()) {
                x = Q.front(), Q.pop_front();
                inq[x] = 0;
                for(i = head[x]; i != -1; i = edge[i].next) {
                    y = edge[i].y;
                    if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                        dis[y] = dis[x] + edge[i].cost;
                        pre[y] = x, record[y] = i;
                        if(inq[y] == 0) {
                            inq[y] = 1;
                            if(Q.size() && dis[Q.front()] > dis[y])
                                Q.push_front(y);
                            else
                                Q.push_back(y);
                        }
                    }
                }
            }
            if(dis[t] == oo)
                break;
            flow = 0x3f3f3f3f;
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                flow = min(flow, edge[ri].cap);
            }
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                edge[ri].cap -= flow;
                edge[ri^1].cap += flow;
                edge[ri^1].cost = -edge[ri].cost;
            }
            totflow += flow;
            mncost += dis[t] * flow;
        }
        return make_pair(mncost, totflow);
    }
    void init(int n) {
    	this->n = n;
        e = 0;
        for (int i = 0; i <= n; i++)
            head[i] = -1;
    }
} g;
int readDouble() {
    static char s[16];
    scanf("%s", s);
    if (s[0] == '-')	return -1;
    int i, x = 0;
    for (i = 0; s[i] && s[i] != '.'; i++)
        x = x * 10 + s[i] - '0';
    if (!s[i])	return x * 100;
    i++;
    x = x * 10 + s[i] - '0';
    if(!s[i+1]) return x * 10;
    i++;
    x = x * 10 + s[i] - '0';
    return x;
}
int main() {
    int N, M, Nsz[64], Msz[64], cases = 0;
    int NMp[64][64];
    while (scanf("%d %d", &N, &M) == 2 && N) {
    	
  		for (int i = 0; i < N; i++)
            scanf("%d", &Nsz[i]);
        for (int i = 0; i < M; i++)
        	scanf("%d", &Msz[i]);
        for (int i = 0; i < N; i++)
        	for (int j = 0; j < M; j++)
        		NMp[i][j] = readDouble();
        	
        int source = N + M, sink = N + M + 1;
        g.init(N + M + 2);
        for (int i = 0; i < N; i++) 
        	g.Addedge(source, i, Nsz[i], 0);
        for (int i = 0; i < M; i++) 
        	g.Addedge(i + N, sink, Msz[i], 0);
        for (int i = 0; i < N; i++) {
        	for (int j = 0; j < M; j++) {
        		if (NMp[i][j] < 0) 	continue;
        		g.Addedge(i, j + N, 0x3f3f3f3f, NMp[i][j]);
        	}
        }
        pair<int, int> ret1 = g.mincost(source, sink);
        
        g.init(N + M + 2);
        for (int i = 0; i < N; i++) 
        	g.Addedge(source, i, Nsz[i], 0);
        for (int i = 0; i < M; i++) 
        	g.Addedge(i + N, sink, Msz[i], 0);
        	
        const int ADD = 50 * 100 * 2000;
        for (int i = 0; i < N; i++) {
        	for (int j = 0; j < M; j++) {
        		if (NMp[i][j] < 0) 	continue;
        		g.Addedge(i, j + N, 0x3f3f3f3f, ADD - NMp[i][j]);
        	}
        }
        pair<int, int> ret2 = g.mincost(source, sink);
        double r1, r2;
        r1 = ret1.first / 100.0;
        r2 = (ret2.second * ADD - ret2.first) / 100.0;
        printf("Problem %d: ", ++cases);
 		printf("%.2lf to %.2lf\n", r1, r2);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1048 - Low Cost Air Travel

Problem

給定多組組合票價的方案，以及目標的通行順序，請問最少花費需要多少。

組合票必須按照順序使用，當沒有使用完時，選擇將組合票拋棄。組合票之間，不會發生交替使用剩餘的部分，意即手上只能持有一張組合票，之前用到一半的組合票都必須拋棄。

目標的行程順序，走訪時中間可能會多繞路，但必須依序走訪目的地。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
3 
225 3 1 3 4 
200 2 1 2 
50 2 2 3 
1 
2 1 3 
3 
100 2 2 4 
100 3 1 4 3 
200 3 1 2 3 
2 
3 1 4 3 
3 1 2 4 
0

Sample Output

1
2
3
4
5
6
Case 1, Trip 1: Cost = 225
  Tickets used: 1
Case 2, Trip 1: Cost = 100
  Tickets used: 2
Case 2, Trip 2: Cost = 300
  Tickets used: 3 1

Solution

建圖方面相當麻煩，特別小心，有可能會在行程外的地點換組合票使用。

每個點的狀態為 (i, j)，表示完成行程中第 i 個目的地，當前位置在地圖編號 j。因此針對每一個組合票，嘗試建造從行程中的第 i 個目的地，到下一個目的地。

隨後求最短路徑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <queue>
#include <map>
using namespace std;
const int MAXNT = 32767;
vector<int> route[MAXNT];
int NTc[MAXNT], NT;
struct Edge {
    int to, w, label;
    Edge(int a = 0, int b = 0, int c = 0):
        to(a), w(b), label(c) {}
};
vector<Edge> g[MAXNT];
map< pair<int, int>, int> Rid;
int getId(pair<int, int> x) {
    if (Rid.count(x))
        return Rid[x];
    int &r = Rid[x];
    return r = Rid.size();
}
pair<int, int> dist[MAXNT];
int pre[MAXNT][2], inq[MAXNT];
void spfa(int st) {
    memset(dist, 63, sizeof(dist));
    memset(pre, -1, sizeof(pre));
    memset(inq, 0, sizeof(inq));
    
    int u, v;
    queue<int> Q;
    
    Q.push(st), dist[st] = pair<int, int>(0, 0);
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].to;
            if (dist[v] > pair<int, int>(dist[u].first + g[u][i].w, dist[u].second+1)) {
                dist[v] = pair<int, int>(dist[u].first + g[u][i].w, dist[u].second+1);
                pre[v][0] = u, pre[v][1] = g[u][i].label;
                if (!inq[v]) {
                    inq[v] = 1, Q.push(v);
                }
            }
        }
    }
}
void solve(int N, int A[]) {
    for (int i = 0; i < MAXNT; i++) 
        g[i].clear();
    Rid.clear();
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < NT; j++) {
            int st = i, ed = i;
            for (int k = 0; k < route[j].size(); k++) {
                if (ed+1 < N && route[j][k] == A[ed+1])
                    ed++;
                int u = getId(pair<int, int>(st, route[j][0]));
                int v = getId(pair<int, int>(ed, route[j][k]));
                g[u].push_back(Edge(v, NTc[j], j));
//				printf("[%d] %d -> %d\n", j, u, v);
                if (ed == N)
                    break;
            }
        }
    }
    
    int st = getId(pair<int, int>(0, A[0]));
    int ed = getId(pair<int, int>(N-1, A[N-1]));
    spfa(st);
    
    vector<int> buy;
    for (int i = ed; i >= 0; i = pre[i][0])
        buy.push_back(pre[i][1]);
    printf("Cost = %d\n", dist[ed].first);
    printf("  Tickets used:");
    for (int i = (int) buy.size() - 2; i >= 0; i--)
        printf(" %d", buy[i]+1);
    puts("");
}
int main() {
    int N, Q, cases = 0;
    int A[MAXNT];
    while (scanf("%d", &NT) == 1 && NT) {
        for (int i = 0; i < NT; i++) {
            int m, x;
            scanf("%d %d", &NTc[i], &m);
            route[i].clear();
            for (int j = 0; j < m; j++) {
                scanf("%d", &x);
                route[i].push_back(x);
            }
        }
        
        scanf("%d", &Q), ++cases;
        for (int i = 0; i < Q; i++) {
            scanf("%d", &N);
            for (int j = 0; j < N; j++)
                scanf("%d", &A[j]);
            printf("Case %d, Trip %d: ", cases, i+1);
            solve(N, A);
        }
    }
    return 0;
} 
/*
3 
225 3 1 3 4 
200 2 1 2 
50 2 2 3 
3
2 1 3 
1 1
0
3 
100 2 2 4 
100 3 1 4 3 
200 3 1 2 3 
2 
3 1 4 3 
3 1 2 4 
0
*/
Read More +
解題區/解題區 - UVa

UVa 1555 - Garland

Problem

給定 N 盞燈，第一盞燈的所在高度 A。

  • Hi = (Hi-1 + Hi+1)/2 - 1

在 Hi 不低於地面高度 0 的條件下，請問最後一盞燈的高度最低為何。

Sample Input

1
692 532.81

Sample Output

1
446113.34

Solution

二分搜尋第二盞燈的高度，推算出所有燈的高度，必且找最小高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
double isValid(int N, double H1, double H2) {
    double H = 0;
    for (int i = 3; i <= N; i++) {
        H = 2 * H2 + 2 - H1;
        if (H < 0)	return -1;
        H1 = H2;
        H2 = H;
    }
    return H;
}
int main() {
    int N;
    double A;
    while (scanf("%d %lf", &N, &A) == 2) {
        double l = 0, r = A, mid, ret = 0, t;
        for (int it = 0; it < 50; it++) {
            mid = (l + r)/2;
            if ((t = isValid(N, A, mid)) >= 0)
                r = mid, ret = t;
            else
                l = mid;
        }
        printf("%.2lf\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12477 - Good Measures of Dispersion

Problem

詢問區間最大值、最小值、標準差

  • 修改區間內所有元素 A[l, r] = val。
  • 增加區間內所有元素 A[l, r] += val。

Sample Input

1
2
3
4
5
6
7
8
9
1
9 6
-1 3 2 4 -2 8 0 5 -7
2 3 6
0 5 5 2
2 3 6
1 4 7 1
2 3 7
2 1 1

Sample Output

1
2
3
4
5
Case 1:
13/1 10
6/1 6
8/1 8
0/1 0

Solution

利用線段樹的懶操作，解決區間修改問題。

特別注意到區間的 assign 優先權高於 add，當懶操作 assign 被指派時，取消 add。將懶操作標記在節點 x 上，其 x 已經統計好結果，若發生要走訪 x 的子樹，將標記傳遞給子樹。

標準差的部分，可以利用 平方和 和 總和 計算之，因此紀錄總共需要四項 sum, sqr, mx, mn 來完成此題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <stdio.h> 
#include <algorithm>
using namespace std;
const int MAXN = 524288;
class SegmentTree {
public:
    struct Node {
        long long sum, sqr, mx, mn;
        pair<int, long long> label[2];
        void init() {
            sum = sqr = 0;
            mx = -1LL<<60, mn = 1LL<<60;
            label[0] = label[1] = make_pair(0, 0);
        }
    } nodes[MAXN];
    long long A[MAXN];
    void pushDown(int k, int l, int r) {
        int mid = (l + r)/2;
        if (nodes[k].label[0].first) {
            assignUpdate(k<<1, l, mid, nodes[k].label[0].second);
            assignUpdate(k<<1|1, mid+1, r, nodes[k].label[0].second);
            nodes[k].label[0] = make_pair(0, 0); // cancel
        }
        if (nodes[k].label[1].first) {
            addUpdate(k<<1, l, mid, nodes[k].label[1].second);
            addUpdate(k<<1|1, mid+1, r, nodes[k].label[1].second);
            nodes[k].label[1] = make_pair(0, 0); // cancel
        }
    }
    void pushUp(int k) {
        nodes[k].sum = nodes[k<<1].sum + nodes[k<<1|1].sum;
        nodes[k].sqr = nodes[k<<1].sqr + nodes[k<<1|1].sqr;
        nodes[k].mx = max(nodes[k<<1].mx, nodes[k<<1|1].mx);
        nodes[k].mn = min(nodes[k<<1].mn, nodes[k<<1|1].mn);
    }
    void build(int k, int l, int r) { 
        nodes[k].init();
        if (l == r) {
            nodes[k].sum = A[l];
            nodes[k].sqr = A[l] * A[l];
            nodes[k].mx = nodes[k].mn = A[l];
            return ;
        }
        int mid = (l + r)/2;
        build(k<<1, l, mid);
        build(k<<1|1, mid+1, r);
        pushUp(k);
    } 
    // operator, assign > add
    void assignUpdate(int k, int l, int r, long long val) {
        nodes[k].label[0] = make_pair(1, val);
        nodes[k].label[1] = make_pair(0, 0); // cancel lower priority
        nodes[k].sum = (long long) (r - l + 1) * val;
        nodes[k].sqr = (long long) (r - l + 1) * val * val;
        nodes[k].mn = nodes[k].mx = val;
    }
    void addUpdate(int k, int l, int r, long long val) {
        nodes[k].label[1].first = 1;
        nodes[k].label[1].second += val;
        nodes[k].sqr += 2LL * val * nodes[k].sum + (long long) (r - l + 1) * val * val;
        nodes[k].sum += (long long) (r - l + 1) * val;
        nodes[k].mn += val;
        nodes[k].mx += val;
    }
    void assign(int k, int l, int r, int x, int y, int val) {
        if (x <= l && r <= y) {
            assignUpdate(k, l, r, val);
            return;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            assign(k<<1, l, mid, x, y, val);
        if (y > mid)
            assign(k<<1|1, mid+1, r, x, y, val);
        pushUp(k);
    }
    void add(int k, int l, int r, int x, int y, int val) {
        if (x <= l && r <= y) {
            addUpdate(k, l, r, val);
            return;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            add(k<<1, l, mid, x, y, val);
        if (y > mid)
            add(k<<1|1, mid+1, r, x, y, val);
        pushUp(k);
    }
    // query 
    long long r_sum, r_sqr, r_mx, r_mn;
    void qinit() {
        r_sum = r_sqr = 0;
        r_mx = -1LL<<60, r_mn = 1LL<<60;
    }
    void query(int k, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            r_sum += nodes[k].sum;
            r_sqr += nodes[k].sqr;
            r_mx = max(r_mx, nodes[k].mx);
            r_mn = min(r_mn, nodes[k].mn);
            return ;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            query(k<<1, l, mid, x, y);
        if (y > mid)
            query(k<<1|1, mid+1, r, x, y);
    }
} tree;
long long llgcd(long long x, long long y) {
    long long t;
    while (x%y)
        t = x, x = y, y = t%y;
    return y;
}
int main() {
    int testcase, cases = 0;
    int n, q;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &q);
        for (int i = 1; i <= n; i++)
            scanf("%lld", &tree.A[i]);
            
        tree.build(1, 1, n);
        
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < q; i++) {
            int cmd, l, r, val;
            scanf("%d", &cmd);
            if (cmd == 0) { // assign [l, r] = val
                scanf("%d %d %d", &l, &r, &val);
                tree.assign(1, 1, n, l, r, val);
            } else if (cmd == 1) { // add [l, r] = val
                scanf("%d %d %d", &l, &r, &val);
                tree.add(1, 1, n, l, r, val);
            } else if (cmd == 2) {
                scanf("%d %d", &l, &r);
                
                tree.qinit();
                tree.query(1, 1, n, l, r);
                
                long long m = (r - l + 1), g;
                long long a = tree.r_sqr * m - tree.r_sum * tree.r_sum;
                long long b = m * m;
                g = llgcd(a, b);
                a /= g, b /= g;
                printf("%lld/%lld ", a, b);
                printf("%lld\n", tree.r_mx - tree.r_mn);
            }
        }
    }
    return 0;
}
/*
999
9 6
-1 3 2 4 -2 8 0 5 -7
2 3 6
0 5 5 2
2 3 6
1 4 7 1
2 3 7
2 1 1
9 6
-1 3 2 4 -2 8 0 5 -7
2 3 6
0 5 5 2
2 3 6
1 4 7 1
2 3 7
2 1 1
*/
Read More +
解題區/解題區 - UVa

UVa 11098 - Battle II

Problem

每個炸彈都有引爆範圍、炸彈半徑、以及炸彈所在座標。

  • 引爆一個炸彈時，其爆炸範圍內的其他炸彈也會被引爆，產生連鎖反應一次引爆多顆炸彈。
  • 引爆過的炸彈，無法再次引爆。
  • 引爆一個炸彈的成本與爆炸範圍成正比 1 : 1。

求平均花費 (引爆總花費 / 引爆次數) 最小為何？

Sample Input

1
2
3
4
5
6
1
3
4 7 2 2
8 5 1 0
3 -3 1 1

Sample Output

1
Case #1: 1 0 2

Solution

問平均最少花費是有原因的，如果只問最少花費只需要引爆無法被連鎖的炸彈，或者在 SCC 連通元件中找一個花費最小的炸彈。

首先，在一個連鎖反應下，先做 SCC 進行縮點，知道一個 SCC 元件中用花費最小的那個炸彈代表即可，將圖轉換成 DAG 後。indegree = 0 的點必然需要手動引爆，在這樣的情況下，已經能讓所有炸彈引爆。

為了要讓平均花費最小，勢必增加引爆炸彈的數量，引爆時便能降低平均花費，但引爆的順序必須按照拓樸排序，否則會違反 引爆過的炸彈，無法再次引爆 的規則。

藉此，根據貪心策略，將非 indegree = 0 的炸彈拿出，按照花費由小到大排序，從花費小的炸彈開始嘗試，直到平均花費無法變得更小。

選定哪個炸彈需要引爆後，仍要按照拓樸排序的方式輸出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
// SCC, DAG, greedy
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN = 1024;
class SCC {
public:
    int n;
    vector<int> g[MAXN], dag[MAXN];
    // <SCC begin>
    int vfind[MAXN], findIdx;
    int stk[MAXN], stkIdx;
    int in_stk[MAXN], visited[MAXN];
    int contract[MAXN];
    int scc_cnt;
    // <SCC end>
    int scc(int u) {
        in_stk[u] = visited[u] = 1;
        stk[++stkIdx] = u, vfind[u] = ++findIdx;
        int mn = vfind[u], v;
        for(int i = 0; i < g[u].size(); i++) {
        	v = g[u][i];
            if(!visited[v])
                mn = min(mn, scc(v));
            if(in_stk[v])
                mn = min(mn, vfind[v]);
        }
        if(mn == vfind[u]) {
            do {
                in_stk[stk[stkIdx]] = 0;
                contract[stk[stkIdx]] = scc_cnt;
            } while(stk[stkIdx--] != u);
            scc_cnt++;
        }
        return mn;
    }
    void addEdge(int u, int v) { // u -> v
        g[u].push_back(v);
    }
    void solve() {
        for (int i = 0; i < n; i++)
            visited[i] = in_stk[i] = 0;
        scc_cnt = 0;
        for (int i = 0; i < n; i++) {
        	if (visited[i])	continue;
        	stkIdx = findIdx = 0;
        	scc(i);
        }
    }
    void make_DAG() {
        int x, y;
        for (int i = 0; i < n; i++) {
            x = contract[i];
            for (int j = 0; j < g[i].size(); j++) {
                y = contract[g[i][j]];
                if (x != y)
                    dag[x].push_back(y);
            }
        }
        for (int i = 0; i < scc_cnt; i++) {
            sort(dag[i].begin(), dag[i].end());
            dag[i].resize(unique(dag[i].begin(), dag[i].end()) - dag[i].begin());
        }
    }
    void init(int n) {
        this->n = n;
        for (int i = 0; i < n; i++)
            g[i].clear(), dag[i].clear();
    }
} g;
int X[MAXN], Y[MAXN], E[MAXN], R[MAXN];
void greedy() {
    int m = g.scc_cnt, n = g.n;
    int cost[MAXN], scc_id[MAXN], pick[MAXN] = {};
    for (int i = 0; i < m; i++)
        cost[i] = 0x3f3f3f3f, scc_id[i] = -1;
    for (int i = 0; i < n; i++) {
        if (cost[g.contract[i]] > E[i])
            cost[g.contract[i]] = E[i], scc_id[g.contract[i]] = i;
    }
    
    int indeg[MAXN]	= {};
    vector<int> topo;
    queue<int> Q;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < g.dag[i].size(); j++) {
            indeg[g.dag[i][j]]++;
        }
    }
        
    // greedy, let reta / retb = minimum value
    // if (reta / retb) > (reta + cost) / (retb + 1)
    long long reta = 0, retb = 0; // min average cost = total cost / #bomb
    vector< pair<int, int> > candidate;
    for (int i = 0; i < m; i++) {
        if (indeg[i] == 0) {
            reta += cost[i], retb++;
            pick[i] = 1;
        } else {
            candidate.push_back(make_pair(cost[i], i));
        }
    }
    sort(candidate.begin(), candidate.end()); 
    for (int i = 0; i < candidate.size(); i++) {
        long long c = candidate[i].first;
        if (reta * (retb + 1) > (reta + c) * retb) {
            reta += c, retb++;
            pick[candidate[i].second] = 1;
        }
    }
    
    // topo
    for (int i = 0; i < m; i++)
        if (indeg[i] == 0)	Q.push(i);
    while (!Q.empty()) {
        int u = Q.front(), v;
        Q.pop();
        topo.push_back(u);
        for (int i = 0; i < g.dag[u].size(); i++) {
            v = g.dag[u][i];
            if (--indeg[v] == 0)
                Q.push(v);
        }
    }
    
    // make order with fire rule
    int topo_r[MAXN] = {};
    vector< pair<int, int> > ret;
    for (int i = 0; i < topo.size(); i++) {
        topo_r[topo[i]] = i;
    }
    for (int i = 0; i < m; i++) {
        if (pick[i])
            ret.push_back(make_pair(topo_r[i], scc_id[i]));
    }
    sort(ret.begin(), ret.end());
    
    for (int i = ret.size() - 1; i >= 0; i--)
        printf(" %d", ret[i].second);
    puts("");
//	printf("%lld / %lld\n", reta, retb);
}
int main() {
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d %d %d %d", &X[i], &Y[i], &R[i], &E[i]);
        
        g.init(n);	
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;
                long long dist = (long long)(X[i] - X[j]) * (X[i] - X[j]) + (long long)(Y[i] - Y[j]) * (Y[i] - Y[j]);
                long long r = (long long)(R[i] + E[i] + R[j]) * (R[i] + E[i] + R[j]);
                if (dist <= r) 
                    g.addEdge(i, j);
            }
        }
        
        g.solve();
        g.make_DAG();
        
        printf("Case #%d:", ++cases);
        greedy();
    }
    return 0;
}
/*
1
3
4 7 2 2
8 5 1 0
3 -3 1 1
1
7
24 1 4 7
38 33 4 3
13 13 2 0
34 1 0 0
6 25 5 4
1 14 3 7
30 35 1 6
*/
Read More +
解題區/解題區 - UVa

UVa 1086 - The Ministers' Major Mess

Problem

有 M 個人，B 個方案要進行投票表決。

每個人可以選擇 ki 個方案進行通過或不通過，其中 ki <= 4。找到一種方案的通過方式滿足所有人選擇項目的一半以上 (不含)。

Sample Input

1
2
3
4
5
6
7
5 2 
4 2 y 5 n 3 n 4 n
4 4 y 3 y 5 n 2 y 
4 2 
4 1 y 2 y 3 y 4 y 
3 1 n 2 n 3 n 
0 0

Sample Output

1
2
Case 1: ?y??n 
Case 2: impossible

Solution

由於 ki <= 4，又要滿足一半以上。則對於 ki = 1, 2 需要全部符合他們的項目。對於 ki = 3, 4 則不滿足其中一個選項 i 時，其他的選項 j 都必須滿足。

藉此套用 2-sat 模型，找到是否可能有可行解。當要輸出 2-sat 其中一解時，窮舉每一個變數為 true / false，建立一條邊 x -> x' / x' -> x，再用 2-sat 模型判斷是否有解即可。

找解速度會慢很多，這樣會比較好撰寫。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// 2-satisify problem
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN = 262144;
class TwoSat {
public:
    int n;
    vector<int> g[MAXN];
    // <SCC begin>
    int vfind[MAXN], findIdx;
    int stk[MAXN], stkIdx;
    int in_stk[MAXN], visited[MAXN];
    int contract[MAXN];
    int scc_cnt;
    // <SCC end>
    int scc(int u) {
        in_stk[u] = visited[u] = 1;
        stk[++stkIdx] = u, vfind[u] = ++findIdx;
        int mn = vfind[u], v;
        for(int i = 0; i < g[u].size(); i++) {
        	v = g[u][i];
            if(!visited[v])
                mn = min(mn, scc(v));
            if(in_stk[v])
                mn = min(mn, vfind[v]);
        }
        if(mn == vfind[u]) {
            do {
                in_stk[stk[stkIdx]] = 0;
                contract[stk[stkIdx]] = u;
            } while(stk[stkIdx--] != u);
            scc_cnt++;
        }
        return mn;
    }
    void addEdge(int u, int v) { // u -> v
        g[u].push_back(v);
    }
    int solvable() {
        for (int i = 0; i < n; i++)
            visited[i] = in_stk[i] = 0;
        scc_cnt = 1;
        for (int i = 0; i < n; i++) {
        	if (visited[i])	continue;
        	stkIdx = findIdx = 0;
        	scc(i);
        }
        
        for(int i = 0; i < n; i += 2)
            if(contract[i] == contract[i^1])
                return 0;
        return 1;
    }
    void computeChoice() {
        if (!solvable())
            return ;
        for (int i = 0; i < n; i += 2) {
            int val = 0;
            g[i].push_back(i^1);
            if (solvable())	val |= 1;
            g[i].pop_back();
            
            g[i^1].push_back(i);
            if (solvable())	val |= 2;
            g[i^1].pop_back();
            
            printf("%c", "-yn?"[val]);
        }
        puts("");
    }
    void init(int n) {
        this->n = n;
        for (int i = 0; i < n; i++)
            g[i].clear();
    }
} g;
// more than half of his or her opinions satisfied
// opinion <= 4
int main() {
    int n, m, cases = 0;
    char s[128];
    while (scanf("%d %d", &n, &m) == 2 && n) {
        g.init(2 * n);
        
        for (int i = 0; i < m; i++) {
            int vote[8], k, x;
            scanf("%d", &k);
            for (int j = 0; j < k; j++) {
                scanf("%d %s", &x, s);
                x--;
                vote[j] = x * 2 + (s[0] == 'y');
            }
            if (k <= 2) { // all satisfied
                for (int p = 0; p < k; p++)
                    g.addEdge(vote[p]^1, vote[p]);
            } else { // one fail
                for (int p = 0; p < k; p++) {
                    for (int q = 0; q < k; q++) {
                        if (p == q)	continue;
                        // p-th opinion fail
                        g.addEdge(vote[p]^1, vote[q]);
                    }
                }
            }
        }
        
        printf("Case %d: ", ++cases);
        if (!g.solvable()) {
            puts("impossible");
        } else {
            g.computeChoice();
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11119 - Chemical Attraction

Problem

給予由陰陽離子構成的化合物，混和後會根據活性表發生變化，求其中一種穩定態。

所謂的穩定態，就是不會兩個化合物之間可以進行陰陽離子的互換。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
3
Ba Sr Th
3
Cl Br Fl
1 2 3
1 3 2
2 1 3
2 1 3
1 3 2
1 2 3
3
BaFl SrBr ThCl
5
BaFl BaFl SrFl SrCl ThFl
0
3
Na Ag Fe
5
Su Zi Xe Ar Do
1 2 4 3 5
5 3 1 2 4
2 3 1 4 5
3 2 1
3 2 1
1 3 2
1 2 3
2 1 3
10
NaDo AgDo AgAr FeXe NaXe
AgZi AgZi NaSu AgSu FeDo
0
0

Sample Output

1
2
3
4
5
6
7
8
Scenario 1, Mixture 1:
BaCl SrBr ThFl
Scenario 1, Mixture 2:
BaFl BaCl SrFl SrFl ThFl
Scenario 2, Mixture 1:
NaDo AgSu AgSu FeDo NaXe AgZi AgZi NaXe AgAr FeDo

Solution

一個經典的穩定婚姻問題 (stable marriage problem)，可以用 Gale-Shapley algorithm 解決匹配兩邊個數相同的穩定婚姻。穩定婚姻有兩組最優解，其中一組最優解於男方、另外一組為女方，其最優解即為候選的排序為字典順序最小的。

假設現在要給男方一個最優解，那麼根據貪心的思路，男方要不斷地按照排名清單去向女方求婚，如果女方心中對求婚男方的排名更好，則男方求婚成功，而前男友就會被拋棄，被拋棄的男方將會根據清單再找下去。做法類似增廣路徑。

為什麼這樣能趨近穩定呢？原因是這樣子的，由於男方不斷地求婚，女方配對男方的排名會越來越好，男方被拋棄後，求婚對象則會越來越差。

假定男方為 A, B，女方為 1, 2，優先順序為括弧內，越靠前表示順位越高。

1
2
A(1, 2) - 1(B, A)
B(1, 2) - 2(A, B)

假如 A - 1 和 B - 2，則女 1 更喜歡男 A，女 2 更喜歡男 B，男方中也更喜歡對方的配偶 (這個例子中是相同)，而造成配對交換，這即為不穩定婚姻。

解決會交換的情況。當嘗試配對一對男女時，如何保證不會發生循環交換？當男主被某女拋棄，則表示某女心中有一個更好的某男。男方按照順序求婚，就不會發生男方中會更喜歡對方的配偶而交換。

單看女方，了解到拋棄的動作是有限的，算法就能在 O(N^2) 解決。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// Gale-Shapley algorithm, stable marriage problem
#include <stdio.h>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 256;
class GaleShapley { // produce the best possible choice for the mans
public:
    int mOrder[MAXN][MAXN], fOrder[MAXN][MAXN];
    int fPref[MAXN][MAXN];
    int man[MAXN], woman[MAXN];
    int N;
    void init(int n) {
        N = n;
    }
    void stable() {
        int mIdx[MAXN];
        for (int i = 0; i < N; i++)
            man[i] = woman[i] = -1, mIdx[i] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                fPref[i][fOrder[i][j]] = j;
        }
        for (int i = 0; i < N; i++) {
            int m = i, w;
            while (m >= 0) {
                w = mOrder[m][mIdx[m]++];
                while (m >= 0 && (woman[w] == -1 || fPref[w][woman[w]] > fPref[w][m])) {
                    man[m] = w;
                    swap(m, woman[w]);
                }
            }
        }
    }
} g;
char s[MAXN];
int tA[MAXN][MAXN], tB[MAXN][MAXN], rtA[MAXN][MAXN], rtB[MAXN][MAXN];
int main() {
    int N, M, x, n;
    int cases = 0;
    while (scanf("%d", &N) == 1 && N) {
    	map<string, int> Rn, Rm;
        for (int i = 0; i < N; i++)
        	scanf("%s", s), Rn[s] = i;
        scanf("%d", &M);
        for (int i = 0; i < M; i++)
        	scanf("%s", s), Rm[s] = i;
    	
    	for (int i = 0; i < N; i++)
    		for (int j = 0; j < M; j++)
    			scanf("%d", &tA[i][j]), tA[i][j]--, rtA[i][tA[i][j]] = j;
    	for (int i = 0; i < M; i++)
    		for (int j = 0; j < N; j++)
    			scanf("%d", &tB[i][j]), tB[i][j]--, rtB[i][tB[i][j]] = j;
    	++cases;
    	int tcases = 0;
    	while (scanf("%d", &n) == 1 && n) {
    		vector<string> A, B;
    		for (int i = 0; i < n; i++) {
    			scanf("%s", s);
    			string a(2, 'a'), b(2, 'a');
    			a[0] = s[0], a[1] = s[1];
    			b[0] = s[2], b[1] = s[3];
    			A.push_back(a), B.push_back(b);
    		}
    		g.init(n);
    		
    		for (int i = 0; i < n; i++) {
    			vector< pair<int, int> > p;
    			int u = Rn[A[i]], v;
    			for (int j = 0; j < n; j++) {
    				v = Rm[B[j]];
    				p.push_back(pair<int, int>(tA[u][v], j));
    			}
    			sort(p.begin(), p.end(), greater< pair<int, int> >());
    			for (int j = 0; j < n; j++) {
    				g.mOrder[i][j] = p[j].second;
//    				printf("%d ", p[j].second);
    			}
//    			puts(" -m");
    		}
    		
    		for (int i = 0; i < n; i++) {
    			vector< pair<int, int> > p;
    			int u = Rm[B[i]], v;
    			for (int j = 0; j < n; j++) {
    				v = Rn[A[j]];
    				p.push_back(pair<int, int>(tB[u][v], j));
    			}
    			sort(p.begin(), p.end(), greater< pair<int, int> >());
    			for (int j = 0; j < n; j++) {
    				g.fOrder[i][j] = p[j].second;
//    				printf("%d ", p[j].second);
    			}
//    			puts(" -f");
    		}
    		
    		g.stable();
    		
    		printf("Scenario %d, Mixture %d:\n", cases, ++tcases);
    		for (int i = 0; i < n; i++) {
    			int m = g.man[i];
    			if (i)	printf(" ");
    			printf("%s%s", A[i].c_str(), B[m].c_str());
    		}
    		puts("\n");
    	}
    }
    return 0;
}
/*
 */
Read More +
解題區/解題區 - UVa

UVa 1013 - Island Hopping

Problem

島嶼居民要建造網路連到本島，假設現在島嶼跟島嶼之間都沒有架設網路線，現在開始建造網路，使得每一個島嶼都可以與本島或者是間接相連。

請問平均等待時間需要多少。

所有的路線，在同一時刻開始建造，以每一天一公里的速度建造所有的邊，而每一條邊都以歐幾里得距離為路線長度。

Sample Input

1
2
3
4
5
6
7
8
9
7
11 12 2500
14 17 1500
9 9 750
7 15 600
19 16 500
8 18 400
15 21 250
0

Sample Output

1
Island Group: 1 Average 3.20

Solution

一開始沒有注意到同時建造，發現這條規則後，將所有邊的長度由小到大排序，使用并查集去紀錄，找到第一個時刻連到本島的時間。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h> 
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 64;
double X[MAXN], Y[MAXN], M[MAXN];
struct Edge {
    int x, y;
    double v;
    Edge(int a = 0, int b = 0, double c = 0):
        x(a), y(b), v(c) {}
    bool operator<(const Edge &x) const {
        return v < x.v;
    }
};
vector<Edge> E;
int parent[MAXN], weight[MAXN];
double weight2[MAXN];
int findp(int x) {
    return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)	
        return 0;
    if (weight[x] > weight[y]) {
        parent[y] = x, weight[x] += weight[y];
        weight2[x] += weight2[y];
    } else {
        parent[x] = y, weight[y] += weight[x];
        weight2[y] += weight2[x];
    }
    return 1;
}
double solve(int n) {
    sort(E.begin(), E.end());
    double div = 0, sum = 0;
    int u, v;
    for (int i = 0; i < n; i++)
        parent[i] = i, weight[i] = 1, weight2[i] = M[i], div += M[i];
        
    for (int i = 0; i < E.size(); i++) {
        u = E[i].x, v = E[i].y;
        if (findp(u) != findp(v)) {
            if (findp(u) == findp(0))
                sum += weight2[findp(v)] * E[i].v;
            if (findp(v) == findp(0))
                sum += weight2[findp(u)] * E[i].v;
            joint(u, v);
        }
    }
    return sum / div;
}
int main() {
    int n, cases = 0;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            scanf("%lf %lf %lf", &X[i], &Y[i], &M[i]);
        E.clear();
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                double v = hypot(X[i] - X[j], Y[i] - Y[j]);
                E.push_back(Edge(i, j, v));
            }
        }
        
        double ret = solve(n);
        
        printf("Island Group: %d Average %.2lf\n", ++cases, ret);
        
        puts("");
    }
    return 0;
}
/*
7
11 12 2500
14 17 1500
9 9 750
7 15 600
19 16 500
8 18 400
15 21 250
0
*/
Read More +
解題區/解題區 - UVa

UVa 1186 - Chat Rooms

Problem

聊天室會過濾過機器人般的垃圾留言，規則如下

  • 使用的單詞，出現連續子音的個數大於 5 個
  • 使用者最後送出的 10 個訊息中，有 2 行連續子音的個數大於 4 個，並且當前行也存在連續子音的個數大於 4 個。
  • 使用者最後送出的 10 個訊息中，與當前訊息相同的行數大於 1 個。

只要符合其中一條，訊息將無法發送，但是系統仍然會記錄下你曾經發送過的訊息，其他使用者無法看到被過濾的訊息。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
12
hello
how r u?
where r u from?
kjhh kh kgkjhg jhg
where r u from?
i am from London, Ontario, Canada
how r you nxw?
now
where r u from?
kjhh kh kgkjhg jhg
very good
it is very cold here.

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
y
y
y
n
y
y
y
y
n
n
y
y

Solution

這題算簡單，但是題目描述過於鬼畜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h> 
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <ctype.h>
using namespace std;
vector<string> toToken(string s) {
    stringstream sin(s);
    string token;
    vector<string> r;
    while (sin >> token)
        r.push_back(token);
    return r;
}
int isConsonant(char c) {
    c = tolower(c);
    if (c == 'a')	return 0;
    if (c == 'e')	return 0;
    if (c == 'i')	return 0;
    if (c == 'o')	return 0;
    if (c == 'u')	return 0;
    if (c == 'y')	return 0;
    return 1;
} 
int checkCond1(vector<string> &t) {
    for (int i = 0; i < t.size(); i++) {
        int c = 0;
        for (int j = 0; j < t[i].length(); j++) {
            if (isConsonant(t[i][j]))
                c++;
            else
                c = 0;
            if (c > 5)	return 0;
        }
    }
    return 1;
}
int checkCond2(vector<string> &t, vector<int> &D2) {
    int A = 0, B = 0;
    for (int i = 0; i < t.size(); i++) {
        int c = 0;
        for (int j = 0; j < t[i].length(); j++) {
            if (isConsonant(t[i][j]))
                c++;
            else
                c = 0;
            if (c > 4)	A = 1;
        }
    }
    for (int i = D2.size() - 1; i >= max(0, (int) D2.size() - 10); i--) {
        if (D2[i] > 0)
            B++;
    }
    return !(A && B > 2);
}
int checkCond3(string s, vector<string> &D3) {
    int A = 0;
    for (int i = D3.size() - 1; i >= max(0, (int) D3.size() - 10); i--) {
        if (D3[i] == s)
            A++;
        if (A > 1)
            return 0;
    }
    return 1;
}
int count4(vector<string> &t) {
    int A = 0;
    for (int i = 0; i < t.size(); i++) {
        int c = 0;
        for (int j = 0; j < t[i].length(); j++) {
            if (isConsonant(t[i][j]))
                c++;
            else
                c = 0;
            if (c > 4)	A = 1;
        }
    }
    return A;
}
int main() {
    int n;
    char s[256];
    while (scanf("%d", &n) == 1) {
        while (getchar() != '\n');
        vector< vector<string> > D;
        vector<int> D2;
        vector<string> D3;
        for (int i = 0; i < n; i++) { 
            gets(s);
            vector<string> t = toToken(s);
            int ok = 1;
            if (!checkCond1(t))
                ok = 0;
            else if (!checkCond2(t, D2))
                ok = 0;
            else if (!checkCond3(s, D3)) 
                ok = 0;
            D.push_back(t), D2.push_back(count4(t)), D3.push_back(s);
            puts(ok ? "y" : "n");
        } 
    }
    return 0;
}
Read More +