解題區/解題區 - UVa

UVa 11759 - IBM Fencing

Problem

給定 N 個凸包，保證凸包之間不會有交點，而依據分層，奇數層使用金屬圍欄，偶數層使用木製圍欄，請問分別為需要多少材料。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
8
8 112 134 73 141 41 119 32 82 54 50 92 43 124 65 132 103
6 119 119 102 119 94 101 102 83 119 83 127 101
8 83 106 62 111 45 99 42 78 54 59 75 55 92 66 96 87
6 70 97 56 97 49 85 56 73 70 73 77 85
8 143 222 110 244 61 238 35 209 39 169 72 147 121 153 147 181
4 115 226 58 226 51 167 132 167
4 113 212 65 212 65 172 113 172
5 99 205 83 206 71 187 91 179 105 189
2
4 0 0 100 0 100 100 0 100
4 1000 1000 1100 1000 1100 1100 1000 1100
0

Sample Output

1
2
3
4
5
6
7
8
9
10
11
Case 1:
Total Number of Communities 2
Total Cost:
Steel Fence: 0.09047417 Million Yuan
Wooden Fence: 0.03190241 Million Yuan
  
Case 2:
Total Number of Communities 2
Total Cost:
Steel Fence: 0.08000000 Million Yuan
Wooden Fence: 0.00000000 Million Yuan

Solution

這裡需要對 N 個凸包做相互關係判斷，建造出 tree 圖，根據樹圖計算分層。

兩個凸包判定可以在 O(log n) 時間內完成，因此建造會在 O(n^2 log n)。

找到多邊形分層圖之間的關係，只會有完全包裹和完全沒交集兩種情況。利用掃描線可以找到兩個相鄰多邊形，要不與其同一層，要不就是上一層。因此可以在 n log n 時間內找到，考慮邊的個數問題，複雜度上提 O(nm log nm) 不如暴力窮舉兩個多邊形做判定 O(n^2 m)，在都是凸多邊形的情況 O(n^2 log m)。掃描線掃了一連串結果，還要處理同一多邊形端點相同的線段，利用隨機擾動處理垂直線 … 等，自找苦吃，暴力完勝。

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
#include <stdio.h>
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    int  label;
    Pt(double a = 0, double b = 0, int c = 0):
    	x(a), y(b), label(c) {}
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)	return x < a.x;
        if (fabs(y - a.y) > eps)	return y < a.y;
        return false;
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
       cross(at, as, bs) * cross(at, as, bt) < 0 &&
       cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
       cross(bt, bs, as) * cross(bt, bs, at) < 0)
        return 1;
    return 0;
}
// this problem
vector<int> g[512];
struct Polygon { // convex
    vector<Pt> p;
    int contain(Polygon &a) {
        int n = p.size();
        if(n < 3)	return false;
        Pt q = a.p[0];
        if(cross(p[0], q, p[1]) > eps)		return 0;
        if(cross(p[0], q, p[n-1]) < -eps)	return 0;
        int l = 2, r = n - 1;
        int line = -1;
        while(l <= r) {
            int mid = (l + r)>>1;
            if(cross(p[0], q, p[mid]) > -eps) {
                line = mid;
                r = mid - 1;
            } else l = mid + 1;
        }
        return cross(p[line-1], q, p[line]) < eps;
    }
};
Polygon poly[512];
int parent[32767], visited[32767], depth[32767];
void bfs(int u) {
    int v;
    queue<int> Q;
    Q.push(u);
    visited[u] = 1, depth[u] = 1;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if (depth[v] < depth[u] + 1) {
                depth[v] = depth[u] + 1;
                visited[v] = 1, parent[v] = u;
                Q.push(v);
            }
        }
    }
}
int main() {
    int N, M, cases = 0;
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 0; i < N; i++) {
            scanf("%d", &M);
            poly[i].p.resize(M);
            for (int j = 0; j < M; j++)
                scanf("%lf %lf", &poly[i].p[j].x, &poly[i].p[j].y);
            double mnx = poly[i].p[0].x;
            int idx = 0;
            for (int j = 0; j < M; j++) {
                if (poly[i].p[j].x < mnx)
                    mnx = poly[i].p[j].x, idx = j;
            }
            if (cross(poly[i].p[idx], poly[i].p[(idx+1)%M], poly[i].p[(idx-1+M)%M]) < eps)
                reverse(poly[i].p.begin(), poly[i].p.end());
        }
        
        for (int i = 0; i < N; i++)
            g[i].clear();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j)	continue;
                if (poly[i].contain(poly[j]))
                    g[i].push_back(j);
            }
        }
        
        for (int i = 0; i < N; i++) {
            visited[i] = 0, parent[i] = -1, depth[i] = 0;
        }
        for (int i = 0; i < N; i++) {
            if (visited[i] == 0)
                bfs(i);
        }		
        int communities = 0;
        double Acost = 0, Bcost = 0;
        for (int i = 0; i < N; i++) {
            if (parent[i] == -1)
                communities++;
            double tmp = 0;
            for (int j = 0, k = poly[i].p.size() - 1; j < poly[i].p.size(); k = j++)
                tmp += dist(poly[i].p[j], poly[i].p[k]);
            if (depth[i]&1)
                Acost += tmp;
            else
                Bcost += tmp/2;
        }
        
        printf("Case %d:\n", ++cases);
        printf("Total Number of Communities %d\n", communities);
        printf("Total Cost:\n");
        printf("Steel Fence: %.8lf Million Yuan\n", Acost / 10000.0);
        printf("Wooden Fence: %.8lf Million Yuan\n", Bcost / 10000.0);
        puts("");
    }
    return 0;
}
/*
8
8 112 134 73 141 41 119 32 82 54 50 92 43 124 65 132 103
6 119 119 102 119 94 101 102 83 119 83 127 101
8 83 106 62 111 45 99 42 78 54 59 75 55 92 66 96 87
6 70 97 56 97 49 85 56 73 70 73 77 85
8 143 222 110 244 61 238 35 209 39 169 72 147 121 153 147 181
4 115 226 58 226 51 167 132 167
4 113 212 65 212 65 172 113 172
5 99 205 83 206 71 187 91 179 105 189
2
4 0 0 100 0 100 100 0 100
4 1000 1000 1100 1000 1100 1100 1000 1100
0
*/
Read More +
解題區/解題區 - UVa

UVa 1006 - Fixed Partition Memory Management

Problem

每個程式會有在不同的空間限制下會有不同的運行時間，現在給定 N 個內存池，M 個程式，每個程式只能在一個內存池下運行，並且同一個時間內存池內最多有一個程式。

最平均運行時間最少為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2 4
40 60
1 35 4
1 20 3
1 40 10
1 60 7
3 5
10 20 30
2 10 50 12 30
2 10 100 20 25
1 25 19
1 19 41
2 10 18 30 42
0 0

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Case 1
Average turnaround time = 7.75
Program 1 runs in region 1 from 0 to 4
Program 2 runs in region 2 from 0 to 3
Program 3 runs in region 1 from 4 to 14
Program 4 runs in region 2 from 3 to 10
Case 2
Average turnaround time = 35.40
Program 1 runs in region 2 from 25 to 55
Program 2 runs in region 2 from 0 to 25
Program 3 runs in region 3 from 0 to 19
Program 4 runs in region 3 from 19 to 60
Program 5 runs in region 1 from 0 to 18

Solution

平均最少時間的計算，就是拿每個程式的運行結束時間加總取平均。

但是必須累計到前一個在內存池運行的程式時間，這一點必須轉換成最少費用流模型。

事實上，換個角度想，假使排定程式 A 運行，而後會有 B, C 程式，那麼 A 的運行時間會累計到三次，而 B 會被累計到兩次。也就是說，內存池每一個程式的時間加總會分配到 1 ~ N 個程式重複計數。

因此模型為 source - program - [memory_pool, count] - sink。

輸出的時候，在內存池被累計越多次的程式應該越早執行。

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;
struct Node {
    int x, y, cap, cost;// x->y, v
    int next;
} edge[1000005];
int e, head[600], dis[600], prev[600], record[600], inq[600];
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++;
}
int mincost(int s, int t) {
    int mncost = 0, flow, totflow = 0;
    int i, x, y;
    while(1) {
        memset(dis, 63, sizeof(dis));
        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;
                    prev[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 = oo;
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for(x = t; x != s; x = prev[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 mncost;
}
int main() {
    int n, m, cases = 0;
    int x, y, d, a;
    int mem[128], needmem[128][128], runtime[128][128], ch[128];
    
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
    	for (int i = 0; i < n; i++)
    		scanf("%d", &mem[i]);
    	for (int i = 0; i < m; i++) {
    		scanf("%d", &ch[i]);
    		for (int j = 0; j < ch[i]; j++)
    			scanf("%d %d", &needmem[i][j], &runtime[i][j]);
    		needmem[i][ch[i]] = 0x3f3f3f3f;
    	}
    	
        e = 0;
        memset(head, -1, sizeof(head));
        int source = n*m + m + 1, sink = n*m + m + 2;
        for (int i = 0; i < m; i++) {
        	addEdge(source, i, 1, 0);
        	for (int j = 0; j < ch[i]; j++) {
        		for (int k = 0; k < n; k++) {
        			if (needmem[i][j] <= mem[k] && mem[k] <= needmem[i][j+1]) {
        				for (int p = 0; p < m; p++)
        					addEdge(i, m + k * m + p, 1, runtime[i][j] * (p + 1));
        			}
        		}
        	}
        }
        for (int i = 0; i < n; i++)
        	for (int j = 0; j < m; j++)
        		addEdge(m + i * m + j, sink, 1, 0);
        
        double cost = mincost(source, sink);
        int prog[128], from[128] = {}, run[128];
        vector< pair<int, int> > runtable[128];
        for (int i = 0; i < m; i++) {
        	for (int j = head[i]; j != -1; j = edge[j].next) {
        		if (edge[j].cap == 0 && edge[j].y >= m && edge[j].y < m + n*m) {
        			prog[i] = (edge[j].y - m) / m;
        			run[i] = edge[j].cost / ((edge[j].y - m) % m + 1);
        			runtable[prog[i]].push_back(make_pair((edge[j].y - m) % m, i));
        			break;
        		}
        	}
        }
        for (int i = 0; i < n; i++) {
        	sort(runtable[i].begin(), runtable[i].end(), greater< pair<int, int> >());
        	for (int j = 1; j < runtable[i].size(); j++)
        		from[runtable[i][j].second] = from[runtable[i][j-1].second] + run[runtable[i][j-1].second];
        }
        printf("Case %d\n", ++cases);
        printf("Average turnaround time = %.2lf\n", (double) cost / m);
        for (int i = 0; i < m; i++) {
        	printf("Program %d runs in region %d from %d to %d\n", i+1, prog[i]+1, from[i], from[i] + run[i]);
        }
        puts("");
    }
    return 0;
}
/*
2 4
40 60
1 35 4
1 20 3
1 40 10
1 60 7
3 5
10 20 30
2 10 50 12 30
2 10 100 20 25
1 25 19
1 19 41
2 10 18 30 42
0 0
*/
Read More +
解題區/解題區 - UVa

UVa 1001 - Say Cheese

Problem

在一個三維空間中的乳酪，知道乳酪常會有氣泡般的空洞，假設在空洞中任意位置之間移動不消耗時間，為了抵達目的地，可以啃食乳酪到另外一個空洞，啃食時間與距離 1 : 1 關係，請問最少時間為何。

Sample Input

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

Sample Output

1
2
Cheese 1: Travel time = 100 sec
Cheese 2: Travel time = 20 sec

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
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int main() {
    int n, x[128], y[128], z[128], r[128];
    int cases = 0;
    while (scanf("%d", &n) == 1 && n >= 0) {
        for (int i = 0; i < n + 2; i++) {
            if (i < n)
                scanf("%d %d %d %d", &x[i], &y[i], &z[i], &r[i]);
            else
                scanf("%d %d %d", &x[i], &y[i], &z[i]), r[i] = 0;			
        }
        n += 2;
        double f[128][128];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)	f[i][i] = 0;
                else {
                    double dist = sqrt(pow(x[i]-x[j], 2) + pow(y[i]-y[j], 2) + pow(z[i] - z[j], 2));
                    if (dist <= r[i] + r[j])
                        f[i][j] = 0;
                    else
                        f[i][j] = dist - (r[i] + r[j]);
                }
            }
        }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
        printf("Cheese %d: Travel time = %.0lf sec\n", ++cases, f[n-1][n-2] * 10);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1000 - Airport Configuration

Problem

機場有一個長形走廊，其中南側是搭機處，北側是下機處。

給予很多城市間旅客的數量，從城市 A 到城市 B 的旅客 X 人會在這個機場上進行轉換。

現在讀入機場的放置口設定 (順序)，請問每一種設定所產生的負載為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
3
1  2  2 10  3 15
2  1  3 10
3  2  1 12  2 20
1
1 2 3
2 3 1
2
2 3 1
3 2 1
0
2
1  1  2 100
2  1  1 200
1
1 2
1 2
2
1 2
2 1
0
0

Sample Output

1
2
3
4
5
6
Configuration Load
    2         119
    1         122
Configuration Load
    2         300
    1         600

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
#include <stdio.h> 
#include <algorithm>
#include <vector>
#include <stdlib.h>
using namespace std;
int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        int A[32][32] = {}, x, city_id, dest, k;
        int north[32], south[32];
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &city_id, &k);
            for (int j = 0; j < k; j++) {
                scanf("%d %d", &dest, &x);
                A[city_id][dest] += x;
            }
        }
        vector< pair<int, int> > ret;
        for (; scanf("%d", &city_id) == 1 && city_id;) {
            for (int i = 0; i < n; i++)
                scanf("%d", &north[i]);
            for (int i = 0; i < n; i++)
                scanf("%d", &south[i]);
            int load = 0;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    load += A[north[i]][south[j]] * (abs(i - j) + 1);
            ret.push_back(make_pair(load, city_id));
        }
        sort(ret.begin(), ret.end());
        puts("Configuration Load");
        for (int i = 0; i < ret.size(); i++) {
            printf("%5d         %d\n", ret[i].second, ret[i].first);
        }
    }
    return 0;
}
Read More +
解題區/出題解題

[ACM 題目] 順來逆受

Problem

「其實雙親不准我在家裡畫漫畫。」
「是嗎？你都畫些什麼啊」
「乃是在下 x 大哥的原創本是也。」
「還有，薰是普通人」
「薰姐，功的反義詞是什麼？」
「什麼？是守嗎？」
「薰姐，剛才我說的話請你全忘記吧。」

在一個 N 個城市的國家，每個城市之間用 M 條邊相連。隨著時間，它們開始分裂，彼此會開始斷訊，無法聯絡到相鄰的城市。定時回報某個城市可以藉由間接或直接連絡的城市個數。

操作：

  • D i：移除輸入順序 i 個連接邊。
  • Q i：輸出城市 i 能聯絡的城市個數。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5 5
1 2
1 3
2 3
3 4
4 5
4
Q 1
D 4
Q 5
Q 2

Sample Output

1
2
3
5
2
3

Solution

1
Read More +
學校課程/通識課程

[通識] 文明的進程 Week 6

公私領域的分裂，在不同的場合下，擁有的心理、情緒反應會有所不同。在某些場合 渴望愉悅 是必要的行為，抑制住反而有失禮儀。相反地， 否認愉悅 也是有場合是必須的。例如在家裡與在社交場所，在家裡可以因為有家人關係，表現得自然不過，如果什麼都抑制住，反而稱不上家人相處。而在社交場所，即使討厭一個人，也不能在臉上表現出來。

比中指 辱罵別人其實是很文明的舉止，因為並沒有實施暴力行為，是一種克制自我的行為。然而，比中指仍然稱不上是好的禮儀，但已經進步很多。

裸體代表的就是 自然 、 本相 ，查看其背後的涵義，這在很多理論上作為依據－抗議的主旨。 求自然 、 求真相 。

關於小組報告的大綱如下：

  • 為什麼主題有關文明化？
  • 看時間軸中，行為是怎麼形成的？
  • 約束人們做了哪些事情，思考了那些事情。
  • 約束－身分－環境，三者彼此之間的相互關係。
  • 在不同的時空背景下，又有什麼差別？是甚麼原因造成的？

特別注意報告要點：

  • 請說大家沒想過的，觀眾都等著你給的 surprise

本周報告

無處不在的文明教育（家庭、學校、公共空間與媒體）

家庭

談什麼？不談什麼？

首先是性教育、生與死，小時候不談這些，但隨著長大成人就會依依序序跟家裡長輩們談談，關於性、生後事 … 等一些比較嚴肅的話題。

看不看 A 片？寫不寫遺書？A 片的命名如何文明化？

PTT A片取什麼名字最安全？
大陸尋奇、舌尖上的日本、微積分、幫爸爸抓的、流體力學、日文初級音聽檢定 … 等

最後老師特別贊助：取名為 文明的進程 。

學校

環保意識的培養？

其實我認為學校文明教育從蔣公那時開始到現在就很有不同，學三民主義的課程到現在九年一貫課程，中間經歷了相當多的轉變。老一輩的人三民主義的日子，學著書上的精神，造就他們的價值觀。而我們學習到的只有宏觀歷史，而少了點歷史仇視，沒有嚮往開國元老，敬重政治人物的努力。

小學從品德教育開始，在國中之後便不怎麼有時間上這些，原本有 課 上，變成用條例規範，逐漸地，我們可以開始閱讀 規則 並且知道要遵守。

公共空間與媒體

媒體很有趣，從小看到大，可以說是一個群體訓練場，看著畫面猜著下面給的標題是否符合，已經快要變成一場遊戲，只要八九不離十，就有十足把握出門跟別人談談這些。在一個單向的管道中，從媒體為何而來？人們疏離開始說起，又或者不想跟別人談這個主題，需要一個媒介替你轉達！

Read More +
解題區/解題區 - UVa

UVa 12833 - Daily Potato

Problem

找到迴文是起頭和結尾都是字符 c，並且 c 在中間出現 X 次

參考範例輸入，六個詢問 (a, 2) (b, 2) (c, 2) … 他把字符弄再一起，例如第一個 (a, 2) 來說，起頭為 a 且中間要出現恰好 2 次 a，主字串中只看到 abccba 和 aa。

Sample Input

1
2
3
4
5
6
1
8
abccbaab
6
abcabc
2 2 2 1 1 3

Sample Output

1
2
3
4
5
6
7
Case 1:
2
2
1
3
3
0

Solution

因為要恰好 X 個，對於每組詢問基本上只會有 n 個位置，當作起頭，然後 O(1) 檢查迴文即可。就算分 26 組下去，還是 TLE。

O(1) 檢查的方式按照 manacher’s algorithm 的做法，

manacher’s algorithm 算法核心，在 O(n) 時間內找到最長迴文子字串。


圖片與算法來源 here

可以將每組詢問壓到 O(log n) 以下，我們知道從每一個中心展開的最長迴文，也代表可以記錄展開的時候，恰好以某個字符開頭的最大總數。

對於每一組詢問，保證每一個中心最多當過一次迴文中心，因此只要總數大於等於指定個數，保證可以湊出來。

其 A[i][c] 表示以位置 i 為中心，起頭是字符 c，出現最多的 c 個數。之後問 c x 輸出有多少 A[i][c] >= x。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXL 262144
char S[MAXL], C[MAXL], T[MAXL];
int dp[MAXL], n, m;
int A[MAXL][26], SUM[MAXL][26];
void exbuild(char S[]) { // manacher's algorithm
    n = strlen(S), m = 2 * n + 1;
    int mx = 0, idx = 0;
    int ans = 0;
    T[0] = '$', T[m] = '#', T[m + 1] = '\0';
    for (int i = 0; i < n; i++)
    	T[i * 2 + 1] = '#', T[i * 2 + 2] = S[i];
    //
    memset(SUM[0], 0, sizeof(SUM[0]));
    for (int i = 1; i < m; i++) {
    	memcpy(SUM[i], SUM[i-1], sizeof(SUM[0]));
    	if ('a' <= T[i] && T[i] <= 'z')
    		SUM[i][T[i] - 'a']++;
    }
    //
    for (int i = 1; i < m; i++) {
        if (mx > i) {
        	memcpy(A[i], A[2 * idx - i], sizeof(A[2 * idx - i]));
            dp[i] = min(dp[2 * idx - i], mx - i);
            if (dp[2 * idx - i] >= mx - i) {
            	int r = idx - (mx - idx), l = 2 * idx - i - dp[2 * idx - i];
            	for (int j = 0; j < 26; j++) {
            		A[i][j] -= (SUM[r][j] - SUM[l][j]) * 2;
            	}
        	}
        } else {
        	for (int j = 0; j < 26; j++)
        		A[i][j] = SUM[i][j] - SUM[i-1][j];
            dp[i] = 1;
        }
        for(; T[i-dp[i]] == T[i+dp[i]]; dp[i]++)
        	if ('a' <= T[i+dp[i]] && T[i+dp[i]] <= 'z')
                A[i][T[i-dp[i]] - 'a'] += 2;
        if(dp[i] + i > mx)		mx = dp[i] + i, idx = i;
    }
//    for (int i = 1, j = 0; i < m; i ++, j++)
//    	printf("[%02d] %c %d\n", i, T[i], dp[i]);
}
vector<int> M[2][26];
void prepare() {
    for (int i = 0; i < 26; i++)
        M[0][i].clear(), M[1][i].clear();
    for (int i = 1; i < m; i++) {
//		printf("%c ", T[i]);
        for (int j = 0; j < 26; j++) {
            M[A[i][j]&1][j].push_back(A[i][j]);
//			printf("%d ", A[i][j]);
        }
//		puts("");
    }
    for (int i = 0; i < 26; i++) {
        sort(M[0][i].begin(), M[0][i].end());
        sort(M[1][i].begin(), M[1][i].end());
    }
}
void query(int x, char c) {
    if (x == 0)	{puts("0"); return;}
    int p = (int) (lower_bound(M[x&1][c - 'a'].begin(), M[x&1][c - 'a'].end(), x) - M[x&1][c - 'a'].begin());
    printf("%d\n", int(M[x&1][c - 'a'].size() - p));
}
int main() {
    freopen("in.txt", "r+t", stdin);
    freopen("out2.txt", "w+t", stdout); 
    int testcase, N, Q, cases = 0;
    int x;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %s", &N, S);
        scanf("%d %s", &Q, C);
        exbuild(S);
        prepare();
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < Q; i++) {
            scanf("%d", &x);
            query(x, C[i]);
        }
    }
    return 0;
}
/*
1
8
abccbaab
6
abcabc
2 2 2 1 1 3
1000
6
abaaba
7
aaaaaab
5 4 3 2 1 0 2
123
10
ccecabebcb
10
ebddcdacad
5 6 2 5 5 5 5 1 9 9
10
abbbbeaaba
10
cbabcabcec
2 0 1 8 5 6 2 4 8 1
10
baddaeaecb
10
bbdebdbedd
1 5 5 6 2 9 9 1 5 0
*/
Read More +
解題區/解題區 - UVa

UVa 12830 - A Football Stadium

Problem

在一個 L x W 的區域中，有 N 個點障礙物，要在其中找到一個最大空白矩形，中間不包含任何障礙物。

Sample Input

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

Sample Output

1
2
3
Case 1: 18
Case 2: 81
Case 3: 25

Solution

x, y 軸兩個都要做嘗試基底的動作。考慮一下都是 x = ? 當做基底時, 如果 y 值與窮舉點一樣, 那麼可選上或選下, 但無法決定哪個好，但是可以被決定於 y = ? 當做基底時的窮舉。整體效率是 O(n*n)

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
#include <stdio.h>
#include <algorithm>
using namespace std;
// same 10043 - Chainsaw Massacre.
struct Pt {
    int x, y;
    Pt(int a = 0, int b = 0):
        x(a), y(b){}
    bool operator<(const Pt &p) const {
        if(p.x != x)
            return x < p.x;
        return y < p.y;
    }
};
bool cmp(Pt a, Pt b) {
    if(a.y != b.y)
        return a.y < b.y;
    return a.x < b.x;
}
Pt tree[3000];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        int h, w;
        int x, y;
        scanf("%d %d", &h, &w);
        int op, i, j;
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        	scanf("%d %d", &tree[i].x, &tree[i].y);
        tree[n++] = Pt(0, 0);
        tree[n++] = Pt(h, w);
        tree[n++] = Pt(h, 0);
        tree[n++] = Pt(0, w);
        sort(tree, tree+n);
        int area = 0;
        for(i = 0; i < n; i++) {
            int mny = 0, mxy = w;
            for(j = i+1; j < n; j++) {
                area = max(area, (tree[j].x-tree[i].x)*(mxy-mny));
                if(tree[j].x == tree[i].x)
                    continue;
                if(tree[j].y > tree[i].y)
                    mxy = min(mxy, tree[j].y);
                else
                    mny = max(mny, tree[j].y);
            }
        }
        sort(tree, tree+n, cmp);
        for(i = 0; i < n; i++) {
            int mnx = 0, mxx = h;
            for(j = i+1; j < n; j++) {
                area = max(area, (tree[j].y-tree[i].y)*(mxx-mnx));
                if(tree[j].y == tree[i].y)
                    continue;
                if(tree[j].x > tree[i].x)
                    mxx = min(mxx, tree[j].x);
                else
                    mnx = max(mnx, tree[j].x);
            }
        }
        printf("Case %d: %d\n", ++cases, area);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1479 - Graph and Queries

Problem

給 N 個點、M 條邊的無向圖，現在有三種操作：

  • D X ：刪除輸入編號 X 的邊
  • Q X K ：詢問與 X 相同連通元件中，節點權重第 K 大。
  • C X V ：將節點 X 權重修改成 V。

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
3 3 
10 
20 
30 
1 2 
2 3 
1 3 
D 3 
Q 1 2 
Q 2 1 
D 2 
Q 3 2 
C 1 50
Q 1 1
E
3 3 
10 
20 
20 
1 2 
2 3 
1 3 
Q 1 1 
Q 1 2 
Q 1 3 
E 
0 0

Sample Output

1
2
Case 1: 25.000000 
Case 2: 16.666667

Solution

可以看出，如果順著做會比較繁瑣，分裂總是比合併來的痛苦，根據并查集的概念，將其變成合併操作。

我們逆著輸入順序處理，根據離線的方式，可以預測最後會分裂到甚麼情況、最後某個節點帶什麼權重，分別將其建造一個平衡樹。刪除一條邊相當於加入一條邊，并查集看出好比兩個平衡樹合併，修改一個節點權重相當於回朔前一個版本的值。

而要在平衡樹中查找第 k 大元素不能用 STL，這裡用比較簡單的 treap，編程複雜度比較低。

treap 的效率取決於每個節點攜帶的隨機權重，事先用內存池撒過一次亂數，之後需要再從內存池提取，之後就不撒亂數，蛋疼的是竟然活生生掛掉了。還是乖乖 srand(514); 偷懶不想用 new 加快效率什麼的，實在囧

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
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXN 65536
#define MAXM 65536
#define MAXQ (1<<20)
struct node;
node *null;
struct node {
    node *lson, *rson;
    int key, value, size;
    
    node(int x = 0, int s = 1):key(x), size(s) {
        lson = rson = null;
    }
    void update() {
        if (this != null)
            size = lson->size + rson->size + 1;
    }
} nodes[MAXQ], *root[MAXN];
struct treap {
    int bufIdx;
    node *getNode(int val) {
        node *ret = &nodes[bufIdx++];
        *ret = node(val);
        ret->value = rand();
        return ret;
    }
    void rotate(node* &a, int dir) { // dir {0: left, 1: right}
        node *p;
        if (dir == 0) {
            p = a->rson;
            a->rson = p->lson;
            p->lson = a;
        } else {
            p = a->lson;
            a->lson = p->rson;
            p->rson = a;
        }
        a->update(), p->update();
        a = p;
    }
    void insert(node* &a, int val) {
        if (a == null)
            a = getNode(val);
        else {
            if (val < a->key) {
                insert(a->lson, val);
                if (a->lson->value > a->value)
                    rotate(a, 1);
            } else {
                insert(a->rson, val);
                if (a->rson->value > a->value)
                    rotate(a, 0);
            }
        }
        a->update();
    }
    void remove(node* &a, int val) {
        if (a->key == val) {
            if (a->lson == null)
                a = a->rson;
            else if (a->rson == null)
                a = a->lson;
            else {
                if (a->lson->value > a->rson->value)
                    rotate(a, 1), remove(a->rson, val);
                else
                    rotate(a, 0), remove(a->lson, val);
            }
        } else if (val < a->key) {
            remove(a->lson, val);
        } else {
            remove(a->rson, val);
        }
        a->update();
    }
    void merge(node* &from, node* &to) {
        if (from->lson != null)
            merge(from->lson, to);
        if (from->rson != null)
            merge(from->rson, to);
        insert(to, from->key); // delete node `from`, need use delete replace pool.
    }
    node* kth_element(node* &a, int k) {
        if (a == null || k <= 0 || k > a->size)	return null;
        if (k == a->lson->size + 1)
            return a;
        if (k <= a->lson->size)
            return kth_element(a->lson, k);
        else
            return kth_element(a->rson, k - a->lson->size - 1);
    }
    node* rkth_element(node* &a, int k) {
        if (a == null || k <= 0 || k > a->size)	return null;
        if (k == a->rson->size + 1)
            return a;
        if (k <= a->rson->size)
            return rkth_element(a->rson, k);
        else
            return rkth_element(a->lson, k - a->rson->size - 1);
    }
    int lower_dist(node* &a, int val) {
        if (a == null)	return 1;
        if (a->value < val)
            return a->lson->size + 1 + lower_dist(a->rson, val);
        else
            return lower_dist(a->lson, val);
    }
    int upper_dist(node* &a, int val) {
        if (a == null)	return 1;
        if (a->value > val)
            return a->rson->size + 1 + upper_dist(a->lson, val);
        else
            return upper_dist(a->rson, val);
    }
    void print(node *ver) {
        if (ver == null)	return;
        print(ver->lson);
        printf("print %d %d\n", ver->key, ver->size);
        print(ver->rson);
    }
    void init() {
        bufIdx = 0;
        null = &nodes[bufIdx++];
        null->size = 0, null->lson = null->rson = null, null->value = 0;
    }
} tree;
char cmd[MAXQ][4];
int QX[MAXQ], QY[MAXQ], edgeX[MAXM], edgeY[MAXM], w[MAXN];
int parent[MAXN], weight[MAXN];
int findp(int x) {
    return parent[x] == x ? x : (parent[x] = findp(parent[x]));
}
void joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)	return;
    if (weight[x] > weight[y]) {
        parent[y] = x, weight[x] += weight[y];
        tree.merge(root[y], root[x]);
        
    } else {
        parent[x] = y, weight[y] += weight[x];
        tree.merge(root[x], root[y]);
    }
}
void initDisjointSet(int n)  {
    for (int i = 1; i <= n; i++)
        parent[i] = i, weight[i] = 1;
}
void changeVertex(int u, int val) {
    int r = findp(u);
    tree.remove(root[r], w[u]);
    tree.insert(root[r], val);
    w[u] = val;
}
int main() {
    //    freopen("in.txt", "r+t", stdin);
    //    freopen("out.txt", "w+t", stdout);
    int n, m, q, t;
    int cases = 0;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        tree.init();
        for (int i = 1; i <= n; i++)
            scanf("%d", &w[i]);
        for (int i = 1; i <= m; i++)
            scanf("%d %d", &edgeX[i], &edgeY[i]);
        int exists[MAXM] = {};
        for (int i = 1; i <= m; i++)
            exists[i] = 1;
        for (q = 0; scanf("%s", cmd[q]) == 1 && cmd[q][0] != 'E'; q++) {
            if (cmd[q][0] == 'D')
                scanf("%d", &QX[q]), exists[QX[q]] = 0;
            else if (cmd[q][0] == 'C')
                scanf("%d %d", &QX[q], &QY[q]), t = QY[q], QY[q] = w[QX[q]], w[QX[q]] = t;
            else if (cmd[q][0] == 'Q')
                scanf("%d %d", &QX[q], &QY[q]);
        }
        
        for (int i = 1; i <= n; i++)
            root[i] = null;
        for (int i = 1; i <= n; i++)
            tree.insert(root[i], w[i]);
        initDisjointSet(n);
        for (int i = 1; i <= m; i++)
            if (exists[i] == 1)
                joint(edgeX[i], edgeY[i]);
        
        double ret = 0, cnt = 0;
        for (int i = q - 1; i >= 0; i--) {
            if (cmd[i][0] == 'D')
                joint(edgeX[QX[i]], edgeY[QX[i]]);
            else if (cmd[i][0] == 'C')
                changeVertex(QX[i], QY[i]);
            else if (cmd[i][0] == 'Q') {
                cnt++;
                node* v = tree.rkth_element(root[findp(QX[i])], QY[i]);
                if (v == null)	/*puts("undefined")*/;
                else 			ret += v->key/*, printf("kth %d\n", v->key)*/;
            }
        }
        ret /= cnt;
        printf("Case %d: %lf\n", ++cases, ret);
    }
    return 0;
}
/*
 3 3
 10
 20
 30
 1 2
 2 3
 1 3
 D 3
 Q 1 2
 Q 2 1
 D 2
 Q 3 2
 C 1 50
 Q 1 1
 E
 */
Read More +
解題區/解題區 - UVa

UVa 12825 - Happy Robot

Problem

機器人一開始在原點 (0, 0)，並且面向東方 (East)。會按照以下三種指令做事。

  • L: turn left 方向往左轉，ex. 往北變成往西
  • R: turn right 方向往右轉，ex. 往北變成往東
  • F: go forward one step，依照當前方向往前走一步

指令中會有 ? 表示可以插入三種其中一種操作，請問機器人分別能走到的 x, y 最大最小值為何。

Sample Input

1
2
3
F?F
L??
LFFFRF

Sample Output

1
2
3
Case 1: 1 3 -1 1
Case 2: -1 1 0 2
Case 3: 1 1 3 3

Solution

動態規劃，把 x, y 分開考慮，同時維護 4 個方向的最大最小值。

定義 dp[i][dir][min/max] : 執行前 i 個指令，在 dir 方向上的最大最小值。

遞迴公式請參照代碼。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int main() {
    char s[1024];
    int cases = 0;
    while (scanf("%s", s) == 1) {
        int dpx[1024][4][2], dpy[1024][4][2];
        // [N E S W][min/max]
        const int dx[4] = {0, 1, 0, -1};
        const int dy[4] = {1, 0, -1, 0};
        int n = strlen(s);
        for (int i = 0; i <= n; i++)
            for (int j = 0; j < 4; j++) {
                dpx[i][j][0] = INF, dpx[i][j][1] = -INF;
                dpy[i][j][0] = INF, dpy[i][j][1] = -INF;
            }
        dpx[0][1][0] = 0, dpx[0][1][1] = 0;
        dpy[0][1][0] = 0, dpy[0][1][1] = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'F' || s[i] == '?') {
                for (int j = 0; j < 4; j++) {
                    dpx[i+1][j][0] = min(dpx[i+1][j][0], dpx[i][j][0] + dx[j]);
                    dpx[i+1][j][1] = max(dpx[i+1][j][1], dpx[i][j][1] + dx[j]);
                    dpy[i+1][j][0] = min(dpy[i+1][j][0], dpy[i][j][0] + dy[j]);
                    dpy[i+1][j][1] = max(dpy[i+1][j][1], dpy[i][j][1] + dy[j]);
                }
            } 
            if (s[i] == 'R' || s[i] == '?') {
                for (int j = 0; j < 4; j++) {
                    dpx[i+1][(j+1)%4][0] = min(dpx[i+1][(j+1)%4][0], dpx[i][j][0]);
                    dpx[i+1][(j+1)%4][1] = max(dpx[i+1][(j+1)%4][1], dpx[i][j][1]);
                    dpy[i+1][(j+1)%4][0] = min(dpy[i+1][(j+1)%4][0], dpy[i][j][0]);
                    dpy[i+1][(j+1)%4][1] = max(dpy[i+1][(j+1)%4][1], dpy[i][j][1]);
                }
            }
            if (s[i] == 'L' || s[i] == '?') {
                for (int j = 0; j < 4; j++) {
                    dpx[i+1][(j+3)%4][0] = min(dpx[i+1][(j+3)%4][0], dpx[i][j][0]);
                    dpx[i+1][(j+3)%4][1] = max(dpx[i+1][(j+3)%4][1], dpx[i][j][1]);
                    dpy[i+1][(j+3)%4][0] = min(dpy[i+1][(j+3)%4][0], dpy[i][j][0]);
                    dpy[i+1][(j+3)%4][1] = max(dpy[i+1][(j+3)%4][1], dpy[i][j][1]);
                }
            }
//			for (int j = 0; j < 4; j++) {
//				printf("%d %d %d %d\n", dpx[i][j][0], dpx[i][j][1], dpy[i][j][0], dpy[i][j][1]);
//			}
//			puts("--");
        }
        int mnx = INF, mxx = -INF, mny = INF, mxy = -INF;
        for (int i = 0; i < 4; i++) {
            mnx = min(mnx, dpx[n][i][0]);
            mxx = max(mxx, dpx[n][i][1]);
            mny = min(mny, dpy[n][i][0]);
            mxy = max(mxy, dpy[n][i][1]);
        }
        printf("Case %d: %d %d %d %d\n", ++cases, mnx, mxx, mny, mxy);
    }
    return 0;
}
Read More +