解題區/解題區 - UVa

UVa 10486 - Mountain Village

Problem

給定一個 n x m 的網格，現在要紮營於格子上，但是每一格的高度不同，希望使用 k 個格子，他們可以藉由上下左右四格相連，找一種方案，使得最低、最高紮營高度差最小。

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
5 10
0 0 3 46 0 46 0 0 12 12
0 0 13 50 49 46 11 10 10 11
0 51 51 49 99 99 89 0 0 10
0 0 48 82 70 99 0 52 13 14
51 50 50 51 70 35 70 10 14 11
6
1
5
10
12
47
50

Output

1
2
3
4
5
6
0
0
3
4
89
99

Solution

由於高度介於 0 到 100 之間，考慮窮舉最低紮營處的高度 l。採用掃描線的方式，依序加入高度較低的地點，直到其中一個連通子圖的節點總數大於等於 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
85
86
87
88
89
90
91
92
#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 64;
int A[MAXN][MAXN];
vector< pair<int, int> > g[128];
int parent[MAXN*MAXN], weight[MAXN*MAXN];
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;
}
void init(int n)  {
    for (int i = 0; i <= n; i++)
        parent[i] = i, weight[i] = 1;
}
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int query(int n, int m, int need) {
    int x, y, tx, ty;
    int ret = 0x3f3f3f3f;
    for (int i = 0; i < 100; i++) { // lower
        init(n * m);
        
        int ok = 0;
        for (int j = i; j < 100 && !ok; j++) { // upper
            if (j - i >= ret)
                break;
            for (int k = 0; k < g[j].size() && !ok; k++) {
                x = g[j][k].first, y = g[j][k].second;
                for (int d = 0; d < 4; d++) {
                    tx = x + dx[d], ty = y + dy[d];
                    if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                        continue;
                    if (A[tx][ty] <= j && A[tx][ty] >= i) {
                        joint(x * m + y, tx * m + ty);
                        if (weight[findp(x * m + y)] >= need)
                            ok = 1, ret = min(ret, j - i);
                    }
                }
            }
        }
        
    }
    return ret;
}
int main() {
    int n, m, q, x;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < 100; i++)
            g[i].clear();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &A[i][j]);
                g[A[i][j]].push_back(make_pair(i, j));
            }
        }
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            scanf("%d", &x);
            printf("%d\n", query(n, m, x));
        }
    }
    return 0;
}
/*
5 10
0 0 3 46 0 46 0 0 12 12
0 0 13 50 49 46 11 10 10 11
0 51 51 49 99 99 89 0 0 10
0 0 48 82 70 99 0 52 13 14
51 50 50 51 70 35 70 10 14 11
6
1
5
10
12
47
50
*/
Read More +
解題區/解題區 - UVa

UVa 10463 - Aztec Knights

Problem

給定一種特殊的騎士走法，請問在 n x m 格子上，從 (x, y) 到 (a, b) 的步數情況，走訪時不能重複經過相同點。

若能恰好在質數步抵達，輸出最少的步數。如不是質數，輸出合數的最少步數。都還是不行則輸出無法抵達。

Input

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

Output

1
2
3
CASE# 1: Destination is not reachable.
CASE# 2: The knight takes 2 prime moves.
CASE# 3: The knight takes 0 composite move(s).

Solution

這題麻煩的地方在於恰好在質數抵達，那麼考慮使用 IDA 來完成，在搜索時發生不是在質數步數抵達回傳無解，繼續迭代加深。估價函數為當前座標 (x, y) 到 (a, b) 的最短距離。

在做 IDA 之前，使用 Bfs 查看移動所需步數，若恰好是質數則直接輸出答案，若保證無法抵達終點，輸出無解。最後再進行 IDA 搜索，來加快處理程序。

根據測試，使用的質數步數不大於 11。

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
// IDA, Bfs
#include <stdio.h> 
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int dx[] = {1, 1, -1, -1, 3, 3, -3, -3};
const int dy[] = {3, -3, 3, -3, 1, -1, 1, -1};
const int px[] = {1, 1, -1, -1, 1, 1, -1, -1};
const int py[] = {1, -1, 1, -1, 1, -1, 1, -1};
int hdist[16][16][16][16];
vector< pair<int, int> > g[16][16];
int move(int n, int m, int x, int y, int kind, int &rx, int &ry) {
    int tx, ty;
    tx = x + dx[kind], ty = y + dy[kind];
    if (tx < 0 || ty < 0 || tx >= n || ty >= m)
        return 0;
    rx = tx, ry = ty;
    tx = x, ty = y;
//	for (int i = 0; i < 2; i++) {
//		tx = tx + px[kind], ty = ty + py[kind];
//		if (tx < 0 || ty < 0 || tx >= n || ty >= m)
//			return 0;
//	}
    return 1;
}
void moveBfs(int n, int m, int sx, int sy) {
    int x, y, tx, ty;
    int dist[16][16] = {};
    const int INF = 0x3f3f3f3f;
    queue<int> X, Y;
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            dist[i][j] = INF;
            
    X.push(sx), Y.push(sy), dist[sx][sy] = 0;
    while (!X.empty()) {
        x = X.front(), y = Y.front();
        X.pop(), Y.pop();
        for (int i = 0; i < 8; i++) {
            if (move(n, m, x, y, i, tx, ty)) {
                if (dist[tx][ty] > dist[x][y] + 1) {
                    dist[tx][ty] = dist[x][y] + 1;
                    X.push(tx), Y.push(ty);
                }
            }
        }
    }
    
    // record sssp
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            hdist[sx][sy][i][j] = dist[i][j];
        }
    }
}
#define MAXL (100>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXL];
int P[5500], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 100;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for (k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
// IDA
int ida_depth, solved;
int used[16][16];
int IDA(int x, int y, int ex, int ey, int dep, int hv) {
    if (hv == 0) {
        if (!GET(dep)) {
        	solved = 1;
        	return dep;
        }
        return 0x3f3f3f3f;
        return dep;
    }
    if (dep + hv > ida_depth)
        return dep + hv;
    int back = 0x3f3f3f3f, shv, tmp;
    for (int i = 0; i < g[x][y].size(); i++) {
    	int tx = g[x][y][i].first, ty = g[x][y][i].second;
        shv = hdist[tx][ty][ex][ey];
        
        if (used[tx][ty])
        	continue;
        	
        used[tx][ty] = 1;
        tmp = IDA(tx, ty, ex, ey, dep + 1, shv);
        used[tx][ty] = 0;
        
        back = min(back, tmp);
        if (solved) return back;
    }
    return back;
}
int main() {
    sieve();
    int n, m, sx, sy, ex, ey;
    int cases = 0;
    while (scanf("%d %d %d %d %d %d", &n, &m, &sx, &sy, &ex, &ey) == 6) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                moveBfs(n, m, i, j);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j].clear();
                for (int k = 0; k < 8; k++) {
                    int tx, ty;
                    if (move(n, m, i, j, k, tx, ty))
                        g[i][j].push_back(make_pair(tx, ty));
                }
            }
        }
        
//		printf("Bfs %d\n", hdist[sx][sy][ex][ey]);
//		for (int i = 0; i < n; i++, puts(""))
//			for (int j = 0; j < m; j++)
//				printf("%d ", hdist[sx][sy][i][j] == 0x3f3f3f3f ? -1 : hdist[sx][sy][i][j]);
        
        printf("CASE# %d: ", ++cases);
        
        if (hdist[sx][sy][ex][ey] > 1 && hdist[sx][sy][ex][ey] < 100 && !GET(hdist[sx][sy][ex][ey])) {
            printf("The knight takes %d prime moves.\n", hdist[sx][sy][ex][ey]);
            continue;
        }
                
        solved = 0;
        if (hdist[sx][sy][ex][ey] != 0x3f3f3f3f && (sx != ex || sy != ey)) {
            memset(used, 0, sizeof(used)); 
            
            used[sx][sy] = 1;
            ida_depth = 0;
            for (int i = 0; i < Pt && P[i] < 11; i++) {
                if (P[i] < ida_depth)
                    continue;
                ida_depth = P[i];
                ida_depth = IDA(sx, sy, ex, ey, 0, hdist[sx][sy][ex][ey]);
                
                if (solved) {
                    printf("The knight takes %d prime moves.\n", P[i]);
                    break;
                }
            }
        }
        if (!solved) {
            if (hdist[sx][sy][ex][ey] == 0x3f3f3f3f)
                printf("Destination is not reachable.\n");
            else
                printf("The knight takes %d composite move(s).\n", hdist[sx][sy][ex][ey]);
        }
    }
    return 0;
} 
/*
5 7 2 2 3 1
5 5 0 0 3 4
5 5 0 0 4 4
5 5 0 0 0 0
8 4 4 0 3 2
4 8 1 1 3 5
5 7 2 2 3 1
7 8 0 7 0 5
7 5 1 4 0 4
5 6 1 4 0 2
6 4 0 2 0 1
8 8 1 0 2 7
8 5 0 1 6 1
7 8 1 5 1 4
*/
Read More +
解題區/解題區 - UVa

UVa 10454 - Trexpression

Problem

給一個只有加法、乘法和括弧的運算式，在不改變最後的答案下，有多少種不同的運算順序 (不同的 parse tree)。

Input

1
2
3
4
1+2+3+4
(1+2)+(3+4)
1+2+3*4
1+2+(3*4)

Output

1
2
3
4
5
1
2
2

Solution

類似矩陣鏈乘積的 O(n^3) 解法。

dp[l, r] 表示表達式 exp[l, r] 正確的方法數。當運算式存在加法時，不能拆分乘法運算。只剩下乘法運算時，才能拆分乘法運算。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 256;
long long dp[MAXN][MAXN];
char s[MAXN];
long long dfs(int l, int r) {
    if (l == r)			return 1;
    if (dp[l][r] != -1)	return dp[l][r];
    long long &ret = dp[l][r];
    ret = 0;
    int left = 0, o1 = 0, o2 = 0;
    for (int i = l; i <= r; i++) {
        if (s[i] == '(')
            left++;
        else if (s[i] == ')')
            left--;
        else {
            if (left == 0) {
                if (s[i] == '+')	
                    o1 = 1;
                if (s[i] == '*')
                    o2 = 1;
            }				
        }
    }
    if (o1 == 0 && o2 == 0)
        ret += dfs(l+1, r-1);
    for (int i = l; i <= r; i++) {
        if (s[i] == '(')
            left++;
        else if (s[i] == ')')
            left--;
        else {
            if (left == 0) {
                if (s[i] == '+')
                    ret += dfs(l, i-1) * dfs(i+1, r);
                if (s[i] == '*' && o1 == 0)
                    ret += dfs(l, i-1) * dfs(i+1, r);
            }				
        }
    }
    return ret;
}
int main() {
    while (gets(s)) {
        memset(dp, -1, sizeof(dp));
        long long v = dfs(0, strlen(s) - 1);
        printf("%lld\n", v);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10413 - Crazy Savages

Problem

瘋狂的島嶼上有 n 個野蠻人、m 個山洞，山洞呈現環狀分佈。

每個野蠻人一開始各自在自己的洞窟 Ci，每隔一天就會移動到下 Pi 個山洞，在島上待 Li 天後就會死亡。

兩個野蠻人若剛好移動到相同洞窟，則會發生爭吵，請問至少要幾個洞窟，才能不發生爭吵。

Input

1
2
3
4
5
6
7
8
9
10
11
2
3
1 3 4
2 7 3
3 2 1
5
1 2 14
4 4 6
8 5 9
11 8 13
16 9 10

Output

1
2
6
33

Solution

窮舉洞窟數量 m，檢查是否存在爭吵。

檢查任兩個野蠻人 i, j 是否會在生存時間內相遇，假設會在第 k 天相遇，滿足公式

1
2
ci + k * pi = a * m  --- (1)
cj + k * pj = b * m  --- (2)

將公式整理後

1
2
3
(2)-(1) 	=> (ci - cj) + k * (pi - pj) = m * (a - b)
            => (a - b) * m + k * (pj - pi) = ci - cj
check k in [0, min(L[i], L[j])] has a

檢查 k 最小為多少，使得等式解存在。

套用擴充歐幾里德算法，得到 ax + by = gcd(x, y) 的第一組解 (a, b)，其 a, b 的參數式為

1
2
3
4
5
g = gcd(x, y)
a = a + lcm(x, y)/x * k
b = b + lcm(x, y)/y * k
=> a = a + y / g * k
=> b = b + x / g * k

最小化 a 參數，滿足 a >= 0，隨後檢查可行解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h> 
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN = 32;
const int INF = 0x3f3f3f3f;
int C[MAXN], P[MAXN], L[MAXN];
// a x + by = g
void exgcd(int x, int y, int &g, int &a, int &b) {
    if (y == 0)
        g = x, a = 1, b = 0;
    else
        exgcd(y, x%y, g, b, a), b -= (x/y) * a;
}
int hasCollision(int m, int n) {
    // assume m caves arranged in a circle
    // ci + k * pi = a * m  --- (1)
    // cj + k * pj = b * m  --- (2)
    // (2)-(1) 	=> (ci - cj) + k * (pi - pj) = m * (a - b)
    //			=> (a - b) * m + k * (pj - pi) = ci - cj
    // check k in [0, min(L[i], L[j])] has a solution.
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            int x = P[j] - P[i], y = m, z = C[i] - C[j];
            int a, b, g;
            int limitR = min(L[i], L[j]), limitL = 0;
            exgcd(x, y, g, a, b);
        
            if (z%g)	continue;
            a = a * (z / g);
            // ax + by = z
            // a = a + lcm(x, y)/x * k, b = b + lcm(x, y)/y * k
            // a = a + y / g * k, b = b + x / g * k
            // minmum a, a >= 0
            if (g < 0)	g = -g;
            a = (a%(y/g) + y/g) % (y/g);
            if (a <= limitR)
                return true;
        }
    }
    return false;
}
int main() {
    int testcase, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int m = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d", &C[i], &P[i], &L[i]);
            m = max(m, C[i]);
        }
            
        int ret = -1;
        for (int i = m; i < 99999999; i++) {
            
            if (!hasCollision(i, n)) {
                ret = i;
                break;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
2
3
1 3 4
2 7 3
3 2 1
5
1 2 14
4 4 6
8 5 9
11 8 13
16 9 10
*/
Read More +
解題區/解題區 - UVa

UVa 10412 - Big Big Trees

Problem

有隻猴子在樹間，每一棵樹有平行的分支，猴子可以在兩棵樹的分支端點跳躍，並且跳躍距離不超過歐幾里德距離 K，並且跳躍的時候只能跳端點的直線上，同時不能撞到其他分支，否則視如跳躍失敗。

猴子從樹幹走到分支端點、端點走到樹幹是需要計算步行花費，請問從第一棵樹走到最後一棵樹，最少的步行花費為何。

Input

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

Output

1
2
5
28

Solution

分支數量很少，直接暴力嘗試跳躍的可行性。使用外積解決線段交問題，隨後計算跳躍的最少花費，記錄狀態 dp[i] 表示從第一棵樹走到第 i 棵樹的最少步行成本。

特別小心當跳躍都無法時，可以走在地面上，由於這一點掛了好多 WA。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <string.h>
#include <assert.h>
#include <vector>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    double length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
//		angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if (as == at && bs == bt)
        return as == bs;
    if (as == at)
        return onSeg(bs, bt, as);
    if (bs == bt)
        return onSeg(as, at, bs);
    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;
}
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
const int MAXN = 1024;
int HN[MAXN], H[MAXN][32];
int main() {
    int testcase, N, M, K;
    
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &M, &K);
        for (int i = 0; i < N; i++) {
            scanf("%d", &HN[i]);
            for (int j = 0; j < HN[i]; j++)
                scanf("%d", &H[i][j]);
        }
        int dp[MAXN];
        
        memset(dp, 63, sizeof(dp));
        dp[0] = 0;
        
        for (int i = 0; i+1 < N; i++) {
//			printf("%d\n", dp[i]);
            for (int j = 0; j < HN[i]; j++) {
                for (int k = 0; k < HN[i+1]; k++) {
                    int dx, dy;
                    dx = M - H[i][j] - H[i+1][k];
                    dy = abs(j - k);
                    if (dx * dx + dy * dy > K * K)
                        continue;	
//					printf("%d %d, %d %d\n", j, k, dx, dy);
                    int ok = 1;
                    for (int p = 0; p < HN[i]; p++) {
                        if (p == j)	continue;
                        if (intersection(Pt(H[i][j], j), Pt(M-H[i+1][k], k), Pt(0, p), Pt(H[i][p], p)))
                            ok = 0;
                    }
                    for (int p = 0; p < HN[i+1]; p++) {
                        if (p == k)	continue;
                        if (intersection(Pt(H[i][j], j), Pt(M-H[i+1][k], k), Pt(M, p), Pt(M-H[i+1][p], p)))
                            ok = 0;
                    }
                    if (ok) {
//						printf("--- %d %d %d\n", j, k, H[i][j], H[i+1][k]);
                        dp[i+1] = min(dp[i+1], dp[i] + H[i][j] + H[i+1][k]);
                    }
                }	
            }
            dp[i+1] = min(dp[i+1], dp[i] + M); // WTF !!!!!!!!!!!!!!! 
        }
        
        printf("%d\n", dp[N-1]);
    }
    return 0;
}
/*
1
5 10 12
1 2
3 2 1 4
8 2 4 4 1 4 0 0 0
8 1 1 2 0 4 1 3 3
10 1 4 0 1 1 1 1 2 1 4
999
5 10 3
2 0 2
1 1
10 1 2 0 1 2 2 0 4 4 4
9 3 1 2 1 2 1 4 1 3
8 0 1 2 1 3 1 0 0
2
2 7 3
4 3 2 2 0
5 3 0 1 0 0
3 50 40
4 15 3 16 10
8 12 12 12 21 12 15 6 14
13 15 23 20 18 14 1 21 9 9 18 23 10 4
999
3 5 100
3 0 0 1
2 0 0
3 0 0 1
2 7 5
1 3
4 3 3 2 1
2 10 2
1 4
2 0 4
2 10 4
1 4
2 0 4
2 10 2
2 0 4
2 0 4
*/
Read More +
解題區/解題區 - UVa

UVa 10351 - Cutting Diamonds

Problem

給一個橢球的三個參數，一刀縱切橢球，問切割橢球的截面積為何。

Input

1
2
7 6 4 8 6 4
4 8 8 8 8 8

Output

1
2
3
4
Set #1
8.246681
Set #2
50.265482

Solution

回顧積分公式，得到橢圓面積。將橢球固定一個參數，調整計算截面積。公式如代碼中所附。

$$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1 \\ \text{area } = ab\pi \\ \frac{x^2}{a^2} + \frac{y^2}{b^2} + \frac{z^2}{c^2} = 1 \\ \frac{x^2}{(a \sqrt{1 - z^2 / c^2})^2} + \frac{y^2}{(b \sqrt{1 - z^2 / c^2})^2} = 1 \\ \text{cross-sectional area} = ab (1 - z^2 / c^2) \pi \\$$ 
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
#include <stdio.h> 
#include <math.h>
using namespace std;
/*
    x^2 / a^2 + y^2 / b^2 = 1 
        area = ab pi
    
    x^2 / a^2 + y^2 / b^2 + z^2 / c^2 = 1
    
    x^2 / (a \sqrt{1 - z^2 / c^2})^2 + y^2 / (b \sqrt{1 - z^2 / c^2})^2 = 1;
    cross-sectional area = ab (1 - z^2 / c^2) pi
    
    volume 	ab (1 - z^2 / c^2) pi dz
            ab pi (z - z^3 / 3 / c^2), for z in [l, r]
*/
const double pi = acos(-1);
int main() {
    int a, b, c, ra, rb, rc;
    int cases = 0;
    while (scanf("%d %d %d %d %d %d", &ra, &rb, &rc, &a, &b, &c) == 6) {
        printf("Set #%d\n", ++cases);
        double ta, tb, tc, l, r;
        if (ra > a || rb > b || rc > c) {
            printf("%.6lf\n", 0.0); // WTF
            continue;
        }
        if (ra < a) {
            ta = b/2.0, tb = c/2.0, tc = a/2.0;
            r = a/2.0, l = r - fabs(a - ra);
        } else if (rb < b) {
            ta = a/2.0, tb = c/2.0, tc = b/2.0;
            r = b/2.0, l = r - fabs(b - rb);
        } else if (rc < c) {
            ta = a/2.0, tb = b/2.0, tc = c/2.0;
            r = c/2.0, l = r - fabs(c - rc);
        } else {
            printf("%.6lf\n", 0.0); // WTF
            continue;
        }
        double area;
        area = ta * tb * pi * (1 - l*l/tc/tc);
        printf("%.6lf\n", area);
    }
    return 0;
}
/*
7 6 4 8 6 4
4 8 8 8 8 8
2 6 4 8 6 4
8 6 4 8 6 4
*/
Read More +
解題區/解題區 - UVa

UVa 10280 - Old Wine Into New Bottles

Problem

給予 n 種酒瓶，每一種酒瓶有其裝酒的容積上下限 [min, max] 毫升，請問將 m 公升的酒裝入酒瓶，最後剩餘的最少量為多少。

每一種酒瓶可以無限使用。

Input

1
2
3
4
5
6
7
8
9
2
10 2
4450 4500
725 750
10000 2
4450 4500
725 750

Output

1
2
3
250
0

Solution

這一題需要剪枝，無法單純地運行背包 dp，單純的背包 dp 很容易造成 TLE。

發現到只考慮使用一種酒瓶，那麼當酒量大於某個定值後，保證都能裝完。假設使用單一酒瓶的數量為 k 個以上時，能裝出所有量，則能覆蓋的區間為

1
[min, max], ..., [k*min, k*max], [(k+1)*min, (k+1)*max]

當第 k+1 個區間的左端點小於第 k 個區間的右端點時，可以得到接下來的所有區間都會發生重疊。推導得到 (k+1)*min >= k*max 最後條件 k >= min / (max - min)。

滿足保證能裝出，直接輸出答案 0，否則做背包 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
73
74
75
76
77
#include <stdio.h> 
#include <algorithm>
#include <string.h>
using namespace std;
#define MAXL (1000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXL];
/*
    k bottles
    [min, max], ..., [k*min, k*max], [(k+1)*min, (k+1)*max]
    
    always have solution for [k*min, k*max], [(k+1)*min, (k+1)*max] 
    sat. (k+1)*min >= k*max 
            k >= min / (max - min)
    all interval cover each other after k-bottles.
*/
const int MAXN = 128;
int mx[MAXN], mn[MAXN];
int main() {
    int testcase, L, N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &L, &N);
        L *= 1000;
        
        int lower_full = 0x3f3f3f3f; 
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &mn[i], &mx[i]);
            lower_full = min(lower_full, mn[i] * mn[i] / (mx[i] - mn[i]));
        }
        
        if (L >= lower_full) {
            puts("0");
            if (testcase)
                puts("");
            continue;
        }
        
        // limit L <= 4500 * 4500 / (4500 * 0.01)
        int A[4505] = {}, ret = 0;
        
        for (int i = 0; i < N; i++)
            for (int j = mn[i]; j <= mx[i]; j++)
                A[j] = 1;
            
        memset(mark, 0, sizeof(mark)); 
        SET(0);
        for (int i = 1; i <= 4500; i++) {
            if (A[i] == 0)
                continue;
            for (int j = i, k = 0; j <= L; j++, k++) {
                if (GET(k))
                    SET(j), ret = max(ret, j);
            }
        }
        
        printf("%d\n", L - ret);
        if (testcase)
            puts("");
    }
    return 0;
}
/*
2
10 2
4450 4500
725 750
10000 2
4450 4500
725 750
*/
Read More +
解題區/解題區 - 其他題目

2015 Google Code Jam Round 1B

windows format to linux format 

1
$ awk '{ sub("\r$", ""); print }' out.txt > output.txt

題解

  • A. Counter Culture
  • B. Noisy Neighbors
  • C. Hiking Deer

［A. Counter Culture］

給定一個數字 N，要求藉由兩種操作從 1 變成 N，第一種操作將當前數字 x 變成 x + 1，第二種操作為 x 變成 reverse(x)，並且消除前導為零。求操作的最少次數。

由於 N 很大，搜索沒有搞頭，但關於反轉數字能理解到，當後半部恰好等於目標的前半部時，此時反轉最有利，根據貪心策略進行反轉操作，但要防止前導為 0。關於 x + 1 部分，主要是增加位數。

這時候來逆推吧！降位數 (1000 -> 999, 10000 -> 9999)、反轉貪心 (123654 -> 100321)、WTF 的情況 (19 -> 11 -> 10)。在 WTF 的情況中，反轉無效，怒降一個數字。

［B. Noisy Neighbors］

在 R x C 的網格上，每一格可以租給一個用戶，當用戶之間共享一個邊時，將會增加不滿意程度，求租給 K 名用戶，建築的不滿意程度最低為何。

考慮 K 小的時候，將網格黑白染色，必然只放置在黑色或白色網格上，此時不滿意程度皆為 0。當 K 多餘白色格子或黑色格子時，將會增加不滿意程度，每當增加一格，勢必會挑選相對的顏色 (填滿白色格子後，選黑色格子來填)，那麼每一次必須挑最少相鄰邊的格子。

為什麼一定會填滿其中一種顏色？假設最優解存在其中一種顏色未填滿，且存在這一格 x 附近沒有使用的格子，那麼必然存在將一個產生不滿意的格子移動到 x 會是一個更優解。不斷地迭代下去，就是貪心的來源！

［C. Hiking Deer］

跟蹤狂 H 在一個圓從 0 出發繞一圈，H 很討厭人群，因此盡可能不與其他人碰面，H 的能力可以跟蹤在任何人身後。現在知道一群人會不斷地繞著這個圓，並且分別以各自的速度、當前位置，全部人都按著順時針方式繞行，不存在兩個人在相同地點以相同速度。現在從 time = 0 開始，請問 H 至少會發生幾次碰面。

由於是一個環狀，又要考慮繞行的區間最少人數，朝著掃描線思路邁進！保證答案 (碰面次數) 不超過總人數 N，一開始瞬間移動到最快抵達終點的人身上，只會碰到 N - 1 個人！

根據抵達終點的時間排序，維護當前需要的碰面次數 e，假設尾隨編號 i 的人，需要碰面 e 個人！經過掃描一些人後，又遇到 i，表示 i 又繞了一圈，那麼碰面次數 e = e + 1，讓尾隨後面的點時，都會遇到那該死的 i！

A code

GCJ20151B - Counter Culture
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 <string.h>
long long reverseNumber(long long x) {
    static char buf[32];
    sprintf(buf, "%lld", x);
    
    long long y = 0;
    for (int i = strlen(buf) - 1; i >= 0; i--)
        y = y * 10 + buf[i] - '0';
    return y;
}
long long f(long long n) {
    if (n < 10)
        return n;
    long long half = 1;
    while (half * half <= n)	
        half *= 10;
    if (n % half == 0)	// 1000 -> 999, 10000 -> 9999
        return 1 + f(n - 1);
    else {				
        long long v = reverseNumber(n - n%half + 1);
        if (v != n - n%half + 1)	// 123654 -> 100321, subtract & reverse
            return n%half + f(v);
        else						// 19 -> 11, but 11 is palindrome, without reverse -> 10
            return n%half + f(v-1);
    }
}
int main() {
    int testcase, cases = 0;
    long long n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld", &n);
        printf("Case #%d: %lld\n", ++cases, f(n));
    }
    return 0;
}

B code

GCJ20151B - Noisy Neighbors
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
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int main() {
    int testcase, cases = 0;
    int N, M, K;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &M, &K);
        
        vector<int> B, W;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int adj = 0;
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && y >= 0 && x < N && y < M)
                        adj++;
                }
                if ((i+j) %2 == 0)
                    B.push_back(adj), W.push_back(0);
                else
                    B.push_back(0), W.push_back(adj);
            }
        }
        
        sort(B.begin(), B.end());
        sort(W.begin(), W.end());
        
        int cost1 = 0, cost2 = 0, ret = -1;
        for (int i = 0; i < K; i++) {
            cost1 += B[i];
            cost2 += W[i];
        }
        ret = min(cost1, cost2);
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}

C code

GCJ20151B - Hiking Deer
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
#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
const int MAXN = 524288;
int N, pass[MAXN];
struct Node {
    long long arrive_time, v;
    int id;
    Node(long long a = 0, int b = 0, long long c = 0):
        arrive_time(a), id(b), v(c) {}
    bool operator<(const Node &a) const {
        if (arrive_time != a.arrive_time)
            return arrive_time < a.arrive_time;
        return v < a.v;
    }
};
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        
        set<Node> pQ;
        int id = 0;
        long long D, H, M;
        for (int i = 0; i < N; i++) {
            scanf("%lld %lld %lld", &D, &H, &M);
            for (int j = 0; j < H; j++) {
                long long arrive_time = (360 - D) * (M + j);
                pQ.insert(Node(arrive_time, id, M + j));
                pass[id] = 0, id++;
            }
        }
        
        int ret = id, encounter = id;
        
        for (; encounter <= 2 * id; ) {
            Node u = *pQ.begin(); 			// extract minimum
            
            ret = min(ret, encounter);
            
            if (pass[u.id])
                encounter++;
            else
                encounter--;
            pass[u.id] = 1;
            
            pQ.erase(pQ.begin());
            pQ.insert(Node(u.arrive_time + u.v * 360, u.id, u.v));
        }
        
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
學校課程/虛擬實境

虛擬實境 論文研讀 Part 1

期末上繳報告啊，不知道要寫多少才對得起自己。理解正確性不敢保證，相當可怕。

單詞概要

  • Computed Tomography - 電腦斷層掃描 (X 光)，簡稱 CT
  • Shepp-Logan filter - 影像去噪中，一種運算操作
  • Delaunay - 計算幾何中 Delaunay Triangulation
  • ODT - optimal Delaunay Triangulation
  • Tetrahedron - 四面體
  • Isosufrface - 等價曲面
  • Truncate - 切去頭端
  • Hausdorff distance - 空間中，集合之間的距離描述 wiki
  • Marching cubes - 用於 CT 模型，重建時的建構 3D 時，根據取樣點得到的最小構造單位。
  • QEM - Quadric Error Mactrics

本文

The Sinogram Polygonizer for Reconstructing 3D Shapes 這篇論文主要拿 Grid-base 掃描重建方法以及根據取樣點重建 3D 模型的算法探討。

首先從離散取樣中重建，最基礎的做法是根據 z-index 作切割，得到 xy 平面，在其上作 Grid-base 網格狀的取樣，得到座標 (x, y, z) 是否在該物體內部。

當取樣數量越多時，密集程度越高，能造就的邊緣就越明顯。藉由 Grid-base 取樣的缺點在於邊緣的凸顯仍然不夠明確於三角化，取樣點的數量必須非常多，才能表示非平行三軸的邊緣。

從 CT 圖中，掃描資料為數張正弦圖 (sinogram)，將一個物體放置於轉盤上，轉動轉盤將 X 光照射上去，根據物體的阻射程度得到正弦圖，相當於是光線投影到平面的強度 (CT value)。當一個物體只由一種材質構成時，其阻礙程度與阻礙光線的長度成線性關係，如此一來 CT value 就能有效地反應在物體表面的距離。

這裡補充一點，通常物體不會只由一個材質構成，因此在某些重建工作時會特別弱，如人體掃描重建，則會在眼睛材質上難以得到好的效果。阻礙能力會擴散到其他的正弦圖上，在複合材料的重建工作則會相對地困難。

CT 圖存在些許的干擾，受到鄰近材質的阻射影響。看到網路上文章寫到，即便現代的降噪算法相當厲害，對於醫院普遍使用的成像仍然使用幾十年前的算法，其最重要的原因是擔憂降噪算法捨棄掉的部分到底是不是正確的，去掉資訊若是重要的反而會造成判斷失誤，因此學術界使用 CT 圖的降噪算法仍然不普及於醫學界。

CT

目前 Shepp-Logan filter 相當好用，在 CT 去噪效果受到肯定！公式如下：

$$f(p) = \frac{1}{2} \int_{0}^{2 \pi} \alpha(R_\theta p)^{2} S_{\theta}(P(R_{\theta} p)) d \theta \\ S_{\theta}(q) \leftarrow \int_{-\infty }^{\infty} {\beta(\tilde{q}(x)) S_{\theta}(\tilde{q} (x)) h(x - (q)_{x})} dx \\ h(t) = 2 / (\pi^{2} \delta^{2} - 4 t^{2}) \\$$ $S_{\theta}(q)$ 表示在轉盤角度為$\theta$ 時成像於 q 點的數值$\beta(q) = cos(\angle qso)$，點 q 連線到光源 s、再連線到圓盤圓心點 o。並且$\tilde{q}$ 限定為與點 q 具有相同的 y 值，就是說對水平方向上鄰近點數值去噪$\delta$ 為取樣的像素大小於成像畫面。

從數學公式中看出，受到鄰近點$\tilde{q}$ 影響與光源的偏角差異、與點 q 的距離呈現的關係。

#### 補充 CT 重建 ####

CT 重建方法 中，存在三種常見的方式

迭代法 反投影法 backprojection
濾波反投影法 filtered backprojection

在掃瞄資料中，根據不同角度進行掃描投影，會得到數張 2D 影像，對於實際物體離散取樣，把每一個樣本都當作一個變數 $x_{i}$，根據模擬的方式，可以得到好幾條方程式，解出方程式後，就能知道每個位置上是否有實體 (在物體內部)。但是這樣的效能並不好，會有成千上萬的變數和方程式，甚至有可能發生多組解。


##### 迭代法 #####

迭代法提供一個逼近方法，類似模擬退火法的那種梯度迭代，每一次迭代逐漸將變數數值增加，增加後與實際投影比較，不斷地逼近投影實際值，捨棄掉不合法的數值，每迭代一次讓解更加地接近，當誤差小於某個定值後即可停止。這種作法通常會很慢，但迭代過程中可以加入很多彈性的參數變化，彈性較高。

##### 反投影法 #####

反投影法則是將投影值結果反投影回去，投影的 2D 影像上的某一個點的數值，會反投影到射線上的每一個點，多次反投影後。若該位置存在於物體中，則貢獻於投影像的次數會很多，因此反投影的累加的值也會比較高。接著給定閥值、誤差修正來判斷，效果會更為顯著。反投影法概念上非常簡單，但在邊緣的結果會很模糊。

##### 濾波反投影法 #####

濾波反投影法這部分不是很理解，看起來是先利用 卷積 (Convolution) 操作，再利用傅立葉卷積的反變換，變換過程中需要一個濾波器協助，反變換回來後，再進行反投影法。在傅立葉反變換中需要濾波器，因此選擇濾波器變得相當重要，本篇論文選的是 Shepp-Logan filter 來完成。濾波反投影法的優點是在於輪廓清楚，但會發生 吉布斯現象 (Gibbs phenomenon)，逼近原圖時，不連續的函數截面附近會發生震盪。

## 接續 ##

在濾波後，反投影後得到 CT value $f(p)$。當然 $f(p)$ 是一個連續函數的積分，事實上處理時離散的 (因為機器再怎麼精密，齒輪轉角也不會是連續，就看齒數多寡來決定)。

論文中用了 迭代法 和 濾波反投影法 重建比較，可以得到非常相似的結果。來確認使用的儀器是相當可靠的精準度。

接下來要進行建模，簡單會具有以下幾個步驟。

1. 可以決定要用幾個四面體構成。
2. 三角網格藉由二值化 (CT value 來判定是在物體中還是外部) 抓取，並且加入四面體中。
3. 三角網格到等值曲面的 QEM (Quadric Error Mactrics) 要最小化。
4. 三角網格上的點座標，移動距離購小的時候，算法停止迭代。否則返回第二步，繼續鬆弛新的節點。

第一步進行四面體構成時，通常會採用 * Delaunay Tetrahedralization (相對於 2D 平面的 Delaunay Trianglution，Delaunay Trianglution 是由 2D Voronoi Diagram，那麼 Delaunay Tetrahedralization 就是由 3D Voronoi Diagram 搭建完成)，事實上還有數種建模的方法 (如 Marching cubes 之類的)，稍後有機會會提及到。但不管一開始選定的四面體採用哪種策略，經由往後的迭代，將會修整到差不多 QEM。

### 邊緣擷取 ###

對於每一個四面體，找到四面體的重心$g_{i}$ 並且計算 CT value $f(g_{i})$

對於相鄰的四面體，計算 $Tiso= (f(gi)+f(gj))/2$ 接下來要找等值曲面 $Tiso$，找到一個點 p 位於等值曲面上，並且 p 在 gi, gj 的連線上。對於 p 所在的等值曲面上計算法向量 $n_{k}$，等下要用來計算 QEM 用的。

QEM

下篇待續

Read More +
解題區/解題區 - UVa

UVa 1502 - GRE Words

Problem

依序背單字，下一個單字中要出現當前單字為 substring 的情況，每一個單字都有各自的權重，求背一次能得到的最高權重總合為多少。

如範例輸入背的順序為 a -> ab -> abb -> abbab 答案為 1 + 2 + 3 + 8 = 14。

Sample Input

1
2
3
4
5
6
7
1
5
a 1
ab 2
abb 3
baba 5
abbab 8

Sample Output

1
Case #1: 14

Solution

這一題的測資有問題，輸入中出現非小寫字母，導致存取發生錯誤，部分程序沒有考慮這一點，居然就通過了？
一群人 Invalid Memory Access 通過，而我因寫法比較不同成了 RE 下亡魂，測試數據格式錯誤啊！坑爹啊，害我掛載好多 assert 抓哪裡溢出 …

原本想說是一道有趣的 AC 自動機複習，將 fail 指針 (suffix link) 整理成另一棵樹，對其 fail tree 壓樹 (走訪)，套上線段樹等數據結構，就能支持多字串匹配的數據查找。當匹配時將會一直攀爬 fail 指針，最後爬到 root，中間經過的節點都是匹配的字串，也因此單看 fail 指針，也肯定是 tree。

在走訪時，會匹配 fail link 上的所有節點 (都是其 suffix string)。dp[i] 表示使用第 i 個字串為背單字序列結尾的最大權重，則 dp[i] = max(dp[j]) + w，其中滿足 j < i 且 word[j] 是 word[i] 的 substring。

窮舉第 i 字符串的後綴匹配節點，找尋匹配節點藉由 fail link 到 root 上節點的最大值 (max(dp[j]))。

利用線段樹完成區間最大值更新、單點查詢 (找尋節點到 root 的最大值，更新一個點的權重時，相當於作區間最大值更新，藉由壓樹其子樹被表示成區間)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
// NOTES: has error test data, there are some characters which aren't lowercase letters.
// FUCK
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#include <assert.h>
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
const int MAXCHAR = 26;
const int MAXNODE = 1048576;
class ACmachine {
public:
    struct Node {
        Node *next[MAXCHAR], *fail;
        int cnt, val, id, nid;
        void init() {
            fail = NULL;
            cnt = val = 0;
            nid = id = -1;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size;
    vector<int> fg[MAXNODE];
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init(), p->nid = size-1;
        assert(size < MAXNODE);
        fg[p->nid].clear();
        return p;
    }
    void init() {
        size = 0;
        root = getNode();
    }
    int toIndex(char c) {
    	assert(c - 'a' >= 0 && c - 'a' < MAXCHAR);
        return c - 'a';
    }
    void dfs(Node *p, Node *q) {
        for (int i = 0; i < MAXCHAR; i++) {
            if (q->next[i]) {
                Node *u = p->next[i], *v = q->next[i];
                if (u == NULL)
                    p->next[i] = getNode(), u = p->next[i];
                u->cnt |= v->cnt;
                dfs(u, v);
            }
        }
    }
    void merge(const ACmachine &other) {
        dfs(root, other.root);
    }
    void insert(const char str[], int sid) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        p->cnt = 1;
        if (sid >= 0)	p->id = sid;
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
    void build() { // AC automation    
        queue<Node*> Q;
        Node *u, *p;
        Q.push(root), root->fail = NULL;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            if (u != root) {
            	assert(u->fail != NULL);
            	assert(u->nid != u->fail->nid);
            	fg[u->nid].push_back(u->fail->nid);
            	fg[u->fail->nid].push_back(u->nid);
            }
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] == NULL)
                    continue;
                Q.push(u->next[i]);
                p = u->fail;
                while (p != NULL && p->next[i] == NULL)
                    p = p->fail;
                if (p == NULL || p->next[i] == NULL)
                    u->next[i]->fail = root;
                else
                    u->next[i]->fail = p->next[i];
                u->next[i]->val = u->next[i]->fail->val + u->next[i]->cnt;
                u->next[i]->id = u->next[i]->fail->id | u->next[i]->id;
            }
        }
    }
    int query(const char str[]) {
        Node *u = root, *p;
        int matched = 0;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            while (u->next[idx] == NULL && u != root)
                u = u->fail;
            u = u->next[idx];
            u = (u == NULL) ? root : u;
            p = u;
            matched += p->val;
        }
        return matched;
    }
    void free() {
        return ;
        // owner memory pool version
        queue<Node*> Q;
        Q.push(root);
        Node *u;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] != NULL) {
                    Q.push(u->next[i]);
                }
            }
            delete u;
        }
    }
};
const int MAXN = 1048576;
class SegmentTree {
public:
    struct Node {
        long long mx;
        pair<int, long long> label;
        void init() {
            mx = -1LL<<60;
            label = make_pair(0, 0);
        }
    } nodes[MAXN];
    void pushDown(int k, int l, int r) {
        int mid = (l + r)/2;
        if (nodes[k].label.first) {
            maxUpdate(k<<1, l, mid, nodes[k].label.second);
            maxUpdate(k<<1|1, mid+1, r, nodes[k].label.second);
            nodes[k].label = make_pair(0, 0); // cancel
        }
    }
    void pushUp(int k) {
        nodes[k].mx = max(nodes[k<<1].mx, nodes[k<<1|1].mx);
    }
    void build(int k, int l, int r) { 
        nodes[k].init();
        if (l == r) {
            nodes[k].mx = 0;
            return ;
        }
        int mid = (l + r)/2;
        build(k<<1, l, mid);
        build(k<<1|1, mid+1, r);
        pushUp(k);
    } 
    // operator, assign > add
    void maxUpdate(int k, int l, int r, long long val) {
        if (nodes[k].label.first)
            val = max(val, nodes[k].label.second);
        nodes[k].label = make_pair(1, val);
        nodes[k].mx = max(nodes[k].mx, val);
    }
    void assign(int k, int l, int r, int x, int y, int val) {
        if (x <= l && r <= y) {
            maxUpdate(k, l, r, val);
            return;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            assign(k<<1, l, mid, x, y, val);
        if (y > mid)
            assign(k<<1|1, mid+1, r, x, y, val);
        pushUp(k);
    }
    // query 
    long long r_mx;
    void qinit() {
        r_mx = -1LL<<60;
    }
    void query(int k, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            r_mx = max(r_mx, nodes[k].mx);
            return ;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            query(k<<1, l, mid, x, y);
        if (y > mid)
            query(k<<1|1, mid+1, r, x, y);
    }
};
ACmachine ac;
SegmentTree tree;
vector<string> words;
vector<int> wvals;
char s[1048576];
int bPos[MAXN], ePos[MAXN], inIdx;
void prepare(int u, int p) {
    bPos[u] = ++inIdx;
    for (int i = 0; i < ac.fg[u].size(); i++) {
        if (ac.fg[u][i] == p)	continue;
        prepare(ac.fg[u][i], u);
    }
    ePos[u] = inIdx;
} 
void solve() {
    for (int i = 0; i < ac.size; i++)
        bPos[i] = ePos[i] = 0;
    inIdx = 0;
    for (int i = 0; i < ac.size; i++) {
        if (bPos[i] == 0) {
            prepare(i, -1); // interval [1, inIdx]
        }
    }
            
    assert(inIdx < MAXN/2);
    tree.build(1, 1, inIdx);
    
    long long ret = 0;
    for (int i = 0; i < words.size(); i++) {
        ACmachine::Node *u = ac.root;
        int idx;
        long long dpval = 0;
        for (int j = 0; j < words[i].length(); j++) {
            idx = ac.toIndex(words[i][j]);
            while (u->next[idx] == NULL && u != ac.root)
                u = u->fail;
            u = u->next[idx];
            u = (u == NULL) ? ac.root : u;
            
            tree.qinit();
            tree.query(1, 1, inIdx, bPos[u->nid], bPos[u->nid]);
            dpval = max(dpval, tree.r_mx);
        }
        dpval += wvals[i];
        tree.assign(1, 1, inIdx, bPos[u->nid], ePos[u->nid], dpval);
        ret = max(ret, dpval);
    }
    printf("%lld\n", ret);
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int testcase, cases = 0;
    int N, val;
    scanf("%d", &testcase);
    while (testcase--) {
    	scanf("%d", &N);
    	    	
       	ac.init();
       	words.clear(), wvals.clear();
       	for (int i = 0; i < N; i++) {
       		scanf("%s %d", s, &val);
       		ac.insert(s, i);
       		words.push_back(s), wvals.push_back(val);
       	}
       	
       	ac.build();
       	
       	printf("Case #%d: ", ++cases);
       	solve(); 
       	
        ac.free();
    }
    return 0;
}
/*
999
4
abbaaa 49
bba 41
ba 19
bbba 20
8
abbaaa 49
bba 41
ba 19
bbba 20
abbbabaaa 21
b 47
ababba 26
a 0
3
abaab 35
ab 9
abaabaaabbabababaaab 35
8
aabbbbbababbaaaab 14
abaabbaaaaaabbaabbba 13
babaaababaaaaabababa 17
abaab 35
ab 9
abaabaaabbabababaaab 35
bbbaaa 31
aabab 34
32
aa 19
bababbabbbaabaaaab 40
aabbbaaaaaa 48
ababaaabbabbbaabbb 38
a 42
bbbbbaabbbaa 10
baabbbababaab 41
aabbabbabba 28
baaab 3
aaaaaaaaa 15
bbbabbababaaabab 16
aab 18
baaab 2
abbbab 2
bababa 4
bbabbbbbaabbaaaababb 35
bbbaabba 34
bbbb 24
bbbb 17
babbbabbababababaa 9
ababaaaa 38
bbbb 3
bba 31
aabaabaaa 34
aabbbbbaababaa 41
aabbbaabbbabaababbbb 45
abbbaabbababab 37
ababbaabb 3
bbabbbbbaba 8
a 10
babbabaabbbbab 34
bbababaaaaaaaaa 5
 */
Read More +