解題區/解題區 - UVa

UVa 12871 - Landmine Cleaner

Problem

給予每一個格子的得分，分數為鄰近九格的 L 個數 (1 個 1 分) 加上自己是否為 L (3 分)，因此最低 0 分，最高 12 分。

保證只有唯一解。

Sample Input

1
2
3
4
5
1
3 4
2 6 3 2
7 5 7 5
6 7 3 2

Sample Output

1
2
3
-L--
L-LL
LL--

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 1024
int A[MAXN][MAXN], solv[MAXN][MAXN];
int g[MAXN][MAXN];
const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
int n, m;
int isplace(int x, int y) {
    int v = A[x][y], tx, ty;
    int unknown = 0, score = 0;
    for (int i = 0; i < 8; i++) {
        tx = x + dx[i], ty = y + dy[i];
        if (tx < 0 || ty < 0 || tx >= n || ty >= m)
            continue;
        if (solv[tx][ty])	score += g[tx][ty];
        else				unknown++;
    }
    if (v < 3)					return -1;
    if (v > 8)					return 1;
    if (score + unknown < v)	return 1;
    if (score + 4 > v)			return -1;
    return 0; // not sure.
}
int main() {
    int testcase;
    int t;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &A[i][j]);
            }
        }
        memset(solv, 0, sizeof(solv));
        int test = n * m;
        while (test) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (solv[i][j])	continue;
                    int t = isplace(i, j);
                    if (t) {
                        test--;
                        g[i][j] = t > 0;
                        solv[i][j] = 1;
                    }
                }
            }
            
        }
        for (int i = 0; i < n; i++, puts("")) {
            for (int j = 0; j < m; j++) {
                if (solv[i][j])
                    putchar(g[i][j] ? 'L' : '-');
                else {
                    assert(false);
                }
            }
        }
    }
    return 0;
}
/*
9999
3 4
2 6 3 2
7 5 7 5
6 7 3 2
3 3
7 9 7
9 12 9
7 9 7
3 1
0
0
0
*/
Read More +
解題區/解題區 - UVa

UVa 12431 - Happy 10/9 Day

Problem

計算 base B 下，每一個 digit 都是 d 的情況，長度為 N，mod M 的結果為何？

Sample Input

1
2
1
3 10 2 10

Sample Output

1
Case 1: 2

Solution

找到

$$d B^{0} + d B^{1} + ... + d B^{N-1} \text{ mod } M \\ \Rightarrow d \frac{B - 1}{B^{N} - 1} \text{ mod } M$$

由於 M 超過 int，運算起來仍有機會 overflow，因此要使用模乘法，也就是相當於直式乘法的運算，防止 (a*b) mod 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
#include <stdio.h> 
long long mul(long long a, long long b, long long mod) { 
    long long ret = 0; 
    for( ; b != 0; b>>=1, (a<<=1)%=mod) 
        if(b&1) (ret += a) %= mod; 
    return ret; 
}
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = mul(ret, x, mod);
        y >>= 1, x = mul(x, x, mod);
    }
    return ret;
}
long long solve(long long n, long long b, long long d, long long m) {
    // d * (b^n - 1) / (b - 1) mod m
    long long ret;
    ret = mpow(b, n, (b - 1) * m); // b^n mod (b-1) * m
    ret = (ret + (b - 1) * m - 1)/ (b - 1);
    ret = mul(ret, d, m);
    return ret;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long n, b, d, m, ret;
        scanf("%lld %lld %lld %lld", &n, &b, &d, &m);
        ret = solve(n, b, d, m);
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12425 - Best Friend

Problem

給一個整數 N，接著詢問 x，有多少 gcd(i, N) <= x。

Sample Input

1
2
3
4
5
6
7
8
2
30 3
1
2
10
11 2
1
2

Sample Output

1
2
3
4
5
6
7
Case 1
8
16
28
Case 2
10
10

Solution

先把 N 的因數 f 全部找出，原則上不超過 2000 個，然後建出 phi(N/f[i])。

當要知道 gcd(i, N) = x 時，相當於找到 gcd(i/x, N/x) = 1，任何與 N/x 互質的個數。建造完後，對於每次詢問二分答案即可。

很多地方忘記用 long long，吃了不少 Runtime error。

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 <algorithm>
#include <vector>
#include <map>
using namespace std;
#define maxL (1000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int P[100000], Pt = 0;
int phi[1048576];
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 1000000;
    for (i = 1; i <= n; i++)
    	phi[i] = i;
    for (i = 2; i <= n; i++) {
        if(!GET(i)) {
            for (k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            for (j = i; j <= n; j += i)
            	phi[j] = phi[j]/i * (i-1);
            P[Pt++] = i;
        }
    }
}
vector< pair<long long, int> > factor(long long n) {
    long long on = n;
    vector< pair<long long, int> > R;
    
    for(int i = 0, j; i < Pt && (long long)P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {		
            for(j = 0; n%P[i] == 0; n /= P[i], j++);
            R.push_back(make_pair((long long)P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
void make(int idx, int n, long long m, vector< pair<long long, int> > &v, vector<long long> &ret) {
    if(idx == v.size()) {
        ret.push_back(m);
        return;
    }
    long long a = m, b = v[idx].first;
    for(int i = v[idx].second; i >= 0; i--)
        make(idx + 1, n, a, v, ret), a *= b;
}
long long getPhi(long long n) {
    if (n < 1000000)	return phi[n];
    vector< pair<long long, int> > f = factor(n);
    for (int i = 0; i < f.size(); i++)
        n = n / f[i].first * (f[i].first - 1);
    return n;
}
int main() {
    sieve();
    int testcase, cases = 0, Q;
    long long N, X;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld %d", &N, &Q);
        vector< pair<long long, int> > f = factor(N);
        vector<long long> fa;
        vector<long long> sum;
        make(0, N, 1, f, fa);
        sum.resize(fa.size(), 0);
        sort(fa.begin(), fa.end());
        for (int i = 0; i < fa.size(); i++) {
            if (i)
                sum[i] = sum[i-1] + getPhi(N / fa[i]);
            else
                sum[i] = getPhi(N / fa[i]);
        }
        printf("Case %d\n", ++cases);
        for (int i = 0; i < Q; i++) {
            scanf("%lld", &X);
            if (X <= 0) {
                puts("0");
                continue;
            }
            long long ret = 0;
            int pos = (int)(lower_bound(fa.begin(), fa.end(), X) - fa.begin());
            if (pos >= fa.size() || fa[pos] > X)	pos--;
            ret = sum[pos];
            printf("%lld\n", ret);
        }
    }
    return 0;
}
/*
2
30 3
1
2
10
11 5
0
1
2
11
15
*/
Read More +
解題區/解題區 - UVa

UVa 12404 - Trapezium Drawing

Problem

給予梯形兩點座標、四個邊長。找到另外兩點座標。

Sample Input

1
2
1
0 0 20 0 10 14 8

Sample Output

1
2
Case 1:
14.00000000 8.00000000 0.00000000 8.00000000

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
105
106
107
108
109
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
#define MAXN 131072
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    Pt operator/(const double a) const {
        return Pt(x / a, y / a);
    }
    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;
    }
    bool operator==(const Pt &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    } 
};
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 cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
double solve(double a, double b, double c, double d) {
    // d^2 - x^2 = b^2 - (a - x - c)^2
    // d^2 - x^2 = b^2 - (a-c - x)^2
    // d^2 - x^2 = b^2 - ((a-c)^2 - 2(a-c)x + x^2)
    // d^2 - x^2 = b^2 - (a-c)^2 + 2(a-c)x - x^2
    // d^2 - b^2 + (a-c)^2 = 2(a-c)x
    double x;
    x = (pow(d, 2) - pow(b, 2) + pow(a-c, 2))/(2 * (a-c));
    return x;
}
int main() {
    int testcase, cases = 0;
    double x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        Pt A, B, C, D;
        double a, b, c, d;
        scanf("%lf %lf", &x, &y);
        A = Pt(x, y);
        scanf("%lf %lf", &x, &y);
        B = Pt(x, y);
        scanf("%lf %lf %lf", &b, &c, &d);
        a = dist(A, B);
        x = solve(a, b, c, d);
        
        Pt vAB = (B - A) / a;
        double theta = atan2(sqrt(d*d - x*x), x);
        D = rotateRadian(vAB, theta) * d + A;
        C = D + vAB * c;
        printf("Case %d:\n", ++cases);
        printf("%.8lf %.8lf %.8lf %.8lf\n", C.x, C.y, D.x, D.y);
    }
    return 0;
}
/*
1
0 0 20 0 10 14 8
8
0 0 20 0 10 14 8
0 0 20 0 8 14 10
20 0 0 0 10 14 8
20 0 0 0 8 14 10
8 0 8 20 10 14 8
8 0 8 20 8 14 10
0 20 0 0 10 14 8
0 20 0 0 8 14 10
*/
Read More +
解題區/解題區 - UVa

UVa 10397 - Connect the Campus

Problem

在現有的鋪設下，還有幾處建築物之間沒有連通。

找到花費最小的歐基里德距離生成樹

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
4
103 104
104 100
104 103
100 100
1
4 2
4
103 104
104 100
104 103
100 100
1
4 2

Sample Output

1
2
4.41
4.41

Solution

直接用 kruskal 就可以完成，但是建造邊最慘將會達到 O(n^2)，因此效率並不好，好幾年之後回過頭來寫這一題。

對於 EMST 可以使用 Delaunay triangulation 完成。Delaunay triangulation 原則上可以在 O(n log n) 時間內完成。由於 EMST 是 Delaunay 的 subgraph，而 Delaunay 保證 edge 數最多為 3n - 6。套用 kruskal 的 O(E log E) 算法就能保證在 O(n log n) 時間內完成。

Delaunay triangulation 目前實作有 D&C 和 random 兩種。

計算幾何資料請參照 morris821028/Computational-Geometry 下載。

廣泛的比較下，兩者期望都在 O(n log n) 完成，而實際結果 D&C 普遍速度快很多。random 作法很吃機率期望，原因是要支持動態的 point location 操作，沒有一個好的資料結構來保證每一步的搜索效率，教科書上給予一個類似可持久化結構的 DG structure，深度是期望的 O(log n)，實作起來只會比 O(n) 快個常數倍。但 random increase algorithm 對於演算法的證明的確是比較容易，而且步驟相當好說明。

當效率不好去學 D&C algorithm，一開始要對座標進行排序，也就是不支持動態 (離線操作)，接著針對 x 座標剖半，兩個完成 Delaunay triangulation 的凸包進行合併，接著需要將中間縫隙穿針引線地縫起來。因此要找到兩個凸包的下公切線，然後開始攀爬上去，保證一開始的下公切線一定是 Delaunay edge，然後開始窮舉下一個 Delaunay edge，過程中也不斷地移除不適的邊。

有相當不錯的資料結構可以快速地搜索公切線、圍繞凸包的頂點 … 等，但是根據教科書給予的計算，每一個點的 degree 期望值不超過 9，意即偷偷地窮舉攀爬不影響效率。

關於三點共圓，詢問一點是否在圓內的操作，投影到拋物面上，三點在投影結果上拉出一個平面，若點在圓內，則保證該點在平面的下方。求出外心計算，會造成誤差 (無法儲存除法運算結果)，換成拋物面的思路魯棒性高。

下附 D&C algorithm 的做法，關於 random 就放在 github repo 封存了。

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
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <assert.h>
#include <string.h>
#include <list>
using namespace std;
#define eps 1e-8
#define MAXN (1048576)
#define MAXV 1024
struct Point {
    double x, y;
    int id;
    Point(double a = 0, double b = 0, int c = -1):
    	x(a), y(b), id(c) {}	
    Point operator-(const Point &a) const {
        return Point(x - a.x, y - a.y);
    }
    Point operator+(const Point &a) const {
        return Point(x + a.x, y + a.y);
    }
    Point operator*(const double a) const {
        return Point(x * a, y * a);
    }
    Point operator/(const double a) const {
        return Point(x / a, y / a);
    }
    bool operator<(const Point &a) const {
        if (fabs(x - a.x) > eps)	return x < a.x;
        if (fabs(y - a.y) > eps)	return y < a.y;
        return false;
    }
    bool operator==(const Point &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator!=(const Point &a) const {
        return !(fabs(x - a.x) < eps && fabs(y - a.y) < eps);
    } 
    void read(int id = -1) {
        this->id = id;
    }
    double dist(Point b) {
        return hypot(x - b.x, y - b.y);
    }
    double dist2(Point b) {
        return (x - b.x) * (x - b.x) + (y - b.y) * (y - b.y);
    }
    void print() {
        printf("point (%lf, %lf)\n", x, y);
    }
};
struct Point3D {
    double x, y, z;
    Point3D(double a = 0, double b = 0, double c = 0):
        x(a), y(b), z(c) {}
    Point3D(Point p) {
        x = p.x, y = p.y, z = p.x * p.x + p.y * p.y;
    }
    Point3D operator-(const Point3D &a) const {
        return Point3D(x - a.x, y - a.y, z - a.z);
    }
    double dot(Point3D a) {
    	return x * a.x + y * a.y + z * a.z;
    }
};
struct Edge {
    int id;
    list<Edge>::iterator twin;
    Edge(int id = 0) {
        this->id = id;
    }
};
int cmpZero(double v) {
    if (fabs(v) > eps)	return v > 0 ? 1 : -1;
    return 0;
}
double cross(Point o, Point a, Point b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
Point3D cross(Point3D a, Point3D b) { // normal vector
    return Point3D(a.y * b.z - a.z * b.y 
                 , -a.x * b.z + a.z * b.x
                 , a.x * b.y - a.y * b.x);
}
int inCircle(Point a, Point b, Point c, Point p) {
    if (cross(a, b, c) < 0)
        swap(b, c);
    Point3D a3(a), b3(b), c3(c), p3(p);
//	printf("%lf %lf %lf\n", a3.x, a3.y, a3.z);
//	printf("%lf %lf %lf\n", b3.x, b3.y, b3.z);
//	printf("%lf %lf %lf\n", c3.x, c3.y, c3.z);
//	printf("%lf %lf %lf\n", p3.x, p3.y, p3.z);
    b3 = b3 - a3, c3 = c3 - a3, p3 = p3 - a3;
    Point3D f = cross(b3, c3); // normal vector
    return cmpZero(p3.dot(f)); // check same direction, in: < 0, on: = 0, out: > 0
}
int intersection(Point a, Point b, Point c, Point d) { // seg(a, b) and seg(c, d)
    return cmpZero(cross(a, c, b)) * cmpZero(cross(a, b, d)) > 0 
        && cmpZero(cross(c, a, d)) * cmpZero(cross(c, d, b)) > 0;
}
class Delaunay {
    public:
    list<Edge> head[MAXV]; // graph
    Point p[MAXV];
    int n, rename[MAXV];
    void init(int n, Point p[]) {
        for (int i = 0; i < n; i++)
            head[i].clear();
        for (int i = 0; i < n; i++)
            this->p[i] = p[i];
        sort(this->p, this->p + n);
        for (int i = 0; i < n; i++)
            rename[p[i].id] = i;
        this->n = n;
        divide(0, n - 1);
    }
    void addEdge(int u, int v) {
        head[u].push_front(Edge(v));
        head[v].push_front(Edge(u));
        head[u].begin()->twin = head[v].begin();
        head[v].begin()->twin = head[u].begin();
    }
    void divide(int l, int r) {
        if (r - l <= 1) { // #point <= 2
            for (int i = l; i <= r; i++)
                for (int j = i+1; j <= r; j++)
                    addEdge(i, j); 
            return;
        }
        int mid = (l + r) /2;
        divide(l, mid);
        divide(mid + 1, r);
        
        list<Edge>::iterator it;
        int nowl = l, nowr = r;
        
//		printf("divide %d %d\n", l, r);
        for (int update = 1; update; ) { // find left and right convex, lower common tangent
            update = 0;
            Point ptL = p[nowl], ptR = p[nowr];
            for (it = head[nowl].begin(); it != head[nowl].end(); it++) {
                Point t = p[it->id];
                double v = cross(ptR, ptL, t);
                if (cmpZero(v) > 0 || (cmpZero(v) == 0 && ptR.dist2(t) < ptR.dist2(ptL))) {
                    nowl = it->id, update = 1;
                    break;
                }
            }
            if (update)	continue;
            for (it = head[nowr].begin(); it != head[nowr].end(); it++) {
                Point t = p[it->id];
                double v = cross(ptL, ptR, t);
                if (cmpZero(v) < 0 || (cmpZero(v) == 0 && ptL.dist2(t) < ptL.dist2(ptR))) {
                    nowr = it->id, update = 1;
                    break;
                }
            }
        }
        
        addEdge(nowl, nowr); // add tangent
//		printf("add base %d %d\n", nowl, nowr);
        for (int update = 1; true;) {
            update = 0;
            Point ptL = p[nowl], ptR = p[nowr];
            int ch = -1, side = 0;
            for (it = head[nowl].begin(); it != head[nowl].end(); it++) {
//				ptL.print(), ptR.print(), p[it->id].print();
                if (cmpZero(cross(ptL, ptR, p[it->id])) > 0
                    && (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0))
                    ch = it->id, side = -1;
//				printf("test L %d %d %d\n", nowl, it->id, inCircle(ptL, ptR, p[ch], p[it->id]));
            }
            for (it = head[nowr].begin(); it != head[nowr].end(); it++) {
                if (cmpZero(cross(ptR, p[it->id], ptL)) > 0
                    && (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0))
                    ch = it->id, side = 1;
//				printf("test R %d %d %d\n", nowr, it->id, inCircle(ptL, ptR, p[ch], p[it->id])); 
            }
            if (ch == -1)	break; // upper common tangent
//			printf("choose %d %d\n", ch, side);
            if (side == -1) {
                for (it = head[nowl].begin(); it != head[nowl].end(); ) {
                    if (intersection(ptL, p[it->id], ptR, p[ch])) {
                        head[it->id].erase(it->twin);
                        head[nowl].erase(it++);
                    } else
                        it++;
                }
                nowl = ch;
                addEdge(nowl, nowr);
            } else {
                for (it = head[nowr].begin(); it != head[nowr].end(); ) {
                    if (intersection(ptR, p[it->id], ptL, p[ch])) {
                        head[it->id].erase(it->twin);
                        head[nowr].erase(it++);
                    } else
                        it++;
                }
                nowr = ch;
                addEdge(nowl, nowr);
            }
        }
    }
    
    vector< pair<int, int> > getEdge() {
        vector< pair<int, int> > ret;
        list<Edge>::iterator it;
        for (int i = 0; i < n; i++) {
            for (it = head[i].begin(); it != head[i].end(); it++) {
                if (it->id < i)
                    continue;
//				printf("DG %d %d\n", i, it->id);
                ret.push_back(make_pair(p[i].id, p[it->id].id));
            }
        }
        return ret;
    }
} tool;
struct edge {
    int x, y, v;
    edge(int a = 0, int b = 0, int c = 0):
        x(a), y(b), v(c) {}
    bool operator<(const edge &a) const {
        return v < a.v;
    }
};
int parent[1024], weight[1024];
void init(int n) {
    for(int i= 0; i <= n; i++)
        parent[i] = i, weight[i] = 1;
}
int findp(int x) {
    return x == parent[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])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
int main() {
    int n, m, cases = 0;
    Point p[MAXV];
    while (scanf("%d", &n) == 1) {
        init(n);
        int x, y;
        int e = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            p[i] = Point(x, y, i);
        }
        
        tool.init(n, p);
            
        vector<edge> E;
        vector< pair<int, int> > DG = tool.getEdge();
        for (int i = 0; i < DG.size(); i++) {
            x = DG[i].first, y = DG[i].second;
            int v = (p[x].x - p[y].x) * (p[x].x - p[y].x) + 
                        (p[x].y - p[y].y) * (p[x].y - p[y].y);
            E.push_back(edge(x, y, v));
//			printf("DG %d %d %d\n", x, y, v);
        }
        
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            e += joint(x, y);
        }
        
        sort(E.begin(), E.end());
        double ret = 0;
        for (int i = 0; i < E.size(); i++) {
            x = E[i].x, y = E[i].y;
            if (joint(x, y)) {
                ret += sqrt(E[i].v);
                e++;
                if (e == n - 1)
                    break;
            }
        }
        printf("%.2lf\n", ret);
    }
    return 0;
}
/*
2
1 1
2 2
0
1
1 1
0
4
103 104
104 100
104 103
100 100
1
4 2
4
3 4
4 0
4 3
0 0
1
4 2
*/
Read More +
解題區/解題區 - UVa

UVa 1674 - Lightning Energy Report

Problem

給一棵樹，接著有數次操作將路徑 (u, v) 上的所有節點權重加上 k。

請問最後每一個點帶有的權重為何？

Sample Input

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

Sample Output

1
2
3
4
5
6
7
8
9
10
Case #1: 
5 
25 
28 
3 
110 
3 
13 
18 
5

Solution

參照 zerojudge b322. 樹形鎖頭 的解法。

解說圖

A[] : 子樹總和
B[] : 節點權重

增加路徑 u 到 v 的權重為 k 時，路徑相當於 u 到某點 x 再到 LCA(u, v) 接著 y 最後 v。

那我們增加節點 u, v 的權重 B[u] += k, B[v] += k，減少其 LCA 的權重 B[LCA(u, v)] -= 2k，然後你會觀察 A[] 的部分，權重增加 k 的只會有 u-v 之間的所有節點。

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
#define MAXV 65536
int visited[MAXV];
vector<int> tree[MAXV];
int parent[MAXV], weight[MAXV];
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])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
// LCA
vector< pair<int, int> > Q[MAXV];// query pair, input index - node
int LCA[131072]; // [query time] input query answer buffer.
void tarjan(int u, int p) {// rooted-tree.
    parent[u] = u;
    for(int i = 0; i < tree[u].size(); i++) {//son node.
        int v = tree[u][i];
        if(v == p)	continue;
        tarjan(v, u);
        parent[findp(v)] = u;
    }
    visited[u] = 1;
    for(int i = 0; i < Q[u].size(); i++) {
        if(visited[Q[u][i].second]) {
            LCA[Q[u][i].first] = findp(Q[u][i].second);
        }
    }
}
int dfs(int u, int p, int weight[]) {
    int sum = weight[u];
    for(int i = 0; i < tree[u].size(); i++) {//son node.
        int v = tree[u][i];
        if(v == p)	continue;
        sum += dfs(v, u, weight);
    }
    return weight[u] = sum;
}
int main() {
    //	freopen("in.txt", "r+t", stdin);
    //	freopen("out2.txt", "w+t", stdout);
    int n, m, x, y;
    int testcase, cases = 0;
    int X[MAXV], Y[MAXV], K[MAXV];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            tree[i].clear();
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            tree[x].push_back(y);
            tree[y].push_back(x);
        }
        
        int weight[MAXV] = {}, extra[MAXV] = {};
        for (int i = 0; i < n; i++)
            visited[i] = 0, Q[i].clear();
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &X[i], &Y[i], &K[i]);
            Q[X[i]].push_back(make_pair(i, Y[i]));
            Q[Y[i]].push_back(make_pair(i, X[i]));
        }
        tarjan(0, -1);
        for (int i = 0; i < m; i++) {
            extra[LCA[i]] += K[i];
            weight[X[i]] += K[i];
            weight[Y[i]] += K[i];
            weight[LCA[i]] -= 2 * K[i];
        }
        dfs(0, -1, weight);
        
        printf("Case #%d:\n", ++cases);
        for (int i = 0; i < n; i++)
            printf("%d\n", weight[i] + extra[i]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1659 - Help Little Laura

Problem

平面上有 N 個點，並且給定數條有向邊，在這個遊戲中，必須從某個點出發，沿著邊回到起點。每一條邊最多經過一次，而點可以重複走。

每經過一條邊，可以獲益每單位長 X 的利益，但是使用一條邊的成本為 Y。

請問最大獲益為何？

Sample Input

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

Sample Output

1
2
3
Case 1: 16.00 
Case 2: 0.00 
Case 3: 522.18

Solution

目標將每一個點調整 indeg = outdeg，要將多餘的邊捨去，只要滿足 indeg = outdeg，則可以表示平面上有數個尤拉環道。

接著建造最少費用流的模型，來捨去掉多餘的邊。當存有邊 e(i->j) 時，outdeg[i]++, indeg[j]++，一開始選擇所有 cost(e(i->j)) > 0 的邊，作為初始盤面，對於 cost(e(i->j)) < 0 先不選，選擇獲益為負的結果並不好。

如果 cost(e(i->j)) > 0，建造邊 i->j, flow: 1, cost: cost(e(i->j))，假使在最少費用流中選擇這一條邊時，就會將 deg 數量減少。對於 cost(e(i->j)) < 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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;
#define eps 1e-8
struct Node {
    int x, y, cap;
    double cost;// x->y, v
    int next;
} edge[1000005];
int e, head[600], prev[600], record[600], inq[600];
double dis[600];
void addEdge(int x, int y, int cap, double 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++;
}
double mincost(int s, int t, int n) {
    double mncost = 0;
    int flow, totflow = 0;
    int i, x, y;
    double oo = 1e+30;
    while(1) {
    	for (int i = 0; i <= n; i++)
    		dis[i] = oo;
        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 = 0x3f3f3f3f;
        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 cases = 0;
    int N, X, Y;
    int x[128], y[128], u;
    while (scanf("%d %d %d", &N, &X, &Y) == 3 && N) {
    	vector<int> g[128];
    	for (int i = 1; i <= N; i++) {
    		scanf("%d %d", &x[i], &y[i]);
    		while (scanf("%d", &u) == 1 && u)
    			g[i].push_back(u);
        } 
        
    	e = 0;
        memset(head, -1, sizeof(head));	
        int deg[128] = {};
        double sumCost = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < g[i].size(); j++) {
                u = g[i][j];
                double d = hypot(x[i] - x[u], y[i] - y[u]);
                double cost = d * X - Y;
                if (cost < 0) {
                    addEdge(u, i, 1, -cost);
                } else {
                    sumCost += cost;
                    addEdge(i, u, 1, cost);
                    deg[u]--, deg[i]++;
                }
            }
        }
        int source = 0, sink = N + 1;
        for (int i = 1; i <= N; i++) {
            if (deg[i] > 0)	addEdge(source, i, deg[i], 0);
            if (deg[i] < 0)	addEdge(i, sink, -deg[i], 0);
        }
        double mncost = mincost(source, sink, N+1);
        printf("Case %d: %.2lf\n", ++cases, sumCost - mncost + eps);
    }
    return 0;
}
/*
4 5 1 
0 0 2 3 0 
1 0 3 4 0 
1 1 4 0 
0 1 1 0 
1 2 1 
0 0 0 
10 7 2 
0 0 2 4 0 
5 0 3 0 
5 10 4 10 0 
2 3 5 0 
7 5 6 0 
0 11 1 0 
8 0 10 5 0 
18 3 7 0 
14 5 8 1 0 
12 9 9 0 
0
*/
Read More +
解題區/解題區 - UVa

UVa 1649 - Binomial coefficients

Problem

組合的反函數，現在給定組合數，輸出是由哪幾種組合可以配出組合數。

Sample Input

1
2
3
2
2
15

Sample Output

1
2
3
4
1
(2,1)
4
(6,2) (6,4) (15,1) (15,14)

Solution

先預見表，完成前幾項的結果。

看著巴斯卡三角形單純看 i，對於 C(n, i) 是一個嚴格遞增的函數。因此窮舉 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
#include <stdio.h>
#include <map> 
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 1024
const long long MAXVAL = 1e+16, MAXVAL2 = 1e+15;
long long C[MAXN][MAXN] = {};
map<long long, vector< pair<long long, long long> > > R;
int testCombination(long long n, long long m, long long Cnm) { // test C(n, m), m < 10
    long long ret = 1;
    m = min(m, n-m);
    for (long long i = 1; i <= m; i++) {
        if (Cnm * i / (n + 1 - i) / ret  < 1)
            return 1;
        ret = ret * (n + 1 - i) / i;
    }
    return ret == Cnm ? 0 : -1;
}
vector< pair<long long, long long> > invCombination(long long n) {
    vector< pair<long long, long long> > ret;
    ret = R[n];
    for (int i = 1; i < 10; i++) {
        long long l = 1, r = n, mid;
        while (l <= r) {
            mid = (l + r)/2;
            int f = testCombination(mid, i, n); // {-1, 0, 1}
            if (f == 0) {
                ret.push_back(make_pair(mid, i));
                ret.push_back(make_pair(mid, mid - i));
                break;
            }
            if (f < 0)
                l = mid + 1;
            else
                r = mid - 1;
        }
    }
    sort(ret.begin(), ret.end());
    ret.resize(unique(ret.begin(), ret.end()) - ret.begin());
    return ret;
}
int main() {
//	printf("%d\n", testCombination(5000, 2, 12497500));
    C[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
            C[i][j] = min(C[i][j], MAXVAL);
            if (j != i && C[i][j] <= MAXVAL2)
                R[C[i][j]].push_back(make_pair(i, j));
        }
    }
//	for (int i = 0; i < 10; i++)
//		printf("%lld\n", C[MAXN-1][i]);
    int testcase;
    long long n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld", &n);
        vector< pair<long long, long long> > r = invCombination(n);
        printf("%d\n", (int) r.size());
        for (int i = 0; i < r.size(); i++)
            printf("(%lld,%lld)%c", r[i].first, r[i].second, i == r.size()-1 ? '\n' : ' ');
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1614 - Hell on the Markets

Problem

金融交易，它們希望賣出、買進交易結束後的差為零。

意即將數字分兩堆的結果相同。

Sample Input

1
2
3
4
4
1 2 3 3
4
1 2 3 4

Sample Output

1
2
3
No
Yes
1 -1 -1 1

Solution

由於保證 0 < a[i] <= i，基於這一點，可以發現到只考慮一個數字 a[1] 時，必然可以湊出 1 - a[1]，當考慮第 i 大數字時，保證前 i - 1 個數字可以湊出 1 ~ (i-1)，加上第 i 個數字必然可以湊出 1 ~ (i-1)+a[i] (1, 2, 3, ..., i-1, a[i], 1+a[i], ..., i-1+a[i])。

而事實上，可以湊出所有的 1 ~ sum[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
#include <stdio.h>
#include <algorithm>
using namespace std;
    
pair<int, int> A[100000];
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        long long sum = 0;
        int ret[100000] = {};
        for (int i = 0; i < n; i++) {
            scanf("%d", &A[i].first);
            A[i].second = i;
            sum += A[i].first;
        } 
        if (sum%2) {
            puts("No");
        } else {
            puts("Yes");
            sum /= 2;
            sort(A, A+n);
            for (int i = n-1; i >= 0; i--) {
                if (sum >= A[i].first)
                    sum -= A[i].first, ret[A[i].second] = 1;
                else
                    ret[A[i].second] = -1;
            }
            for (int i = 0; i < n; i++)
                printf("%d%c", ret[i], i == n-1 ? '\n' : ' ');
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1169 - Robotruck

Problem

在一個二維平面中，灑落 N 個垃圾，機器人從原點 (0, 0) 依序要蒐集垃圾，機器人一次承載 W 重量的垃圾，隨時可以返回原點將垃圾放下。

請問依序收集垃圾的最少花費為何？

Sample Input

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

Sample Output

1
14

Solution

一開始得到方程式 dp[i] = min(dp[j-1] + cost[j, i] + dist[j] + dist[i]) 必須滿足 w[j, i] <= C，其中 j <= i。

其中 dp[i] 表示依序收集前 i 個垃圾的最小花費，cost[j, i] 表示走訪編號 j 到 i 垃圾位置的花費，補上原點到編號 j，並且收集完從 i 回到原點。

這樣的方程式轉換需要 N^2 時間，化簡一下式子

1
2
3
dp[i] = dp[j-1] + cost[j, i] + dist[j] + dist[i]
dp[i] = dp[j-1] + cost[i] - cost[j] + dist[j] + dist[i]
dp[i] = (dp[j-1] - cost[j] + dist[j]) + cost[i] + dist[i]

會發現 i, j 獨立，也滿足垃圾重量累計遞增，因此盡可能保留 dp[j-1] - cost[j] + dist[j] 小的結果，並且重量不超過限制，當重量超過限制時，該組答案在隨後保證再也不會用到，直接捨棄之。

核心就是單調隊列的思路。

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
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 131072
int x[MAXN], y[MAXN], w[MAXN];
int cost[MAXN], dist[MAXN];
int dp[MAXN];
int f(int j) {
    return dp[j-1] - cost[j] + dist[j];
}
int main() {
    int testcase, C, N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &C, &N);
        w[0] = 0, cost[0] = 0;
        for (int i = 1; i <= N; i++) {
            scanf("%d %d %d", &x[i], &y[i], &w[i]);
            cost[i] = cost[i-1] + abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]);
            dist[i] = abs(x[i]) + abs(y[i]);
            w[i] += w[i-1];
        }
        // dp[i] = dp[j-1] + cost[j, i] + dist[j] + dist[i]
        // dp[i] = dp[j-1] + cost[i] - cost[j] + dist[j] + dist[i]
        // dp[i] = (dp[j-1] - cost[j] + dist[j]) + cost[i] + dist[i]
        deque<int> Q;
        Q.push_back(0);
        for (int i = 1; i <= N; i++) {
            while (!Q.empty() && w[i] - w[Q.front()] > C)
                Q.pop_front();
            dp[i] = f(Q.front() + 1) + cost[i] + dist[i];
            while (!Q.empty() && f(Q.back() + 1) >= f(i + 1))
                Q.pop_back();
            Q.push_back(i);
        }
        printf("%d\n", dp[N]);
        if (testcase)	puts("");
    }
    return 0;
}
Read More +