解題區/解題區 - UVa

UVa 1555 - Garland

Problem

給定 N 盞燈，第一盞燈的所在高度 A。

  • Hi = (Hi-1 + Hi+1)/2 - 1

在 Hi 不低於地面高度 0 的條件下，請問最後一盞燈的高度最低為何。

Sample Input

1
692 532.81

Sample Output

1
446113.34

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
#include <stdio.h>
double isValid(int N, double H1, double H2) {
    double H = 0;
    for (int i = 3; i <= N; i++) {
        H = 2 * H2 + 2 - H1;
        if (H < 0)	return -1;
        H1 = H2;
        H2 = H;
    }
    return H;
}
int main() {
    int N;
    double A;
    while (scanf("%d %lf", &N, &A) == 2) {
        double l = 0, r = A, mid, ret = 0, t;
        for (int it = 0; it < 50; it++) {
            mid = (l + r)/2;
            if ((t = isValid(N, A, mid)) >= 0)
                r = mid, ret = t;
            else
                l = mid;
        }
        printf("%.2lf\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12477 - Good Measures of Dispersion

Problem

詢問區間最大值、最小值、標準差

  • 修改區間內所有元素 A[l, r] = val。
  • 增加區間內所有元素 A[l, r] += val。

Sample Input

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

Sample Output

1
2
3
4
5
Case 1:
13/1 10
6/1 6
8/1 8
0/1 0

Solution

利用線段樹的懶操作，解決區間修改問題。

特別注意到區間的 assign 優先權高於 add，當懶操作 assign 被指派時，取消 add。將懶操作標記在節點 x 上，其 x 已經統計好結果，若發生要走訪 x 的子樹，將標記傳遞給子樹。

標準差的部分，可以利用 平方和 和 總和 計算之，因此紀錄總共需要四項 sum, sqr, mx, mn 來完成此題。

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
#include <stdio.h> 
#include <algorithm>
using namespace std;
const int MAXN = 524288;
class SegmentTree {
public:
    struct Node {
        long long sum, sqr, mx, mn;
        pair<int, long long> label[2];
        void init() {
            sum = sqr = 0;
            mx = -1LL<<60, mn = 1LL<<60;
            label[0] = label[1] = make_pair(0, 0);
        }
    } nodes[MAXN];
    long long A[MAXN];
    void pushDown(int k, int l, int r) {
        int mid = (l + r)/2;
        if (nodes[k].label[0].first) {
            assignUpdate(k<<1, l, mid, nodes[k].label[0].second);
            assignUpdate(k<<1|1, mid+1, r, nodes[k].label[0].second);
            nodes[k].label[0] = make_pair(0, 0); // cancel
        }
        if (nodes[k].label[1].first) {
            addUpdate(k<<1, l, mid, nodes[k].label[1].second);
            addUpdate(k<<1|1, mid+1, r, nodes[k].label[1].second);
            nodes[k].label[1] = make_pair(0, 0); // cancel
        }
    }
    void pushUp(int k) {
        nodes[k].sum = nodes[k<<1].sum + nodes[k<<1|1].sum;
        nodes[k].sqr = nodes[k<<1].sqr + nodes[k<<1|1].sqr;
        nodes[k].mx = max(nodes[k<<1].mx, nodes[k<<1|1].mx);
        nodes[k].mn = min(nodes[k<<1].mn, nodes[k<<1|1].mn);
    }
    void build(int k, int l, int r) { 
        nodes[k].init();
        if (l == r) {
            nodes[k].sum = A[l];
            nodes[k].sqr = A[l] * A[l];
            nodes[k].mx = nodes[k].mn = A[l];
            return ;
        }
        int mid = (l + r)/2;
        build(k<<1, l, mid);
        build(k<<1|1, mid+1, r);
        pushUp(k);
    } 
    // operator, assign > add
    void assignUpdate(int k, int l, int r, long long val) {
        nodes[k].label[0] = make_pair(1, val);
        nodes[k].label[1] = make_pair(0, 0); // cancel lower priority
        nodes[k].sum = (long long) (r - l + 1) * val;
        nodes[k].sqr = (long long) (r - l + 1) * val * val;
        nodes[k].mn = nodes[k].mx = val;
    }
    void addUpdate(int k, int l, int r, long long val) {
        nodes[k].label[1].first = 1;
        nodes[k].label[1].second += val;
        nodes[k].sqr += 2LL * val * nodes[k].sum + (long long) (r - l + 1) * val * val;
        nodes[k].sum += (long long) (r - l + 1) * val;
        nodes[k].mn += val;
        nodes[k].mx += val;
    }
    void assign(int k, int l, int r, int x, int y, int val) {
        if (x <= l && r <= y) {
            assignUpdate(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);
    }
    void add(int k, int l, int r, int x, int y, int val) {
        if (x <= l && r <= y) {
            addUpdate(k, l, r, val);
            return;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            add(k<<1, l, mid, x, y, val);
        if (y > mid)
            add(k<<1|1, mid+1, r, x, y, val);
        pushUp(k);
    }
    // query 
    long long r_sum, r_sqr, r_mx, r_mn;
    void qinit() {
        r_sum = r_sqr = 0;
        r_mx = -1LL<<60, r_mn = 1LL<<60;
    }
    void query(int k, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            r_sum += nodes[k].sum;
            r_sqr += nodes[k].sqr;
            r_mx = max(r_mx, nodes[k].mx);
            r_mn = min(r_mn, nodes[k].mn);
            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);
    }
} tree;
long long llgcd(long long x, long long y) {
    long long t;
    while (x%y)
        t = x, x = y, y = t%y;
    return y;
}
int main() {
    int testcase, cases = 0;
    int n, q;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &q);
        for (int i = 1; i <= n; i++)
            scanf("%lld", &tree.A[i]);
            
        tree.build(1, 1, n);
        
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < q; i++) {
            int cmd, l, r, val;
            scanf("%d", &cmd);
            if (cmd == 0) { // assign [l, r] = val
                scanf("%d %d %d", &l, &r, &val);
                tree.assign(1, 1, n, l, r, val);
            } else if (cmd == 1) { // add [l, r] = val
                scanf("%d %d %d", &l, &r, &val);
                tree.add(1, 1, n, l, r, val);
            } else if (cmd == 2) {
                scanf("%d %d", &l, &r);
                
                tree.qinit();
                tree.query(1, 1, n, l, r);
                
                long long m = (r - l + 1), g;
                long long a = tree.r_sqr * m - tree.r_sum * tree.r_sum;
                long long b = m * m;
                g = llgcd(a, b);
                a /= g, b /= g;
                printf("%lld/%lld ", a, b);
                printf("%lld\n", tree.r_mx - tree.r_mn);
            }
        }
    }
    return 0;
}
/*
999
9 6
-1 3 2 4 -2 8 0 5 -7
2 3 6
0 5 5 2
2 3 6
1 4 7 1
2 3 7
2 1 1
9 6
-1 3 2 4 -2 8 0 5 -7
2 3 6
0 5 5 2
2 3 6
1 4 7 1
2 3 7
2 1 1
*/
Read More +
解題區/解題區 - UVa

UVa 11098 - Battle II

Problem

每個炸彈都有引爆範圍、炸彈半徑、以及炸彈所在座標。

  • 引爆一個炸彈時，其爆炸範圍內的其他炸彈也會被引爆，產生連鎖反應一次引爆多顆炸彈。
  • 引爆過的炸彈，無法再次引爆。
  • 引爆一個炸彈的成本與爆炸範圍成正比 1 : 1。

求平均花費 (引爆總花費 / 引爆次數) 最小為何？

Sample Input

1
2
3
4
5
6
1
3
4 7 2 2
8 5 1 0
3 -3 1 1

Sample Output

1
Case #1: 1 0 2

Solution

問平均最少花費是有原因的，如果只問最少花費只需要引爆無法被連鎖的炸彈，或者在 SCC 連通元件中找一個花費最小的炸彈。

首先，在一個連鎖反應下，先做 SCC 進行縮點，知道一個 SCC 元件中用花費最小的那個炸彈代表即可，將圖轉換成 DAG 後。indegree = 0 的點必然需要手動引爆，在這樣的情況下，已經能讓所有炸彈引爆。

為了要讓平均花費最小，勢必增加引爆炸彈的數量，引爆時便能降低平均花費，但引爆的順序必須按照拓樸排序，否則會違反 引爆過的炸彈，無法再次引爆 的規則。

藉此，根據貪心策略，將非 indegree = 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
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
// SCC, DAG, greedy
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN = 1024;
class SCC {
public:
    int n;
    vector<int> g[MAXN], dag[MAXN];
    // <SCC begin>
    int vfind[MAXN], findIdx;
    int stk[MAXN], stkIdx;
    int in_stk[MAXN], visited[MAXN];
    int contract[MAXN];
    int scc_cnt;
    // <SCC end>
    int scc(int u) {
        in_stk[u] = visited[u] = 1;
        stk[++stkIdx] = u, vfind[u] = ++findIdx;
        int mn = vfind[u], v;
        for(int i = 0; i < g[u].size(); i++) {
        	v = g[u][i];
            if(!visited[v])
                mn = min(mn, scc(v));
            if(in_stk[v])
                mn = min(mn, vfind[v]);
        }
        if(mn == vfind[u]) {
            do {
                in_stk[stk[stkIdx]] = 0;
                contract[stk[stkIdx]] = scc_cnt;
            } while(stk[stkIdx--] != u);
            scc_cnt++;
        }
        return mn;
    }
    void addEdge(int u, int v) { // u -> v
        g[u].push_back(v);
    }
    void solve() {
        for (int i = 0; i < n; i++)
            visited[i] = in_stk[i] = 0;
        scc_cnt = 0;
        for (int i = 0; i < n; i++) {
        	if (visited[i])	continue;
        	stkIdx = findIdx = 0;
        	scc(i);
        }
    }
    void make_DAG() {
        int x, y;
        for (int i = 0; i < n; i++) {
            x = contract[i];
            for (int j = 0; j < g[i].size(); j++) {
                y = contract[g[i][j]];
                if (x != y)
                    dag[x].push_back(y);
            }
        }
        for (int i = 0; i < scc_cnt; i++) {
            sort(dag[i].begin(), dag[i].end());
            dag[i].resize(unique(dag[i].begin(), dag[i].end()) - dag[i].begin());
        }
    }
    void init(int n) {
        this->n = n;
        for (int i = 0; i < n; i++)
            g[i].clear(), dag[i].clear();
    }
} g;
int X[MAXN], Y[MAXN], E[MAXN], R[MAXN];
void greedy() {
    int m = g.scc_cnt, n = g.n;
    int cost[MAXN], scc_id[MAXN], pick[MAXN] = {};
    for (int i = 0; i < m; i++)
        cost[i] = 0x3f3f3f3f, scc_id[i] = -1;
    for (int i = 0; i < n; i++) {
        if (cost[g.contract[i]] > E[i])
            cost[g.contract[i]] = E[i], scc_id[g.contract[i]] = i;
    }
    
    int indeg[MAXN]	= {};
    vector<int> topo;
    queue<int> Q;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < g.dag[i].size(); j++) {
            indeg[g.dag[i][j]]++;
        }
    }
        
    // greedy, let reta / retb = minimum value
    // if (reta / retb) > (reta + cost) / (retb + 1)
    long long reta = 0, retb = 0; // min average cost = total cost / #bomb
    vector< pair<int, int> > candidate;
    for (int i = 0; i < m; i++) {
        if (indeg[i] == 0) {
            reta += cost[i], retb++;
            pick[i] = 1;
        } else {
            candidate.push_back(make_pair(cost[i], i));
        }
    }
    sort(candidate.begin(), candidate.end()); 
    for (int i = 0; i < candidate.size(); i++) {
        long long c = candidate[i].first;
        if (reta * (retb + 1) > (reta + c) * retb) {
            reta += c, retb++;
            pick[candidate[i].second] = 1;
        }
    }
    
    // topo
    for (int i = 0; i < m; i++)
        if (indeg[i] == 0)	Q.push(i);
    while (!Q.empty()) {
        int u = Q.front(), v;
        Q.pop();
        topo.push_back(u);
        for (int i = 0; i < g.dag[u].size(); i++) {
            v = g.dag[u][i];
            if (--indeg[v] == 0)
                Q.push(v);
        }
    }
    
    // make order with fire rule
    int topo_r[MAXN] = {};
    vector< pair<int, int> > ret;
    for (int i = 0; i < topo.size(); i++) {
        topo_r[topo[i]] = i;
    }
    for (int i = 0; i < m; i++) {
        if (pick[i])
            ret.push_back(make_pair(topo_r[i], scc_id[i]));
    }
    sort(ret.begin(), ret.end());
    
    for (int i = ret.size() - 1; i >= 0; i--)
        printf(" %d", ret[i].second);
    puts("");
//	printf("%lld / %lld\n", reta, retb);
}
int main() {
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d %d %d %d", &X[i], &Y[i], &R[i], &E[i]);
        
        g.init(n);	
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;
                long long dist = (long long)(X[i] - X[j]) * (X[i] - X[j]) + (long long)(Y[i] - Y[j]) * (Y[i] - Y[j]);
                long long r = (long long)(R[i] + E[i] + R[j]) * (R[i] + E[i] + R[j]);
                if (dist <= r) 
                    g.addEdge(i, j);
            }
        }
        
        g.solve();
        g.make_DAG();
        
        printf("Case #%d:", ++cases);
        greedy();
    }
    return 0;
}
/*
1
3
4 7 2 2
8 5 1 0
3 -3 1 1
1
7
24 1 4 7
38 33 4 3
13 13 2 0
34 1 0 0
6 25 5 4
1 14 3 7
30 35 1 6
*/
Read More +
解題區/解題區 - UVa

UVa 1086 - The Ministers' Major Mess

Problem

有 M 個人，B 個方案要進行投票表決。

每個人可以選擇 ki 個方案進行通過或不通過，其中 ki <= 4。找到一種方案的通過方式滿足所有人選擇項目的一半以上 (不含)。

Sample Input

1
2
3
4
5
6
7
5 2 
4 2 y 5 n 3 n 4 n
4 4 y 3 y 5 n 2 y 
4 2 
4 1 y 2 y 3 y 4 y 
3 1 n 2 n 3 n 
0 0

Sample Output

1
2
Case 1: ?y??n 
Case 2: impossible

Solution

由於 ki <= 4，又要滿足一半以上。則對於 ki = 1, 2 需要全部符合他們的項目。對於 ki = 3, 4 則不滿足其中一個選項 i 時，其他的選項 j 都必須滿足。

藉此套用 2-sat 模型，找到是否可能有可行解。當要輸出 2-sat 其中一解時，窮舉每一個變數為 true / false，建立一條邊 x -> x' / x' -> x，再用 2-sat 模型判斷是否有解即可。

找解速度會慢很多，這樣會比較好撰寫。

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
// 2-satisify problem
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN = 262144;
class TwoSat {
public:
    int n;
    vector<int> g[MAXN];
    // <SCC begin>
    int vfind[MAXN], findIdx;
    int stk[MAXN], stkIdx;
    int in_stk[MAXN], visited[MAXN];
    int contract[MAXN];
    int scc_cnt;
    // <SCC end>
    int scc(int u) {
        in_stk[u] = visited[u] = 1;
        stk[++stkIdx] = u, vfind[u] = ++findIdx;
        int mn = vfind[u], v;
        for(int i = 0; i < g[u].size(); i++) {
        	v = g[u][i];
            if(!visited[v])
                mn = min(mn, scc(v));
            if(in_stk[v])
                mn = min(mn, vfind[v]);
        }
        if(mn == vfind[u]) {
            do {
                in_stk[stk[stkIdx]] = 0;
                contract[stk[stkIdx]] = u;
            } while(stk[stkIdx--] != u);
            scc_cnt++;
        }
        return mn;
    }
    void addEdge(int u, int v) { // u -> v
        g[u].push_back(v);
    }
    int solvable() {
        for (int i = 0; i < n; i++)
            visited[i] = in_stk[i] = 0;
        scc_cnt = 1;
        for (int i = 0; i < n; i++) {
        	if (visited[i])	continue;
        	stkIdx = findIdx = 0;
        	scc(i);
        }
        
        for(int i = 0; i < n; i += 2)
            if(contract[i] == contract[i^1])
                return 0;
        return 1;
    }
    void computeChoice() {
        if (!solvable())
            return ;
        for (int i = 0; i < n; i += 2) {
            int val = 0;
            g[i].push_back(i^1);
            if (solvable())	val |= 1;
            g[i].pop_back();
            
            g[i^1].push_back(i);
            if (solvable())	val |= 2;
            g[i^1].pop_back();
            
            printf("%c", "-yn?"[val]);
        }
        puts("");
    }
    void init(int n) {
        this->n = n;
        for (int i = 0; i < n; i++)
            g[i].clear();
    }
} g;
// more than half of his or her opinions satisfied
// opinion <= 4
int main() {
    int n, m, cases = 0;
    char s[128];
    while (scanf("%d %d", &n, &m) == 2 && n) {
        g.init(2 * n);
        
        for (int i = 0; i < m; i++) {
            int vote[8], k, x;
            scanf("%d", &k);
            for (int j = 0; j < k; j++) {
                scanf("%d %s", &x, s);
                x--;
                vote[j] = x * 2 + (s[0] == 'y');
            }
            if (k <= 2) { // all satisfied
                for (int p = 0; p < k; p++)
                    g.addEdge(vote[p]^1, vote[p]);
            } else { // one fail
                for (int p = 0; p < k; p++) {
                    for (int q = 0; q < k; q++) {
                        if (p == q)	continue;
                        // p-th opinion fail
                        g.addEdge(vote[p]^1, vote[q]);
                    }
                }
            }
        }
        
        printf("Case %d: ", ++cases);
        if (!g.solvable()) {
            puts("impossible");
        } else {
            g.computeChoice();
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11119 - Chemical Attraction

Problem

給予由陰陽離子構成的化合物，混和後會根據活性表發生變化，求其中一種穩定態。

所謂的穩定態，就是不會兩個化合物之間可以進行陰陽離子的互換。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
3
Ba Sr Th
3
Cl Br Fl
1 2 3
1 3 2
2 1 3
2 1 3
1 3 2
1 2 3
3
BaFl SrBr ThCl
5
BaFl BaFl SrFl SrCl ThFl
0
3
Na Ag Fe
5
Su Zi Xe Ar Do
1 2 4 3 5
5 3 1 2 4
2 3 1 4 5
3 2 1
3 2 1
1 3 2
1 2 3
2 1 3
10
NaDo AgDo AgAr FeXe NaXe
AgZi AgZi NaSu AgSu FeDo
0
0

Sample Output

1
2
3
4
5
6
7
8
Scenario 1, Mixture 1:
BaCl SrBr ThFl
Scenario 1, Mixture 2:
BaFl BaCl SrFl SrFl ThFl
Scenario 2, Mixture 1:
NaDo AgSu AgSu FeDo NaXe AgZi AgZi NaXe AgAr FeDo

Solution

一個經典的穩定婚姻問題 (stable marriage problem)，可以用 Gale-Shapley algorithm 解決匹配兩邊個數相同的穩定婚姻。穩定婚姻有兩組最優解，其中一組最優解於男方、另外一組為女方，其最優解即為候選的排序為字典順序最小的。

假設現在要給男方一個最優解，那麼根據貪心的思路，男方要不斷地按照排名清單去向女方求婚，如果女方心中對求婚男方的排名更好，則男方求婚成功，而前男友就會被拋棄，被拋棄的男方將會根據清單再找下去。做法類似增廣路徑。

為什麼這樣能趨近穩定呢？原因是這樣子的，由於男方不斷地求婚，女方配對男方的排名會越來越好，男方被拋棄後，求婚對象則會越來越差。

假定男方為 A, B，女方為 1, 2，優先順序為括弧內，越靠前表示順位越高。

1
2
A(1, 2) - 1(B, A)
B(1, 2) - 2(A, B)

假如 A - 1 和 B - 2，則女 1 更喜歡男 A，女 2 更喜歡男 B，男方中也更喜歡對方的配偶 (這個例子中是相同)，而造成配對交換，這即為不穩定婚姻。

解決會交換的情況。當嘗試配對一對男女時，如何保證不會發生循環交換？當男主被某女拋棄，則表示某女心中有一個更好的某男。男方按照順序求婚，就不會發生男方中會更喜歡對方的配偶而交換。

單看女方，了解到拋棄的動作是有限的，算法就能在 O(N^2) 解決。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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
// Gale-Shapley algorithm, stable marriage problem
#include <stdio.h>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 256;
class GaleShapley { // produce the best possible choice for the mans
public:
    int mOrder[MAXN][MAXN], fOrder[MAXN][MAXN];
    int fPref[MAXN][MAXN];
    int man[MAXN], woman[MAXN];
    int N;
    void init(int n) {
        N = n;
    }
    void stable() {
        int mIdx[MAXN];
        for (int i = 0; i < N; i++)
            man[i] = woman[i] = -1, mIdx[i] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                fPref[i][fOrder[i][j]] = j;
        }
        for (int i = 0; i < N; i++) {
            int m = i, w;
            while (m >= 0) {
                w = mOrder[m][mIdx[m]++];
                while (m >= 0 && (woman[w] == -1 || fPref[w][woman[w]] > fPref[w][m])) {
                    man[m] = w;
                    swap(m, woman[w]);
                }
            }
        }
    }
} g;
char s[MAXN];
int tA[MAXN][MAXN], tB[MAXN][MAXN], rtA[MAXN][MAXN], rtB[MAXN][MAXN];
int main() {
    int N, M, x, n;
    int cases = 0;
    while (scanf("%d", &N) == 1 && N) {
    	map<string, int> Rn, Rm;
        for (int i = 0; i < N; i++)
        	scanf("%s", s), Rn[s] = i;
        scanf("%d", &M);
        for (int i = 0; i < M; i++)
        	scanf("%s", s), Rm[s] = i;
    	
    	for (int i = 0; i < N; i++)
    		for (int j = 0; j < M; j++)
    			scanf("%d", &tA[i][j]), tA[i][j]--, rtA[i][tA[i][j]] = j;
    	for (int i = 0; i < M; i++)
    		for (int j = 0; j < N; j++)
    			scanf("%d", &tB[i][j]), tB[i][j]--, rtB[i][tB[i][j]] = j;
    	++cases;
    	int tcases = 0;
    	while (scanf("%d", &n) == 1 && n) {
    		vector<string> A, B;
    		for (int i = 0; i < n; i++) {
    			scanf("%s", s);
    			string a(2, 'a'), b(2, 'a');
    			a[0] = s[0], a[1] = s[1];
    			b[0] = s[2], b[1] = s[3];
    			A.push_back(a), B.push_back(b);
    		}
    		g.init(n);
    		
    		for (int i = 0; i < n; i++) {
    			vector< pair<int, int> > p;
    			int u = Rn[A[i]], v;
    			for (int j = 0; j < n; j++) {
    				v = Rm[B[j]];
    				p.push_back(pair<int, int>(tA[u][v], j));
    			}
    			sort(p.begin(), p.end(), greater< pair<int, int> >());
    			for (int j = 0; j < n; j++) {
    				g.mOrder[i][j] = p[j].second;
//    				printf("%d ", p[j].second);
    			}
//    			puts(" -m");
    		}
    		
    		for (int i = 0; i < n; i++) {
    			vector< pair<int, int> > p;
    			int u = Rm[B[i]], v;
    			for (int j = 0; j < n; j++) {
    				v = Rn[A[j]];
    				p.push_back(pair<int, int>(tB[u][v], j));
    			}
    			sort(p.begin(), p.end(), greater< pair<int, int> >());
    			for (int j = 0; j < n; j++) {
    				g.fOrder[i][j] = p[j].second;
//    				printf("%d ", p[j].second);
    			}
//    			puts(" -f");
    		}
    		
    		g.stable();
    		
    		printf("Scenario %d, Mixture %d:\n", cases, ++tcases);
    		for (int i = 0; i < n; i++) {
    			int m = g.man[i];
    			if (i)	printf(" ");
    			printf("%s%s", A[i].c_str(), B[m].c_str());
    		}
    		puts("\n");
    	}
    }
    return 0;
}
/*
 */
Read More +
學校課程/資訊安全

區段加密筆記

本篇筆記，僅為個人淺見

什麼是區段加密

先了解 stream ciphers 和 block ciphers 的差異

  • stream ciphers 特別在於加密用的 key 不斷地變更，並且以極少數的情況下重複使用，每一次加密針對一個 byte 或者是 bit 進行加密。加解密的兩方，可以同時產生出相同 random key。

  • block ciphers 只用同一份 key，把加密文件一次用一個 block 文字進行加密，利用換位 (位置交換)、替換 (文字替換) … 等方式，讓相似內容的明文，可以產出差異極大的密文 (訊息獨立)。

從概念上，串流加密是絕對安全，如果雙方有辦法在不通訊下，可以產生出 random key，而且不重複使用 key，攻擊者會無從下手。但是現今很多 random 的產生方法仍然是演算法的數學模型，因此一定有規則。

而區段加密的好處，在於換位、替換、 … 等方式，將密文的相似度降低，即使明文長得很相似，攻擊者無法誘導相似明文的傳遞，導致 key 快速被發現，因為密文的差異性導致規則難以被破解。

加密設計基礎原則

  • confusion 困惑
    密文跟 key 的關係盡可能混亂，根據加密的方式，有可能某些 key 會造成特殊的密文規則，這種弱 key 要不不存在、要不不使用。減少攻擊者對密文的觀察，就可以找到 key。

  • diffusion 散播
    當明文相當相似時，也許只有幾個 bit 不同，產生出來的密文的差異性也要相當高，否則攻擊者可以推導加密原理，藉由 bitwise 將密文修改，讓解密者受到誤導。

Data Encryption Standard (DES)

  • 每一次加密 64 -bit 的資料，用 56 -bit 的 key。
    這是一個很詭異的現象，通常 key 的長度會比 data 的長度來得大。
  • 經過 16 回合的加密，並且每一個回合用 56 -bit 的 key 產生出 48 -bit 的 subkey 針對 64 -bit 的資料加密。
  • 加密過程會有擴充 subkey 和選擇一部分的 subkey，並且拿一部分的明文對 subkey 加密。

將明文對切成兩個部分，一部分加密 subkey，另一部分根據加密過的 subkey 進行加密。在下一個回合，交換部分明文和部分密文的位置，讓所有的明文都進入到混亂狀態。

在解密時，知道 subkey 的產生規則，然後拿部分明文，加密 subkey 後，得到部分密文的加密要件，逆推回去。這一個繁複的過程，主要是製造 confusion，而 diffusion 的部分，則是在擴充 key 和拿部分明文加密 subkey 時，發生雪崩效應，因為拿部分明文進行加密 subkey，會造成 key 差異性放大。

儘管明文相似程度很高，卻會因為處理過程將差異轉移到 subkey 很多的位置的不同，經過輪替加密。無法利用頻率的方式，找到明文差異會造成密文的哪一個部分的差異。

正確性

為什麼 DES 可以被正確解密？概念上，一個密文只能對應一個明文，這樣才符合正確解密的定義。因此不同的明文，也要產生出來不同的密文。

證明從輪替下手，部分明文 A 會保留到下一個輪替，而部分明文 A 會加密部分明文 B，假設兩個明文在 A 部分不同，則在密文部分就會不同 (因為保留)，假設是 B 部分不同，加密 (XOR 加密) 後也會不同。數學歸納法得證。

加密強度分析

因為 subkey 產生方式和換位、替換的規格是明定，與 key 無關。因此 key 長短將影響加密的強度，從現在分析 56 -bit 在數個小時內就會被解出來。

為什麼 subkey 產生方式和換位、替換的規格是明定？
因為雪崩效應的造成需要某些放大效果，因此表格要符合某些設計規則。

攻擊方法

  • Timing Attacks 加密時間攻擊，因為電腦運算的速度受輸入要件影響，如果 bit 變換數大，會導致加密時間拉長，藉以分析明文。

  • Power Attacks 偵測能源消耗，因為運算所需要的能量不同，隨著時間能到得到能源使用圖，就能分析加密過程的情況。也有為了防止這種偵測，考慮將所有運算做得一樣耗電，這有可能本末倒置。

  • Analytic Attacks 分析攻擊，從統計學的角度進行攻擊，從密文差異下手、從已知密文、明文解方程式、key 與加密結果的關聯性 … 等。

Block mode

ECB

Electronic CodeBook (ECB)，不變的 key，需要加密器和解密器，加解密的複雜度可能不同。

  • 優點：
    構造簡單、容易實做
  • 缺點：
    長時間下，容易被偵測。影像資料的差異性不大，很容易被辨識到重複性，相較於文字很容易受前後文的影響。

CBC

Cipher Block Chaining (CBC)，不變的 key，以及前一個密文會先針對明文加密。

  • 優點：
    相同明文，會因為前一個的密文不同造就出不同的密文，也就是加密器多一個新的狀態。
  • 缺點：
    • 一個密文 Ci 的錯誤，會導致兩個明文解析錯誤 (Pi & Pi+1)。
    • 第一次加密很容易被抽換 bitwise，因為每次驅動的 Initial Vector 都相同。

CFB

Cipher FeedBack (CFB)，類似 CBC，但前一個密文的結果只影響一部分的加密關係，然後將前一段密文狀態加密 key，再對明文加密。

  • 優點：
    • 支持即時 (real-time) 通訊
    • 只需要加密器，加密做兩次相當於解密。
    • 支持自同步 (self-synchronization)，即使中斷連線、訊息錯誤，可以在數個週期後再次同步運作。
    • 藉由自同步的概念，可以捨棄掉 Initial Vector。
    • 後半部的明文，可以透過週期性的部分密文建立解密狀態，支持 random access。
  • 缺點：
    • error propagation 錯誤增長，當一個訊息錯誤時，需要好幾個週期後才能修正回來，這導致中間的解密訊息都不能用。
    • 雜訊過多的情況下，不宜使用。

OFB

Output FeedBack (OFB)，類似於 CFB，將前一段的加密 key 拿回來加密，不依賴接收的密文狀態。

  • 優點：
    • 支持即時 (real-time) 通訊
    • 只需要加密器，加密做兩次相當於解密。
    • 相較於 CFB，沒有錯誤增長的情況。
    • 依序使用的 key，可以事先算出來，然後依次使用。
    • 雜訊下支持的能力好。
  • 缺點：
    • 必須一直保持同步
    • 訊息被修改時，不易被發現，只單純影響單一明文 (沒有錯誤增長)。
    • 起始狀態的 Initial Vector，不能重複使用，否則很容易被攻擊者抓到。
    • 加設沒有預先算 key，沒辦法解密出後半部的明文。

CTR

Counter (CTR)，類似於 OFB，直接利用計數器作為加密 key。

  • 優點：
    • 加解密可以平行化處理，如果加解密速度耗時，可以選擇這一種。
    • 支持 random access。
  • 缺點：
    • 必須一直保持同步
    • 訊息被修改時，不易被發現，只單純影響單一明文 (沒有錯誤增長)。
    • 起始狀態的 Initial Vector，不能重複使用，否則很容易被攻擊者抓到。
Read More +
解題區/解題區 - UVa

UVa 1013 - Island Hopping

Problem

島嶼居民要建造網路連到本島，假設現在島嶼跟島嶼之間都沒有架設網路線，現在開始建造網路，使得每一個島嶼都可以與本島或者是間接相連。

請問平均等待時間需要多少。

所有的路線，在同一時刻開始建造，以每一天一公里的速度建造所有的邊，而每一條邊都以歐幾里得距離為路線長度。

Sample Input

1
2
3
4
5
6
7
8
9
7
11 12 2500
14 17 1500
9 9 750
7 15 600
19 16 500
8 18 400
15 21 250
0

Sample Output

1
Island Group: 1 Average 3.20

Solution

一開始沒有注意到同時建造，發現這條規則後，將所有邊的長度由小到大排序，使用并查集去紀錄，找到第一個時刻連到本島的時間。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h> 
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 64;
double X[MAXN], Y[MAXN], M[MAXN];
struct Edge {
    int x, y;
    double v;
    Edge(int a = 0, int b = 0, double c = 0):
        x(a), y(b), v(c) {}
    bool operator<(const Edge &x) const {
        return v < x.v;
    }
};
vector<Edge> E;
int parent[MAXN], weight[MAXN];
double weight2[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]) {
        parent[y] = x, weight[x] += weight[y];
        weight2[x] += weight2[y];
    } else {
        parent[x] = y, weight[y] += weight[x];
        weight2[y] += weight2[x];
    }
    return 1;
}
double solve(int n) {
    sort(E.begin(), E.end());
    double div = 0, sum = 0;
    int u, v;
    for (int i = 0; i < n; i++)
        parent[i] = i, weight[i] = 1, weight2[i] = M[i], div += M[i];
        
    for (int i = 0; i < E.size(); i++) {
        u = E[i].x, v = E[i].y;
        if (findp(u) != findp(v)) {
            if (findp(u) == findp(0))
                sum += weight2[findp(v)] * E[i].v;
            if (findp(v) == findp(0))
                sum += weight2[findp(u)] * E[i].v;
            joint(u, v);
        }
    }
    return sum / div;
}
int main() {
    int n, cases = 0;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            scanf("%lf %lf %lf", &X[i], &Y[i], &M[i]);
        E.clear();
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                double v = hypot(X[i] - X[j], Y[i] - Y[j]);
                E.push_back(Edge(i, j, v));
            }
        }
        
        double ret = solve(n);
        
        printf("Island Group: %d Average %.2lf\n", ++cases, ret);
        
        puts("");
    }
    return 0;
}
/*
7
11 12 2500
14 17 1500
9 9 750
7 15 600
19 16 500
8 18 400
15 21 250
0
*/
Read More +
解題區/解題區 - UVa

UVa 1186 - Chat Rooms

Problem

聊天室會過濾過機器人般的垃圾留言，規則如下

  • 使用的單詞，出現連續子音的個數大於 5 個
  • 使用者最後送出的 10 個訊息中，有 2 行連續子音的個數大於 4 個，並且當前行也存在連續子音的個數大於 4 個。
  • 使用者最後送出的 10 個訊息中，與當前訊息相同的行數大於 1 個。

只要符合其中一條，訊息將無法發送，但是系統仍然會記錄下你曾經發送過的訊息，其他使用者無法看到被過濾的訊息。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
12
hello
how r u?
where r u from?
kjhh kh kgkjhg jhg
where r u from?
i am from London, Ontario, Canada
how r you nxw?
now
where r u from?
kjhh kh kgkjhg jhg
very good
it is very cold here.

Sample Output

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

Solution

這題算簡單，但是題目描述過於鬼畜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h> 
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <ctype.h>
using namespace std;
vector<string> toToken(string s) {
    stringstream sin(s);
    string token;
    vector<string> r;
    while (sin >> token)
        r.push_back(token);
    return r;
}
int isConsonant(char c) {
    c = tolower(c);
    if (c == 'a')	return 0;
    if (c == 'e')	return 0;
    if (c == 'i')	return 0;
    if (c == 'o')	return 0;
    if (c == 'u')	return 0;
    if (c == 'y')	return 0;
    return 1;
} 
int checkCond1(vector<string> &t) {
    for (int i = 0; i < t.size(); i++) {
        int c = 0;
        for (int j = 0; j < t[i].length(); j++) {
            if (isConsonant(t[i][j]))
                c++;
            else
                c = 0;
            if (c > 5)	return 0;
        }
    }
    return 1;
}
int checkCond2(vector<string> &t, vector<int> &D2) {
    int A = 0, B = 0;
    for (int i = 0; i < t.size(); i++) {
        int c = 0;
        for (int j = 0; j < t[i].length(); j++) {
            if (isConsonant(t[i][j]))
                c++;
            else
                c = 0;
            if (c > 4)	A = 1;
        }
    }
    for (int i = D2.size() - 1; i >= max(0, (int) D2.size() - 10); i--) {
        if (D2[i] > 0)
            B++;
    }
    return !(A && B > 2);
}
int checkCond3(string s, vector<string> &D3) {
    int A = 0;
    for (int i = D3.size() - 1; i >= max(0, (int) D3.size() - 10); i--) {
        if (D3[i] == s)
            A++;
        if (A > 1)
            return 0;
    }
    return 1;
}
int count4(vector<string> &t) {
    int A = 0;
    for (int i = 0; i < t.size(); i++) {
        int c = 0;
        for (int j = 0; j < t[i].length(); j++) {
            if (isConsonant(t[i][j]))
                c++;
            else
                c = 0;
            if (c > 4)	A = 1;
        }
    }
    return A;
}
int main() {
    int n;
    char s[256];
    while (scanf("%d", &n) == 1) {
        while (getchar() != '\n');
        vector< vector<string> > D;
        vector<int> D2;
        vector<string> D3;
        for (int i = 0; i < n; i++) { 
            gets(s);
            vector<string> t = toToken(s);
            int ok = 1;
            if (!checkCond1(t))
                ok = 0;
            else if (!checkCond2(t, D2))
                ok = 0;
            else if (!checkCond3(s, D3)) 
                ok = 0;
            D.push_back(t), D2.push_back(count4(t)), D3.push_back(s);
            puts(ok ? "y" : "n");
        } 
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1462 - Fuzzy Google Suggest

Problem

模擬 Google 的模糊搜尋，使用編輯距離找到相符的前綴單詞數量。

編輯距離的限制小於等於 2。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
4 
content 
common 
onganize 
case 
7 
c 0 
con 0 
con 2 
con 1 
com 1
comm 2 
cog 1

Sample Output

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

Solution

對於每一個詢問，沒辦法把每一個單字都拿出來嘗試過一次。

建造一個 trie，然後在 trie 上面進行編輯距離的 dp 規則，當搜尋到重覆的結果時，可以立刻返回，由於編輯距離小於等於 2，重複走訪的可能性低很多，因此用一個懶標記，如果前綴已經符合，則下次走訪就沒有必要搜索下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#define MAXCHAR 26
#define MAXS (1024)
#define MAXNODE (1048576<<2)
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
class Trie {
public:
    struct Node {
        Node *next[MAXCHAR];
        int cnt, label;
        void init() {
            cnt = label = 0;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size, cases;
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = cases = 0;
        root = getNode();
    }
    inline int toIndex(char c) {
        return c - 'a';
    }
    // merge trie
    void merge_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;
                merge_dfs(u, v);
            }
        }
    }
    void merge(const Trie &other) {
        merge_dfs(root, other.root);
    }
    // basis operation
    void insert(const char str[], int w) {
        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 += w;
        }
    }
    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;
    }
    // fuzzy find
    void fuzzy_dfs(Node *u, int idx, const char s[], int fuzzy_edit) {
    	if (fuzzy_edit < 0)			return ;
        if (u->label == cases + 1)	return ;
    	if (s[idx] == '\0') {
    		u->label = cases + 1;
    		return ;
        }
            
        if (u->label < cases)
            u->label = cases;
        for (int i = 0; i < MAXCHAR; i++) {
            if (u->next[i]) {
                if (toIndex(s[idx]) == i)
                	fuzzy_dfs(u->next[i], idx+1, s, fuzzy_edit);
                else
                	fuzzy_dfs(u->next[i], idx+1, s, fuzzy_edit-1); // replace s[idx]
                fuzzy_dfs(u->next[i], idx, s, fuzzy_edit-1); // insert s[idx]
            }
        }
        fuzzy_dfs(u, idx+1, s, fuzzy_edit-1); // delete s[idx]
    }
    int fuzzy_count(Node *u) {
    	if (u->label == cases+1)
    		return u->cnt;
    	if (u->label < cases)
    		return 0;
        int ret = 0;
        for (int i = 0; i < MAXCHAR; i++) {
            if (u->next[i])
                ret += fuzzy_count(u->next[i]);
        }
        return ret;
    }
    int fuzzyFind(const char str[], int fuzzy_edit) {
    	cases += 2;
    	fuzzy_dfs(root, 0, str, fuzzy_edit);
    	return fuzzy_count(root);
    }
    
    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;
        }
    }
} tool;
char s[MAXS];
int main() {
    int N, Q, f;
    while (scanf("%d", &N) == 1 && N) {
    	tool.init();
    	while (getchar() != '\n');
    	
    	for (int i = 0; i < N; i++) {
    		gets(s);
    		tool.insert(s, 1);
    	}
    	scanf("%d", &Q);
    	for (int i = 0; i < Q; i++) {
    		scanf("%s %d", s, &f);
    		int ret = tool.fuzzyFind(s, f);
    		printf("%d\n", ret);
    	}
    	
    	tool.free();
    }
    return 0;
}
/*
4 
content 
common 
onganize 
case 
7 
c 0 
con 0 
con 2 
con 1 
com 1
comm 2 
cog 1
 */
Read More +
解題區/解題區 - UVa

UVa 1113 - Multiple Morse Matches

Problem

給摩斯電碼的編碼方式，以及一串沒有切割的主字串，和可能使用的單字集，請問有多少不同的解析方式。

Sample Input

1
2
3
4
5
6
7
8
9
10
1
.---.--.-.-.-.---...-.---.
6
AT
TACK
TICK
ATTACK
DAWN
DUSK

Sample Output

1
2

Solution

這題很明顯地是一道 O(nm) 的動態規劃，dp[i] 表示長度為 i 的解析方法數，藉由 match S[i, j] 轉移成 dp[j] += dp[i]。

為了加速 match 的速度，先將字典集轉換成摩斯電碼，插入到 trie 中，當要做 match 時，相當於在 trie 走訪，可以高效地降低 O(m) 的嘗試。變成 O(nn)

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#define MAXCHAR 2 
#define MAXS (4096)
#define MAXNODE (1048576<<2)
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
class Trie {
public:
    struct Node {
        Node *next[MAXCHAR];
        int cnt;
        void init() {
            cnt = 0;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size, cases;
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = cases = 0;
        root = getNode();
    }
    inline int toIndex(char c) {
        return c == '.';
    }
    // merge trie
    void merge_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;
                merge_dfs(u, v);
            }
        }
    }
    void merge(const Trie &other) {
        merge_dfs(root, other.root);
    }
    // basis operation
    void insert(const char str[], int w) {
        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 += w;
    }
    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 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;
        }
    }
} tool;
char S[MAXS], T[MAXS], buf[MAXS];
string morse[] = {
    ".-", "-...", "-.-.", "-..",
    ".", "..-.", "--.", "....",
    "..", ".---", "-.-", ".-..",
    "--", "-.", "---", ".--.",
    "--.-", ".-.", "...", "-",
    "..-", "...-", ".--", "-..-",
    "-.--", "--.."};
int main() {
    int testcase, n;
    scanf("%d", &testcase);
    while (testcase--) {
    	tool.init();
    	
    	scanf("%s", S);
    	scanf("%d", &n);    	
    	for (int i = 0; i < n; i++) {
    		scanf("%s", T);
    		int m = 0;
    		for (int j = 0; T[j]; j++)
    			for (int k = 0; morse[T[j] - 'A'][k]; k++)
                    buf[m++] = morse[T[j] - 'A'][k];
            buf[m] = '\0';
            tool.insert(buf, 1);
    	}
    	
    	int len = (int) strlen(S);
    	int dp[MAXS] = {};
    	dp[0] = 1;
    	for (int i = 0; i < len; i++) {
    		Trie::Node *p = tool.root;
    		for (int j = i; j < len; j++) {
    			int u = tool.toIndex(S[j]);
    			if (p->next[u] == NULL)
                    break;
                p = p->next[u];
                dp[j+1] += dp[i] * p->cnt;
    		}
    	}
    	
    	printf("%d\n", dp[len]);	
    	if (testcase)
    		puts("");
        
        tool.free();    
    }
    return 0;
}
/*
 */
Read More +