解題區►解題區 - UVa

UVa 12653 - Buses

Problem

長度為 n (保證為 5 的倍數)個對列，小公車長度為 5，種類有 K 種，大公車長度 10，種類有 L 種，請問排列的方法數有多少種？

Sample Input

1
2
3
4
25 5 5
5 1000 1000
20 17 31
15 9 2

Sample Output

1
2
3
4
006000
001000
111359
000765

Solution

推導公式如下

$$A_{n} = K * A_{n-1} + L * A_{n-2}$$

考慮塞入最後一台車的類型，找到遞迴公式。之後將其變成線性變換的結果。

$$M = \begin{bmatrix} K & 1 \\ L & 0 \end{bmatrix} \\ M^n = \begin{bmatrix} A^n & A^{n-1} \\ A^{n-1} & A^{n-2} \end{bmatrix} \\$$ 
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
#include <stdio.h>
#include <string.h>
const long long mod = 1000000LL;
struct Matrix {
	long long v[2][2];
	int row, col; // row x col
	Matrix(int n, int m, long long a = 0) {
		memset(v, 0, sizeof(v));
		row = n, col = m;
		for(int i = 0; i < row && i < col; i++)
			v[i][i] = a;
	}
	Matrix operator*(const Matrix& x) const {
		Matrix ret(row, x.col);
		for(int i = 0; i < row; i++)
			for(int j = 0; j < x.col; j++)
				for(int k = 0; k < col; k++)
					ret.v[i][j] = (ret.v[i][j] + v[i][k] * x.v[k][j]%mod)%mod;
		return ret;
	}
	Matrix operator^(const long long& n) const {
		Matrix ret(row, col, 1), x = *this;
		long long y = n;
		while(y) {
			if(y&1)	ret = ret * x;
			y = y>>1, x = x * x;
		}
		return ret;
	}
};
int main() {
    long long N, K, L;
    while (scanf("%lld %lld %lld", &N, &K, &L) == 3) {
        N /= 5;
//        long long dp[120]= {};
//        dp[0] = 1;
//        for (int i = 1; i <= N; i++) {
//            dp[i] = dp[i-1] * K;
//            if (i - 2 >= 0) {
//                dp[i] += dp[i-2] * L;
//            }
//        }
        Matrix A(2, 2, 0);
        A.v[0][0] = K%mod, A.v[0][1] = 1;
        A.v[1][0] = L%mod, A.v[1][1] = 0;
        Matrix M = A ^ N;
        printf("%06lld\n", M.v[0][0]);
    }
    return 0;
}
/*
 $ a_{n} = K a_{n-1} + L a_{n-2} $
 
 25 5 5
 5 1000 1000
 20 17 31
 15 9 2
 */
Read More +
解題區►解題區 - UVa

UVa 12379 - Central Post Office

Problem

給定一個樹狀圖 (題目說明任兩點只有一條唯一路徑)，打算選定一點作為送貨中心，貨車將從該地點出發，經過所有的點，目標最小化送貨時間。不用考慮最後停在哪裡，只需要考慮最後一個送達的時刻。

Sample Input

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

Sample Output

1
2
1
5

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
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
// euler path
#define MAXN 10005
int dist[MAXN], visited[MAXN];
vector<int> g[MAXN];
void dfs(int u) {
	visited[u] = 1;
	for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (visited[v]) continue;
		dist[v] = dist[u]+1;
		dfs(v);
	}
}
int tree_diameter(int n) {
    memset(visited, 0, sizeof(visited));
    dist[1] = 0, dfs(1);
    
    int p = (int)(max_element(dist + 1, dist + n + 1) - dist);
    memset(visited, 0, sizeof(visited));
    dist[p] = 0, dfs(p);
    return *(max_element(dist + 1, dist + n + 1));
}
int main() {
    int testcase, n, m, x;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &m);
            g[i].clear();
            for (int j = 0; j < m; j++) {
                scanf("%d", &x);
                g[i].push_back(x);
            }
        }
        printf("%d\n", (2 * n - 2) - tree_diameter(n));
    }
    return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12322 - Handgun Shooting Sport

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
33
34
35
36
37
10
-309 98 -258 204
-303 83 -251 98
-218 111 -287 31
-145 204 -23 257
-129 272 59 272
-8 159 74 130
150 146 68 174
59 196 128 242
98 256 241 235
197 61 173 92
3
-100 10 -100 50
-50 100 50 100
100 10 100 50
5
-100 100 100 100
-80 120 80 120
-60 140 60 140
-40 160 40 160
-20 180 20 180
2
-50 50 0 50
-10 70 50 70
2
-50 50 0 50
0 70 50 70
2
-50 50 0 50
10 70 50 70
5
-4 10 0 2
5 10 0 1
-2 1 -3 4
4 10 2 10
0 9 -2 9
0

Sample Output

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

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
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
int main() {
    int n, x1, x2, y1, y2;
    while (scanf("%d", &n) == 1 && n) {
        vector< pair<double, double> > interval;
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            double l = atan2(y1, x1), r = atan2(y2, x2);
            if (l > r)
                swap(l, r);
            interval.push_back(make_pair(l, r));
//            printf("[%lf %lf]\n", l, r);
        }
        sort(interval.begin(), interval.end());
        
        int ret = 0;
#define eps 0
        for (int i = 0, j; i < interval.size(); ) {
            ret++;
            double coverR = interval[i].second;
//            printf("try [%lf %lf]\n", interval[i].first, interval[i].second);
            for (j = i; j < interval.size() && interval[j].first <= coverR + eps; j++)
                coverR = min(coverR, interval[j].second);
            i = j;
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
 */
Read More +
解題區►解題區 - UVa

UVa 12307 - Smallest Enclosing Rectangle

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
5
0 0
2 0
2 2
0 2
1 1
5
1 1
9 0
7 10
0 5
2 11
3
5 3
7 2
6 6
4
6 3
9 1
9 6
8 10
0

Sample Output

1
2
3
4
4.00 8.00
95.38 39.19
7.00 11.38
27.00 23.63

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
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
// Accepted
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)	return x < a.x;
        return y < a.y;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    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 val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
typedef Pt Vector;
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;
}
double distProjection(Pt as, Pt at, Pt s) {
	double a, b, c;
	a = at.y - as.y;
	b = as.x - at.x;
	c = - (a * as.x + b * as.y);
	return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
struct Seg {
    Pt s, e;
};
int calcIntersection(Seg a, Seg b, Pt &p) {
    double a1, b1, c1, a2, b2, c2;
    double d, dx, dy;
    a1 = a.s.y-a.e.y, b1 = -a.s.x+a.e.x;
    a2 = b.s.y-b.e.y, b2 = -b.s.x+b.e.x;
    c1 = a1*a.s.x + b1*a.s.y;
    c2 = a2*b.s.x + b2*b.s.y;
    d = a1*b2 - a2*b1;
    dx = c1*b2 - c2*b1;
    dy = a1*c2 - a2*c1;
    if(fabs(d) < eps) // NONE or LINE
        return 0;
    p.x = dx / d, p.y = dy / d;
    /*printf("%lf %lf - %lf %lf\n", a.s.x, a.s.y, a.e.x, a.e.y);
     printf("%lf %lf - %lf %lf\n", b.s.x, b.s.y, b.e.x, b.e.y);
     printf("%lf %lf\n", p.x, p.y);*/
    return onSeg(a.s, a.e, p) && onSeg(b.s, b.e, p);
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(p[i].y > q.y != p[j].y > q.y &&
           q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
            cnt++;
    }
    return cnt&1;
}
double calcArea(Pt p[], int n) {
    if(n < 3)   return 0.0;
    double ret = 0;
    int i;
    p[n] = p[0];
    for(i = 0; i < n; i++)
        ret += p[i].x * p[i+1].y - p[i].y * p[i+1].x;
    return fabs(ret)/2;
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
#define INF 1e+30
void smallRect(int n, Pt p[]) {
	int l = 1, r = 1, u = 1;
    double area = INF, per = INF;
	for( int i = 0; i < n; i++) {
		Pt edge = (p[(i+1)%n]-p[i]) / dist(p[(i+1)%n], p[i]);
        
		while(dot(edge, p[r%n]-p[i]) < dot(edge, p[(r+1)%n]-p[i]))
            r++;
		while(u < r || cross2(edge, p[u%n]-p[i]) < cross2(edge, p[(u+1)%n]-p[i]))
            u++;
		while(l < u || dot(edge, p[l%n]-p[i]) > dot(edge, p[(l+1)%n]-p[i]))
            l++;
		double w = dot(edge, p[r%n]-p[i]) - dot(edge, p[l%n]-p[i]);
		double h = fabs(cross2(p[i]-p[u%n], p[(i+1)%n]-p[u%n]) / dist(p[i], p[(i+1)%n]));
        
		area = min(area, w * h);
		per = min(per, (w + h)*2);
	}
    printf("%.2lf %.2lf\n", area, per);
}
Pt p[262144], ch[262144];
int main() {
    int n, m;
    while(scanf("%d", &n) == 1 && n) {
    	for(int i = 0; i < n; i++)
    		scanf("%lf %lf", &p[i].x, &p[i].y);
        m = monotone(n, p, ch);
		smallRect(m, ch);
    }
    return 0;
}
/*
 5
 0 0
 2 0
 2 2
 0 2
 1 1
 5
 1 1
 9 0
 7 10
 0 5
 2 11
 3
 5 3
 7 2
 6 6
 4
 6 3
 9 1
 9 6
 8 10
 0
 */
Read More +
解題區►解題區 - UVa

UVa 12271 - Comparing answers

Problem

抄答案如何快速檢查？題目是這樣子的，給定任兩點之間的路徑數，輸出從 i->j 兩步可到達的方法數。

現在只需要比對答案是否正確。

Sample Input

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

Sample Output

1
2
YES
NO

Solution

從矩陣乘法可以知道兩步內到達的方法數恰好是矩陣 $A \ast A$，假設答案是 B，A 和 B 都是 $n \ast n$ 矩陣，驗證 $A \ast A = B$ 是否正確，$A \ast A$ 用一般的矩陣乘法需要耗費 O(n^3) 的時間。

為了快速驗證，採用一個隨機算法，同乘上一個隨機的 n * 1 矩陣 C，那麼將問題轉換成

$(A \ast (A \ast C)) = B * C$

發現每一步操作可以在 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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <iostream>
#include <map>
using namespace std;
// random algroithm, identify A * A = B
// (A * (A * C)) = B * C => O(n^2)
#define MAXN 1024
int A[MAXN][MAXN], B[MAXN][MAXN];
int C[MAXN], D[MAXN], E[MAXN], F[MAXN];
int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &A[i][j]);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &B[i][j]);
        for (int i = 0; i < n; i++)
            C[i] = rand() + 1;
        for (int i = 0; i < n; i++) {
            int x = 0, y = 0;
            for (int j = 0; j < n; j++)
                x += C[j] * A[i][j], y += C[j] * B[i][j];
            D[i] = x, E[i] = y;
        }
        int ok = 1;
        for (int i = 0; i < n && ok; i++) {
            int x = 0;
            for (int j = 0; j < n; j++)
                x += D[j] * A[i][j];
            F[i] = x;
            ok &= F[i] == E[i];
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}
/*
 */
Read More +
解題區►解題區 - UVa

UVa 12265 - Selling Land

Problem

求以每個點當作矩形右下角，找到所有最大周長矩形的所有情況。

Sample Input

1
2
3
4
5
6
7
8
1
6 5
..#.#
.#...
#..##
...#.
#....
#..#.

Sample Output

1
2
3
4
5
6 x 4
5 x 6
5 x 8
3 x 10
1 x 12

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
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <string.h>
#define maxL ((1024*1024)>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
using namespace std;
int mark[maxL];
void solve(int n, int h[], int record[]) {
    int i, height;
    stack< pair<int, int> > stk;// <height, position>
    pair<int, int> e;
    h[n] = 0;// visual height.
    for(i = 0; i <= n; i++) {
        height = h[i];
        e = make_pair(height, i);
        while(!stk.empty() && height <= stk.top().first)
            e = stk.top(), stk.pop();
        if (height == 0)
            continue;
        if(stk.empty() || height - stk.top().first > e.second - stk.top().second) {
            record[height + (i - e.second + 1)]++;
            stk.push(make_pair(height, e.second));
        } else {
            record[stk.top().first + (i - stk.top().second + 1)]++;
        }
    }
}
int n, m, h[1024];
int main() {
	int testcase;
    char line[1024];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
    	memset(mark, 0, sizeof(mark));
    	memset(h, 0, sizeof(h));
        for(int i = 0; i < n; i++) {
        	scanf("%s", line);
            for (int j = 0; j < m; j++) {
                if (line[j] == '.') {
                    SET(i * 1024 + j);
                }
            }
        }
        int record[2048] = {};
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
            	if(GET(j * 1024 + i))
            		h[j]++;
            	else
            		h[j] = 0;
            }
            solve(n, h, record);
        }
        for (int i = 1; i <= n+m; i++) {
            if (record[i]) {
                printf("%d x %d\n", record[i], i<<1);
            }
        }
    }
    return 0;
}
/*
 1
 6 5
 ..#.#
 .#...
 #..##
 ...#.
 #....
 #..#.
 */
Read More +
解題區►解題區 - UVa

UVa 12257 - The Queue

Problem

不能站在自己的長官前面，求排列數有多少種，只會有一個人沒有長官，剩餘的人恰有一個長官。

Sample Input

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

Sample Output

1
Case 1: 8

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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <iostream>
#include <map>
using namespace std;
#define MAXN 1024
const long long mod = 1000000007LL;
long long f[MAXN], invf[MAXN];
vector<int> g[MAXN];
long long dfs(int u, int &size) {
    vector<int> subtree;
    long long ret = 1;
    int sum = 0;
    
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i], w;
        ret = (ret * dfs(v, w))%mod;
        subtree.push_back(w), sum += w;
    }
    size = 1 + sum;
    ret = (ret * f[sum])%mod; // * n!
    for (int i = 0; i < subtree.size(); i++)
        ret = (ret * invf[subtree[i]])%mod; // / a!
    return ret;
}
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = (ret * x)%mod;
        x = (x * x)%mod, y >>= 1;
    }
    return ret;
}
int main() {
    f[0] = 1, invf[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        f[i] = (f[i - 1] * i)%mod;
        invf[i] = mpow(f[i], mod - 2, mod);
    }
    
    int testcase, cases = 0, n;
    int a, b;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            g[i].clear();
        }
        
        int indeg[MAXN] = {}, root = 0, w;
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &a, &b);
            g[a].push_back(b);
            indeg[b]++;
        }
        for (int i = 1; i <= n; i++) {
            if (indeg[i] == 0) {
                root = i;
            }
        }
        long long ret = dfs(root, w);
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
 
 */
Read More +
解題區►解題區 - UVa

UVa 12245 - Hyperactive Girl

Problem

可用工作區間為 [1, m]，則要求分配 [li, ri] 的方式，找到所有可能的分配集合符合

  • 所有區間完全覆蓋住 [1, m] (區間可以重疊)
  • 每一個區間至少單獨佔有一個時間點

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
33
34
35
9 9
2 7
3 5
6 8
5 6
2 8
2 6
0 2
7 9
2 8
18 9
8 15
1 17
0 10
9 18
12 15
1 5
5 6
0 10
11 17
8 7
0 3
2 5
5 8
1 3
3 6
4 6
0 2
1 1
0 1
2 1
0 1
0 0

Sample Output

1
2
3
4
5
4
2
4
1
0

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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <iostream>
#include <map>
using namespace std;
struct Interval {
    int l, r;
    bool operator<(const Interval &a) const {
        return l < a.l || (l == a.l && r < a.r);
    }
};
int main() {
    int n, m;
    const int mod = 100000000;
    Interval D[128];
    while(scanf("%d %d", &m, &n) == 2 && n+m) {
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &D[i].l, &D[i].r);
        }
        sort(D, D+n);
        int dp[128][128] = {}; // [prev][now]
        int ret = 0;
        for (int i = 0; i < n; i++) {
            dp[i][i] = (D[i].l == 0);
            for (int j = i+1; j < n; j++) {
                if (D[j].l > D[i].l && D[j].r > D[i].r && D[j].l <= D[i].r) {
                    for (int k = 0; k <= i; k++) {
                        if (D[k].r >= D[j].l && k != i)
                            continue;
                        dp[i][j] = (dp[i][j] + dp[k][i])%mod;
                    }
                }
            }
            if (D[i].r == m) {
                for (int j = 0; j <= i; j++)
                    ret = (ret + dp[j][i])%mod;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12182 - Toll Road

Problem

給定一棵有權重的樹圖，求其連通子圖權重最大為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
4
1 2 -7
3 2 10
2 4 2
5 4 -2
3
1 2 -8
2 3 -8
3 4 -1000
5
14 15 0
15 92 10
92 65 -5
65 35 10
35 89 -30
0

Sample Output

1
2
3
12
0
15

Solution

這一題跟最大連續和區間一樣，把無向樹弄成有根樹，接著採用 greedy 的方式，找到包含子節點的最大子樹總和。

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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <iostream>
#include <map>
using namespace std;
#define MAXN 262144
struct edge {
    int to, v;
    edge(int a = 0, int b = 0):
    to(a), v(b) {}
};
vector<edge> g[MAXN];
int dp[MAXN];
int used[MAXN];
void dfs(int u, int p) {
    used[u] = 1;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].to, w = g[u][i].v;
        if(used[v])    continue;
        dfs(v, u);
    }
    
    int ret = 0;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].to, w = g[u][i].v;
        if(v == p)    continue;
        if (dp[v] + w > 0) {
            ret += dp[v] + w;
        }
    }
    dp[u] = ret;
}
map<int, int> R;
int rename(int x) {
    int &ret = R[x];
    return ret == 0 ? ret = (int)R.size() : ret;
}
int main() {
    int n, x, y, v;
    while(scanf("%d", &n) == 1 && n) {
        for (int i = 1; i <= R.size(); i++)
            g[i].clear();
        R.clear();
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d", &x, &y, &v);
            x = rename(x), y = rename(y);
            g[x].push_back(edge(y, v));
            g[y].push_back(edge(x, v));
//            printf("-- %d %d %d\n", x, y, v);
        }
        
        n = (int)R.size();
        for (int i = 1; i <= n; i++)
            dp[i] = 0;
        for (int i = 1; i <= n; i++)
            used[i] = 0;
        for (int i = 1; i <= n; i++) {
            if (used[i] == 0) {
                dfs(i, -1);
            }
        }
        
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            ret = max(ret, dp[i]);
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
*/
Read More +
解題區►解題區 - UVa

UVa 12173 - White Water Rafting

Problem

給滑水道兩邊緣座標，求最大半徑的圓可以再滑水道之間穿越。

Sample Input

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

Sample Output

1
2
2.50000000
0.70710678

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
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
using namespace std;
#define eps 1e-6
struct Pt {
    int x, y;
    Pt(int a = 0, int b = 0):
    x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
	Pt operator-(const Pt &a) const {
		Pt ret;
		ret.x = x - a.x;
		ret.y = y - a.y;
        return ret;
    }
};
enum LINE_TYPE {LINE, SEGMENT};
struct LINE2D {
    Pt s, e;
    LINE_TYPE type;
};
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;
}
double distProjection(Pt as, Pt at, Pt s) {
	int a, b, c;
	a = at.y - as.y;
	b = as.x - at.x;
	c = - (a * as.x + b * as.y);
	return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
double dist2Seg(Pt sa, Pt sb, Pt p) {
    double c = 1e+30;
    if(between(sa, sb, p))
        c = min(c, distProjection(sa, sb, p));
    else
        c = min(c, min(dist(sa, p), dist(sb, p)));
    return c;
}
int main() {
    int testcase;
    int n, m;
    Pt Di[128], Do[128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d %d", &Di[i].x, &Di[i].y);
        scanf("%d", &m);
        for (int i = 0; i < m; i++)
            scanf("%d %d", &Do[i].x, &Do[i].y);
        
        double ret = 1e+30;
        Di[n] = Di[0], Do[m] = Do[0];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ret = min(ret, dist2Seg(Di[i], Di[i+1], Do[j]));
                ret = min(ret, dist2Seg(Do[j], Do[j+1], Di[i]));
            }
        }
        printf("%.8lf\n", ret/2);
    }
    return 0;
}
/*
 2
 4
 -5 -5
 5 -5
 5 5
 -5 5
 4
 -10 -10
 -10 10
 10 10
 10 -10
 3
 0 0
 1 0
 1 1
 5
 3 -3
 3 3
 -4 2
 -1 -1
 -2 -2
 */
Read More +