解題區/解題區 - UVa

UVa 12671 - Disjoint water supply

Problem

給一張圖，問有多少對 (u, v) 沒有連通路徑。

Sample Input

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

Sample Output

1
2
14
26

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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <map>
#include <algorithm>
using namespace std;
int parent[32767], weight[32767];
int findp(int x) {
    return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int main() {
    int n, m, x, y;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        for (int i = 0; i <= n; i++) {
            parent[i] = 0, weight[i] = 0;
        }
        
        vector<int> g[1024];
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            if (x == 1) {
                parent[y] = y;
            } else
                g[y].push_back(x);
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < g[i].size(); j++) {
                int u = g[i][j];
                if (parent[i] == 0)
                    parent[i] = u;
                else if(findp(i) != findp(u))
                    parent[i] = i;
            }
        }
        
        for (int i = 2; i <= n; i++) {
            weight[findp(i)]++;
        }
        int ret = 0;
        for (int i = 2; i <= n; i++) {
            if (i == parent[i]) {
                ret += weight[i] * (n - 1 - weight[i]);
            }
        }
        printf("%d\n", ret/2 + n - 1);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12663 - High bridge, low bridge

Problem

給水位消長的情況，請問有有多少塊地經過溼乾的次數大於等於 K。

Sample Input

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

Sample Output

1
2
Case 1: 1
Case 2: 3

Solution

先對地面高度作一次排序，來確保每一次消長會將一個區間的所有元素都 +1。

用 binary index tree 維護區間調整，單點查詢。

  1. 假設對於 [l, r] 都加上 v，則對於前綴對 A[l] += v, A[r+1] -= v 這樣保證前綴和不影響其結果。
  2. 單點查詢 B[l] 元素的結果 = sum(A[1, l])
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
int A[131072], tree[131072];
void modify(int x, int N, int val) {
    while (x <= N) {
        tree[x] += val;
        x += x&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += tree[x];
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int cases = 0;
    int N, M, K, l = 0, r;
    while (scanf("%d %d %d", &N, &M, &K) == 3) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &A[i]);
        sort(A+1, A+1+N);
        memset(tree, 0, sizeof(tree));
        int p = 1;
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &r, &l);
            p = upper_bound(A+1, A+1+N, p) - A;
            r = upper_bound(A+1, A+1+N, r) - A;
            if (p <= r) {
                modify(p, N, 1);
                modify(r, N, -1);
            }
            p = l;
        }
        
        int ret = 0;
        for (int i = 1; i <= N; i++) {
            int cnt = query(i);
            ret += cnt >= K;
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
/*
 */
Read More +
解題區/解題區 - UVa

UVa 12655 - Trucks

Problem

給一張 N 個點的圖，問任意兩點之間的最大化最小邊。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
4 5 4
1 2 9
1 3 0
2 3 8
2 4 7
3 4 4
1 4
2 1
3 1
4 3
4 5 2
1 2 30
2 3 20
3 4 10
4 1 40
2 4 50
1 3
1 2

Sample Output

1
2
3
4
5
6
7
9
8
7
20
40

Solution

先將圖縮成最大生成樹，然後使用 tarjan 作離線的 LCA 詢問。

接著詢問在樹上進行即可，因此每次詢問最慘會到 O(n)。

那我們稍微加速，採用 dp 的方式，將樹變成有根樹，記錄每一個節點向上攀升 1 個節點, 2 個節點, 4 個節點 …, 2^n 個節點的路徑上的最大最小值。

因此狀態會是 O(n log n), 建表也能在 O(n log n) 完成，接著調整兩個詢問節點的高度，先想辦法調整到兩個節點到水平高度，藉由之前的計算，高度不超過 n，因此理應可以在 O(log n) 時間內完成到調整到同一水平高度。

這題跟 UVa 12176 - Bring Your Own Horse 相當相似。

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 <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
struct E {
    int x, y, v;
    E(int a=0, int b=0, int c=0):
    x(a), y(b), v(c) {}
    bool operator<(const E &a) const {
        return  v > a.v;
    }
};
E D[100005];
int visited[32767];
vector<E> tree[32767];
int parent[32767], weight[32767];
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;
}
int kruscal(int n, int m) {
    int sum = 0;
    
    sort(D, D+m);
    for(int i = 0; i <= n; i++) {
        parent[i] = i, weight[i] = 1;
        tree[i].clear();
    }
    
    for(int i = 0; i < m; i++) {
        if(joint(D[i].x, D[i].y)) {
        	sum += D[i].v;
        	tree[D[i].x].push_back(E(D[i].x, D[i].y, D[i].v));
        	tree[D[i].y].push_back(E(D[i].y, D[i].x, D[i].v));
        }
    }
    return sum;
}
int dp[32767][20], dpw[32767][20];
int treeLevel[32767], treePath[32767];
void dfs(int u, int p, int level) {
    treeLevel[u] = level, treePath[level] = u;
    for(int i = 1; (1<<i) < level; i++) {
        dp[u][i] = min(dp[u][i-1], dp[dpw[u][i-1]][i-1]);
        dpw[u][i] = treePath[level-(1<<i)];
    }
    for(int i = 0; i < tree[u].size(); i++) {
        int v = tree[u][i].y;
        if(v == p)	continue;
        dp[v][0] = tree[u][i].v;
        dpw[v][0] = u;
        dfs(v, u, level + 1);
    }
}
// LCA
vector< pair<int, int> > Q[32767];// query pair, input index - node
int LCA[131072];//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].y;
    	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 query(int x, int y, int lca) {
    int hx = treeLevel[x], hy = treeLevel[y], hlca = treeLevel[lca];
    int ret = 0x3f3f3f3f;
    for(int i = 16; i >= 0; i--) {
        if (hx-hlca >= (1<<i)) {
            ret = min(ret, dp[x][i]);
            x = dpw[x][i];
            hx -= (1<<i);
        }
        if (hy - hlca >= (1<<i)) {
            ret = min(ret, dp[y][i]);
            y = dpw[y][i];
            hy -= (1<<i);
        }
    }
    return ret;
}
int main() {
    //	freopen("in.txt", "r+t", stdin);
    //	freopen("out.txt", "w+t", stdout);
    int n, m, q, x, y;
    while(scanf("%d %d %d", &n, &m, &q) == 3) {
        
        for(int i = 0; i < m; i++) {
        	scanf("%d %d %d", &D[i].x, &D[i].y, &D[i].v);
        }
        
        kruscal(n, m);
        memset(dp, 0, sizeof(dp));
        memset(dpw, 0, sizeof(dpw));
        dfs(1, -1, 1);
        
        for (int i = 1; i <= n; i++)
            visited[i] = 0, Q[i].clear();
        
        vector< pair<int, int> > ask;
        for (int i = 0; i < q; i++) {
        	scanf("%d %d", &x, &y);
        	Q[x].push_back(make_pair(i, y));
        	Q[y].push_back(make_pair(i, x));
            ask.push_back(make_pair(x, y));
        }
        tarjan(1, -1);
        
        for (int i = 0; i < q; i++) {
//            printf("%d %d %d\n", ask[i].first, ask[i].second, LCA[i]);
            printf("%d\n", query(ask[i].first, ask[i].second, LCA[i]));
        }
    }
    return 0;
}
/*
 */
Read More +
解題區/解題區 - 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 +