解題區/解題區 - Zerojudge

b278. 说话不算话的区间求和

Problem

一个长度为n的数组a[1..n]，初始值为0,。要求你维护三种操作：

1 x v ：把数组的第x个元素改为v；(1≤x≤n,1≤v≤100,000,000)

2 x y ：询问数组元素a[x],a[x+1],…,a[y]之和；(1≤x≤y≤n)

0 k ：撤销最近的k次操作(注意，撤销操作本身也是操作，询问也算一次操作)。(1≤k≤当前操作次数)

Sample Input

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

Sample Output

1
2
3
1

Solution

現在學到了一種可持久化的數據精神，有一種為函數式線段樹，最簡單理解的就是採用修改不改值，而是增加新的節點，而每一次修改最多增加 O(n log n) (延著線段樹走訪路徑增加節點)

也就是說，每一次修改會根據前一次的 root 增加一個新的 root’，這是一個相當重要的一環，每一次修改會產生新的一棵線段樹，而這個新線段樹大部分節點會使用前一個線段樹的節點，因此只要針對走訪不影響的情況下，我們仍然會經過舊有的節點。

這一題最麻煩的是對於版本回溯，對於撤銷操作而言，撤銷操作可以撤銷 “撤銷操作”，因此會不斷地展開原本被撤銷的相關操作，然後又將部分操作撤銷 … 反反覆覆，後來發現只要根據當前的版本號減去要撤銷操作的總數即可返回，因此必須記錄每一次操作的線段樹結果。

套用函數式線段樹就相當簡單了！

感謝 liouzhou_101 的題意指導

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
#define MAXBUF 8388608
struct Node {
    int lson, rson;
    long long sum;
} node[MAXBUF + 50];
int nodesize = 0;
int root[524288];
int build(int l, int r) {
    if (l > r)  return 0;
    int k = nodesize++;
    node[k].sum = 0;
    node[k].lson = node[k].rson = 0;
    if (l == r) return k;
    int m = (l + r)/2;
    node[k].lson = build(l, m);
    node[k].rson = build(m+1, r);
    return k;
}
int change(int p, int l, int r, int x, int val) {
    int k = nodesize++;
    node[k] = node[p];
    if (l == r) {
        node[k].sum = val;
        return k;
    }
    int m = (l + r)/2;
    if (x <= m)
        node[k].lson = change(node[p].lson, l, m, x, val);
    else
        node[k].rson = change(node[p].rson, m+1, r, x, val);
    node[k].sum = node[node[k].lson].sum + node[node[k].rson].sum;
    return k;
}
long long query(int k, int l, int r, int x, int y) {
    if (x <= l && r <= y)
        return node[k].sum;
    int m = (l + r)/2;
    long long sum = 0;
    if (x <= m) {
        sum += query(node[k].lson, l, m, x, y);
    }
    if (y > m) {
        sum += query(node[k].rson, m+1, r, x, y);
    }
    return sum;
}
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        
        root[0] = build(1, n);
        
        int pre_ver = 0, cmd, x = 0, y = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d %d", &cmd, &x);
            if (cmd == 0) {
                y = 0;
                root[i] = root[i - x - 1];
                pre_ver = i;
            } else if (cmd == 1) {
                scanf("%d", &y);
                root[i] = change(root[pre_ver], 1, n, x, y);
                pre_ver = i;
            } else if (cmd == 2){
                scanf("%d", &y);
//                printf("query root = %d\n", root[pre_ver]);
                printf("%lld\n", query(root[pre_ver], 1, n, x, y));
                root[i] = root[pre_ver];
                pre_ver = i;
            }
            if (nodesize > MAXBUF) {
                return 0;
            }
        }
    }
    return 0;
}
/*
 2 5
 1 1 1
 1 2 2
 2 1 2
 0 2
 2 1 2
 */
Read More +
解題區/解題區 - Zerojudge

a331. K-th Number

Problem

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array a[1…n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: “What would be the k-th number in a[i…j] segment, if this segment was sorted?”
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2…5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

Sample Input

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

Sample Output

1
2
3
5
6
3

Solution

之前使用過塊狀鏈表、歸併樹來完成這一題，其中速度快 歸併樹 > 函數式線段樹 > 塊狀鏈表，空間消耗大小 函數式線段樹 > 歸併樹 > 塊狀鏈表。

現在學到了一種可持久化的數據精神，有一種為函數式線段樹，最簡單理解的就是採用修改不改值，而是增加新的節點，而每一次修改最多增加 O(n log n) (延著線段樹走訪路徑增加節點)

也就是說，每一次修改會根據前一次的 root 增加一個新的 root’，這是一個相當重要的一環，每一次修改會產生新的一棵線段樹，而這個新線段樹大部分節點會使用前一個線段樹的節點，因此只要針對走訪不影響的情況下，我們仍然會經過舊有的節點。

為了找到區間 K 大，使用函數式線段樹有點類似於掃描線算法，對於某個時間點依序將數字放進去，然後對於區間查詢 K 大的時候，相當於對某個時間點之間作減法運算。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
struct Node {
    int l, r, lson, rson;
    int sum;
} node[2097152];
int nodesize = 0;
int A[131072], B[131072], root[131072];
int build(int l, int r) {
    if (l > r)  return 0;
    int k = nodesize++;
    node[k].l = l, node[k].r = r, node[k].sum = 0;
    node[k].lson = node[k].rson = 0;
    if (l == r) return k;
    int m = (l + r)/2;
    node[k].lson = build(l, m);
    node[k].rson = build(m+1, r);
    return k;
}
int change(int p, int x, int val) {
    int k = nodesize++;
    node[k] = node[p];
    node[k].sum += val;
    if (node[k].l == node[k].r) return k;
    int m = (node[k].l + node[k].r)/2;
    if (x <= m)
        node[k].lson = change(node[p].lson, x, val);
    else
        node[k].rson = change(node[p].rson, x, val);
    return k;
}
int query(int tp, int tq, int k) {
    if (node[tp].l == node[tp].r)
        return node[tp].l;
    int t = node[node[tp].lson].sum - node[node[tq].lson].sum;
    if (k <= t)
        return query(node[tp].lson, node[tq].lson, k);
    else
        return query(node[tp].rson, node[tq].rson, k - t);
}
int main() {
    int n, m, x, y, k;
    while (scanf("%d %d", &n, &m) == 2) {
        map<int, int> R;
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]), R[A[i]] = 0;
        
        int size = 0;
        for (map<int, int>::iterator it = R.begin(); it != R.end(); it++) {
            it->second = ++size;
            B[it->second] = it->first;        
        }
        
        nodesize = 1;
        root[0] = build(1, size);
        
        for (int i = 1; i <= n; i++) {
            A[i] = R[A[i]];
            root[i] = change(root[i-1], A[i], 1);
        }
        
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &k);
            printf("%d\n", B[query(root[y], root[x-1], k)]);
        }
    }
    return 0;
}
/*
 7 3
 1 5 2 6 3 7 4
 2 5 3
 4 4 1
 1 7 3
 */
Read More +
解題區/解題區 - UVa

UVa 12730 - Skyrk's Bar

Problem

紳士們上小便的時候，彼此之間會隔著 K 個小便斗 (空著人的小便斗)，請問當有 N 個一排的小便斗，請問壅塞個數的期望值為何 (一次平均可以多少人上小便)。

Sample Input

1
2
3
4
3
4 2
7 2
10 3

Sample Output

1
2
3
Case #1: 1.5000
Case #2: 2.2857
Case #3: 2.4133

Solution

狀態紀錄 dp[i] 表示 i 個一排的小便斗的壅塞期望值。

現在考慮最後一個進入的人所佔的位置 p，則期望值會等於 1 + dp[p-K-1] + dp[i-(p+K)]，分別為左側和右側的期望值，儘管左右兩側狀態也會對邊界有空隙 <= K，但是放入之後與 p 之間空隙最 <= 2K，也塞不下其他人 (至少要 2K + 1)。

由於最後一個人的情況有 i 種，每一種的機率都相同，因此推導結果為 dp[i] = 1 + (dp[1] + dp[2] + ... + dp[i-k-1])/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
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
double dp[1048576], sum[1048576];
int main() {
    int testcase, cases = 0;
    int n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            if (i <= m) {
                dp[i] = 1;
            } else {
                dp[i] = 1 + sum[i - m - 1] * 2.0 / i;
            }
            sum[i] = sum[i - 1] + dp[i];
        }
        printf("Case #%d: %.4lf\n", ++cases, dp[n]);
    }
    return 0;
}
/*
 3
 4 2
 7 2
 10 3
 */
Read More +
解題區/解題區 - UVa

UVa 12707 - Block Meh

Problem

給 N 個區間 [l, r]，每一次挑選一個區間 [a0, b0]，接著可以找到另外一個區間 [ai, bi] 被 [a0, b0] 完全覆蓋 (a0 < ai < bi < b0)，接著再對這個區間 [ai, bi] 再找一個被完全覆蓋的區間 [ai+1, bi+1] 如此迭代下去，當作一次操作。

請問至少要幾次，才能將所有區間挑選完。

Sample Input

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

Sample Output

1
2
Case 1: 3
Case 2: 2

Solution

對右端點進行遞增排序，對左端點進行次遞增排序，接著進行掃描算法，每一次放入的區間盡可能被之前的區間包含住，否則將會增加一次操作，也就是說要找盡可能接近的左端點來符合放入的區間。

這個操作方式，非常接近 O(n log n) LIS 的思路。

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 <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.second != b.second)
        return a.second < b.second;
    return a.first < b.first;
}
#define INF 0x3f3f3f3f
int main() {
    int testcase, cases = 0;
    int n, s, e;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        vector< pair<int, int> > D;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &s, &e);
            D.push_back(make_pair(s, e));
        }
        sort(D.begin(), D.end(), cmp);
        vector<int> leftside;
        for (int i = 0; i < D.size(); i++) {
            int pos = (int)(lower_bound(leftside.begin(), leftside.end(), D[i].first + 1)
                            - leftside.begin());
            if (pos == leftside.size()) {
                leftside.push_back(D[i].first);
            } else {
                leftside[pos] = D[i].first;
            }
        }
        printf("Case %d: %d\n", ++cases, (int)leftside.size());
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12701 - The Twin Head Dragon

Problem

給一棵樹，每次覆蓋不重疊的路徑，將路徑上的權重平均得到此次花費，目標覆蓋所有的邊，加總花費最小化。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
4
0 2 1
1 2 2
2 3 3
6
0 1 10000
0 2 10000
0 3 1
0 4 1
0 5 10000
0

Sample Output

1
2
3.5000
15001.5000

Solution

對於每一種狀態作紀錄，然後對於尚未使用過的邊作 bitmask，每次移除一條路徑上的結果。

// 後來發現似乎可以直接轉成有根樹，進行樹形 dp，真是失策。

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
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
struct Edge {
    int to, w, i;
    Edge(int a = 0, int b = 0, int c = 0):
        to(a), w(b), i(c) {}
};
vector<Edge> g[16];
int n, used[1<<16];
double dp[1<<16];
double dfs(int);
void dfs2(int u, int mask, int w, int e, int o) {
    if (e) {
        dp[o] = min(dp[o], dfs(mask) + (double)w/e);
    }
    for (int i = 0; i < g[u].size(); i++) {
        if ((mask>>g[u][i].i)&1) {
            int v = g[u][i].to;
            dfs2(v, mask^(1<<g[u][i].i), w + g[u][i].w, e+1, o);
        }
    }
}
double dfs(int mask) {
    if (mask == 0)  return 0;
    if (used[mask]) return dp[mask];
    used[mask] = 1;
    double &ret = dp[mask];
    ret = 1e+30;
    for (int i = 0; i < n; i++) {
        dfs2(i, mask, 0, 0, mask);
    }
    return ret;
}
int main() {
    int x, y, w;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        for (int i = 0; i < n - 1; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(Edge(y, w, i));
            g[y].push_back(Edge(x, w, i));
        }
        memset(used, 0, sizeof(used));
        printf("%.4lf\n", dfs((1<<(n-1)) - 1));
    }
    return 0;
}
/*
 4
 0 2 1
 1 2 2
 2 3 3
 6
 0 1 10000
 0 2 10000
 0 3 1
 0 4 1
 0 5 10000
 0 */
Read More +
解題區/解題區 - UVa

UVa 12674 - Go up the ultras

Problem

一個山峰高度 h[i] 如果算是突起，則必須符合

  • 到其他更高的山峰之間有經過低於 h[i] - 150000 的可能
  • 如果本身就是最高峰，則高度至少要 150000

Sample Input

1
2
3
4
5
0 10000 100000 884813 0
7
0 100000 0 200000 180000 200000 0

Sample Output

1
2
4
4 6

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#include <stack>
using namespace std;
int n;
int h[1048576], a[1048576];
int main() {
    while(scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            scanf("%d", &h[i]), a[i] = h[i];
        
        stack< pair<int, int> > stk;
        for (int i = 0; i < n; i++) {
            if (!stk.empty()) {
                stk.top().second = min(stk.top().second, h[i]);
            }
            while (!stk.empty() && stk.top().first <= h[i]) {
                pair<int, int> p = stk.top();
                stk.pop();
                if (!stk.empty())
                    stk.top().second = min(stk.top().second, p.second);
            }
            if (!stk.empty()) {
                a[i] = min(a[i], h[i] - stk.top().second);
            }
            stk.push(make_pair(h[i], h[i]));
        }
        
        while (!stk.empty())
            stk.pop();
            
        for (int i = n - 1; i >= 0; i--) {
            if (!stk.empty()) {
                stk.top().second = min(stk.top().second, h[i]);
            }
            while (!stk.empty() && stk.top().first <= h[i]) {
                pair<int, int> p = stk.top();
                stk.pop();
                if (!stk.empty())
                    stk.top().second = min(stk.top().second, p.second);
            }
            if (!stk.empty()) {
                a[i] = min(a[i], h[i] - stk.top().second);
            }
            stk.push(make_pair(h[i], h[i]));
        }
        
        int f = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] >= 150000) {
                if (f++) printf(" ");
                printf("%d", i + 1);
            }
        }
        puts("");
    }
    return 0;
}
/*
 5
 0 10000 100000 884813 0
 7
 0 100000 0 200000 180000 200000 0
 */
Read More +
解題區/解題區 - 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 +