解題區/解題區 - UVa

UVa 1368 - DNA Consensus String

Problem

給予一堆相同長度的 ATCG 構成的基因，找一段字典順序最小的基因，使得與給定的基因漢明碼距離(有多少位置不同)總和最小。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
3 
5 8 
TATGATAC 
TAAGCTAC 
AAAGATCC 
TGAGATAC 
TAAGATGT 
4 10 
ACGTACGTAC 
CCGTACGTAG 
GCGTACGTAT 
TCGTACGTAA 
6 10 
ATGTTACCAT 
AAGTTACGAT 
AACAAAGCAA 
AAGTTACCTT 
AAGTTACCAA 
TACTTACCAA

Sample Output

1
2
3
4
5
6
TAAGATAC 
7 
ACGTACGTAA 
6 
AAGTTACCAA 
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
#include <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    int n, m;
    char DNA[64][1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%s", DNA[i]);
        int hh = 0;
        char ret[1024] = {}, cc[] = "ACGT";
        for (int i = 0; i < m; i++) {
            int cnt[4] = {}, mx = 0;
            for (int j = 0; j < n; j++)
                cnt[find(cc, cc+4, DNA[j][i]) - cc]++;
            
            for (int j = 0; j < 4; j++) {
                if (cnt[j] > cnt[mx])
                    mx = j;
            }
            ret[i] = cc[mx], hh += n - cnt[mx];
                
        }
        printf("%s\n%d\n", ret, hh);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10712 - Count the Numbers

Problem

找一個數字 M 介於 [A, B] 之間，且中間的 substring 包含 N 的個數為何。

Sample Input

1
2
3
4
3 17 3
0 20 0
0 150 17
-1 -1 -1

Sample Output

1
2
3
2
3
2

Solution

建立一個 AC 自動機，使用傳統的 AC 自動機 dp，每一個節點當作一般 AC 自動機的走訪，並且猜測下一步的所有匹配符號。

為了要卡住上限，增加經過的狀態是否一直為前幾次臨界上限，若一直在上限，則搜索範圍將會被限制。

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
#include <stdio.h>
#include <vector>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;
struct Node {
    Node *next[10], *fail, *prev;
    int eos;//prefix has a string end
    long long dp[20][2]; // [string length][upper y/n]
    int ASCII;
    Node() {
        fail = NULL, prev = NULL;
        memset(next, 0, sizeof(next));
        memset(dp, 0, sizeof(dp));
        eos = 0;
        ASCII = 0;
    }
};
void insertTrie(const char str[], Node *root, int label) {
    static Node *p;
    static int i, idx, eos;
    p = root, eos = 0;
    for(i = 0; str[i]; i++) {
        idx = str[i] - '0';
        if(p->next[idx] == NULL) {
            p->next[idx] = new Node();
            p->next[idx]->prev = p;
            p->next[idx]->ASCII = idx;
        }
        eos |= p->eos;
        p = p->next[idx];
        p->eos |= eos;
    }
    p->eos |= label;
}
void freeTrie(Node *root) {
    queue<Node*> Q;
    Node *nd;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        }
        delete nd;
    }
}
void buildACautomation(Node *root) {
    queue<Node*> Q;
    Node *nd, *p;
    root->fail = NULL;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] == NULL)
                continue;
            Q.push(nd->next[i]);
            p = nd->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                nd->next[i]->fail = root;
            else {
                nd->next[i]->fail = p->next[i];
                nd->next[i]->eos |= p->next[i]->eos;//special for dp
            }
        }
    }
}
void clearDp(Node *root) {
    queue<Node*> Q;
    Node *nd;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        memset(nd->dp, 0, sizeof(nd->dp));
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        }
    }
}
long long dp(Node *root, int len, char pattern[]) {
    queue<Node*> Q;
    Node *nd, *p;
    clearDp(root);
    root->dp[0][1] = 1;
    int k, i, j;
    long long ret = 0;
    for(k = 0; k < len; k++) {
        Q.push(root);
        while(!Q.empty()) {
            nd = Q.front(), Q.pop();
            for (j = 0; j < 2; j++) {
                for (i = (k == 0); i <= (j ? pattern[k]-'0' : 9); i++) {
                    if(nd->next[i] != NULL) {
                        if(nd->next[i]->eos) { // matching
                        	if (j && i == pattern[k]-'0') {
                        		long long t = 0;
                        		for (int p = k + 1; p < len; p++)
                        			t = t * 10 + pattern[p] - '0';
                        		t++;
                        		ret += nd->dp[k][j] * t;
//	                    		printf("[%d %d] (%d + %d) %lld ++ %lld\n", k, j, nd->ASCII, i, nd->dp[k][j] * t, t);
                        	} else {
                        		long long t = 1;
                        		for (int p = k + 1; p < len; p++)
                        			t *= 10;	
                        		ret += nd->dp[k][j] * t;
//	                    		printf("[%d %d] (%d + %d) %d ++\n", k, j, nd->ASCII, i, nd->dp[k][j] * t);
                        	}
                        	continue;
                        } 
                        if (j == 0 || (j == 1 && i < pattern[k] - '0'))
                        	nd->next[i]->dp[k+1][0] += nd->dp[k][j];
                        else if(j == 1 && i == pattern[k] - '0')
                        	nd->next[i]->dp[k+1][1] += nd->dp[k][j];
                        if(j == 0)
                        	Q.push(nd->next[i]);
                    } else {
                        p = nd;
                        while(p != root && p->next[i] == NULL)
                            p = p->fail;
                        p = p->next[i];
                        if(p->eos) { // matching
                    		if (j && i == pattern[k]-'0') {
                        		long long t = 0;
                        		for (int p = k + 1; p < len; p++)
                        			t = t * 10 + pattern[p] - '0';
                        		t++;
                        		ret += nd->dp[k][j] * t;
                        	} else {
                        		long long t = 1;
                        		for (int p = k + 1; p < len; p++)
                        			t *= 10;
                        		ret += nd->dp[k][j] * t;
//	                    		printf("[%d %d] (%d + %d) %d ++\n", k, j, nd->ASCII, i, nd->dp[k][j] * t);
                        	}
                        	continue;
                        }
                        if (j == 0 || (j == 1 && i < pattern[k] - '0'))
                        	p->dp[k+1][0] += nd->dp[k][j];
                        else if(j == 1 && i == pattern[k] - '0')
                        	p->dp[k+1][1] += nd->dp[k][j];
                    }
                }
        	}
        }
    }
    return ret;
}
long long getDistinctNumberWith(int n, int m) { // #number <= n, has substring m
    if (n < 0) 
        return 0;
    char pattern[26], s[26];
    sprintf(pattern, "%d", m);
    Node *root = new Node();
    insertTrie(pattern, root, 1);
    for(int i = 0; i < 10; i++) {
    	s[0] = i + '0', s[1] = '\0';
    	insertTrie(s, root, 0);
    }
    buildACautomation(root);
    sprintf(pattern, "%d", n);
    long long ret = 0;
    int nlen = strlen(pattern);
    ret += dp(root, nlen, pattern);
    for	(int i = 1; i < nlen; i++) {
        pattern[i-1] = '9', pattern[i] = '\0';
//		printf ("%s %d %d --------\n", pattern, i, dp(root, i, pattern));
        ret += dp(root, i, pattern);
    }
    if (m == 0)	
        ret++;
    freeTrie(root);
    return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, a, b;
    while(scanf("%d %d %d", &a, &b, &n) == 3 && a >= 0) {
    	long long R, L;
        R = getDistinctNumberWith(b, n);
        L = getDistinctNumberWith(a - 1, n);
        printf("%lld\n", R - L);
    }
    return 0;
}
/*
731653830 735259500 735
735259500 735259500 735
3 17 3
0 20 0
0 150 17
-1 -1 -1
*/
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 +