解題區/解題區 - UVa

UVa 13038 - Directed Forest

Problem

給予一張有向森林圖，要求任兩點若有一條路徑，則兩點不可著相同顏色，請問最少著色數為何？

Sample Input

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

Sample Output

1
2
3
Case 1: 2
Case 2: 4
Case 3: 2

Solution

明顯地，最長路徑長度若為 $L$，至少需要 $L$ 個顏色，因此針對每一個樹根進行最長路徑搜索即可，又由於題目給定森林，把每一個樹根抓出來取最大值即可。複雜度 $\mathcal{O}(N)$

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 131072;
vector<int> g[MAXN];
int indeg[MAXN];
int dfs(int u) {
    int ret = 1;
    for (auto &v : g[u])
        ret = max(ret, dfs(v)+1);
    return ret;
}
int solve(int root, int N) {
    return dfs(root);
}
int main() {
    int testcase, cases = 0;
    int N, M, u, v;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &M);
        for (int i = 0; i <= N; i++)
            g[i].clear(), indeg[i] = 0;
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v), indeg[v]++;
        }
        
        int ret = 1;
        for (int i = 1; i <= N; i++) {
            if (indeg[i] == 0)
                ret = max(solve(i, N), ret);
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13005 - Blood groups

Problem

還記得孟德爾遺傳法則嗎？從血型分成 A, B, AB, O 型四種，由三個遺傳因子 A, B, i 兩兩組合而成。而外星人突破孟德爾遺傳法則，由 $N$ 個遺傳因子 (不包含隱性因子 i) 決定表徵，並且一個子代會從 $N$ 個父代分別繼承一個遺傳因子。

現在給予在場 $N$ 個父代分別有哪些遺傳因子 (若沒有告知，則剩餘都是隱性因子 i)，接下來會有 $Q$ 組詢問，問某一個遺傳因子組合是否可以被在場 $N$ 個父代組合而成。

Sample Input

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

Sample Output

1
2
3
4
5
6
7
8
N
Y
N
Y
N
Y
Y
N

Solution

每一個父代都提供一個遺傳因子，問最後能不能滿足所有匹配，顯而易見地是一題完美二分匹配。建造 source - 父代 - 遺傳因子 - sink。若某一組詢問需要父代提供遺傳因子 $x$，就去找尋有哪些父代可以提供遺傳因子，並且拉一條邊 父代 - 遺傳因子 x 流量為 1。隱性提供者特別判斷一下即可。

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
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
    public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow)) 
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
int main() {
    int N, Q, B, x;
    while (scanf("%d %d", &N, &Q) == 2) {
        set< set<int> > S;
        set<int> A[128];
        for (int i = 0; i < N; i++) {
            scanf("%d", &B);
            for (int j = 0; j < B; j++) {
                scanf("%d", &x);
                A[i].insert(x);
            }
            if (B != N)	A[i].insert(0);
        }
        
        for (int i = 0; i < Q; i++) {			
            int source = 2*N+2, sink = 2*N+3;
            g.Init(2*N+5);
            
            int used[128] = {};
            for (int j = 0; j < N; j++)	// parent
                g.Addedge(source, j, 1);
                
            scanf("%d", &B);
            for (int j = 0; j < B; j++) {
                scanf("%d", &x);
                g.Addedge(N+x, sink, 1);
                for (int k = 0; k < N; k++) {
                    if (A[k].count(x)) {
                        g.Addedge(k, N+x, 1);
                        used[k] = 1;
                    }
                }
            }
            
            int allused = 1;
            for (int j = 0; j < N; j++) {
                if (A[j].count(0) && B != N)
                    used[j] = 1;
                allused &= used[j];
            }
            
            if (!allused) {
                puts("N");
                continue;
            }
            
            int flow = g.Maxflow(source, sink);
            puts(flow == B ? "Y" : "N");
        }
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

2016 Facebook Hacker Cup Round 2

這一場是凌晨的比賽，因此沒有興趣參與，還是來翻譯一下吧！

A. Boomerang Decoration

要製作回力鏢的雙翼，需要兩個對稱形狀的翼構成，簡單來說是兩個相同字串。給予左翼 $L$ 和右翼 $R$，現在 A 和另一名小夥伴 B 同時更改左翼 $L$，使得 $L = R$，請問最少時間為何。

每一時刻，$A$ 可以選擇 $[0, x]$ 都改變成顏色 $c_1$，而 $B$ 則可以選擇 $[y, n-1]$ 全部變成顏色 $c_2$，要求 $A$ 和 $B$ 的塗色區間不可重疊，意即 $y > x$。

由於每一次塗色是前綴或者後綴，那對於 A 而言，一定是選擇 $x$ 嚴格遞減，反之對於 $y$ 是嚴格遞增，否則之前的操作會白工。藉由上述推測得知，A 和 B 塗色的區間不會重疊，得到最後一定要求左區段和右區段工作時間最大值。

目標找到 A 完成左區段 dpL[0...x] 的最少時間，以及 B 完成 dpR[y...n-1] 的最少時間，最後答案為 min(max(dpL[0...x], dpR[x+1...n-1]))。計算 dpL[] 和 dpR[] 的方法是一樣的，左右相反即可，

由於只能更改左翼，右翼不能更改，那麼一旦改了左翼位置 $x$，事實上要全部變動成右翼，變數個數 $d$ 即是右翼不同的連續相同字符片段。根據貪心策略，若左翼位置 $x$ 和右翼位置 $x$ 相同，則變動費用為 dpL[x] = dpL[x-1]，否則就是 dpL[x] = d。時間複雜度 $\mathcal{O}(n)$。

B. Carnival Coins

參與一場遊戲，獎品無限多個，遊戲規則要求一次投擲 $n$ 硬幣，硬幣出現正面的機率 $P$，只要出現 $K$ 個以上正面即可獲得一份獎品，現在手裡握有 $N$ 個硬幣，你可以邀請很多個小夥伴幫忙參與遊戲，將這 $N$ 枚硬幣分給小夥伴玩。在最佳策略下，請問獲得獎品個數的期望值為何？

現在的目標要找到怎麼分，小夥伴個數不是問題，每一個小夥伴要拿多少枚硬幣是主要問題。定義 dp[i][j] 為投擲 $i$ 枚硬幣恰好 $j$ 枚正面的機率，遞推得到 dp[i][j] = dp[i-1][j-1]*P + dp[i-1][j]*(1-P)。由於大於等於 $K$ 枚只能獲得一份獎品，定義 dpw[i] 為投擲 $i$ 枚硬幣獲得一份獎品的期望值，遞推得到 dpw[i] = sum(dp[i][j]), j >= K。

最後，定義 dpw[i] 為分配 $i$ 枚硬幣給小夥伴的最大期望值個數，得到 dpw[i] = max(dpw[i-j]+dpv[j])。每一步都是 $\mathcal{O}(N^2)$，時間複雜度 $\mathcal{O}(N^2)$。

C. Snakes and Ladders

有一個奇怪的收藏家，收集很多梯子，每一個梯子位於水平位置 $x_i$ 高度為 $H_i$，然而當地特有蛇種喜歡懸掛在兩個等高 $H_p$ 的梯子之間，並且兩個梯子中間的其餘梯子都滿足 $H_r \le H_p$。若蛇懸掛在兩個距離 $L$ 的梯子之間，則需要餵養 $L^2$ 單位的飼料，請問飼主一天要餵多少單位的飼料。

搭配組合的數學計算，由於懸掛的組合保證中間不會有高於兩側，則可以用單調堆完成紀錄，由左而右依序加入梯子，在單調堆中維護梯子高度遞減的位置。由於等高的梯子個數需要合併，否則沒辦法計算 $L$，為了計算 $L^2$。當從左而右加入梯子時，往左找到合法的等高梯子，由於得知 $\sum (X - x_i)^2$，把式子展開得到 $nX^2 - 2X \sum x_i + \sum x_i^2$，因此需要對於每一個高度，要合併 $\sum x_i$ 和 $\sum x_i^2$。

由於每一個元素至多 push 和 pop 一次，時間複雜度 $\mathcal{O}(N)$。

D. Costly Labels

在一棵 $N$ 個節點的無根樹，每一個節點可填入 $K$ 種顏色，對於每一個節點填不同顏色都有不同花費，若一個節點 $u$ 的鄰居中有兩個以上節點顏色相同，則 $u$ 需要額外花費 $P$ 來維持平衡。請問著色的最少花費為何。

若不考慮額外花費 $P$ 這一點，這題就是再簡單不過的貪心。從鴿籠原理知道，若一個點的鄰居大於 $K$ 個，則他必然存在兩個相同顏色的鄰居，一定需要花費 $P$ 維持平衡。由於圖給定一棵樹，自然而然地就設想到樹形 dp，維護子樹的最少花費進行合併。

由於子樹的根著色不用考慮，但方案合併要考慮父節點要著色的方案，因此得到狀態 dp[u][c1][c2] 節點 $u$ 著色 $c_1$，$u$ 的父節點著色 $c_2$。分成兩種狀態轉移，是否要花費 $P$，若 $u$ 花費 $P$，直接合併子樹 $v$ 的最小值 dp[v][?][c1]。若不花費 $P$，勢必要讓子樹都填入不同顏色，由於每一個節點配對顏色花費都不同，最小化著色方案是標準的二分圖帶權匹配，可以用 KM 算法或者是最少費用流完成，只要排除預設 $u$ 的父節點顏色建圖即可，幸好不花費的數值都小於等於 $K$，KM 算法提供 $\mathcal{O}(K^3)$。整體的時間複雜度最慘 $\mathcal{O}(N \times K^2 \times K^3)$。

Solution

A. Boomerang Decoration

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 <bits/stdc++.h>
using namespace std;
const int MAXS = 131072;
char sa[MAXS], sb[MAXS];
int Ldp[MAXS], Rdp[MAXS];
int main() {
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        scanf("%s %s", sa+1, sb+1);
        
        memset(Ldp, 0, sizeof(Ldp));
        memset(Rdp, 0, sizeof(Rdp));
        
        int c;
        c = 0;
        for (int i = 1; i <= n; i++) {
            if (sb[i] != sb[i-1])
                c++;
            if (sa[i] != sb[i])
                Ldp[i] = c;
            else
                Ldp[i] = Ldp[i-1];
        }
        c = 0;
        for (int i = n, j = 1; i >= 1; i--, j++) {
            if (sb[i] != sb[i+1])
                c++;
            if (sa[i] != sb[i])
                Rdp[j] = c;
            else
                Rdp[j] = Rdp[j-1];
        }
        int ret = n;
        for (int i = 1; i <= n; i++) {
            ret = min(ret, max(Ldp[i], Rdp[n-i]));
        }
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}

B. Carnival Coins

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4096;
double dp[MAXN][MAXN], dpw[MAXN], dpv[MAXN];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, K;
        double P;
        scanf("%d %d %lf", &N, &K, &P);
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= i; j++) {
                dp[i+1][j] += dp[i][j] * (1-P);
                dp[i+1][j+1] += dp[i][j] * P;
            }
            dpw[i] = 0;
            for (int j = K; j <= i; j++)
                dpw[i] += dp[i][j];
        }
        
        memset(dpv, 0, sizeof(dpv));
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= i; j++) {
                dpv[i] = max(dpv[i], dpw[j] + dpv[i-j]);
            }
        }
        
        double ret = dpv[N];
        printf("Case #%d: %.9lf\n", ++cases, ret);
    }
    return 0;
}

C. Snakes and Ladders

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
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
struct State {
    int H;
    long long sum, sqsum, n;
    State(int H, long long sum = 0, 
        long long sqsum = 0, long long n = 0):
        H(H), sum(sum), sqsum(sqsum), n(n) {}
};
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, x, h;
        scanf("%d", &n);
        vector<std::pair<int, int>> A;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &h);
            A.push_back(make_pair(x, h));
        }
        sort(A.begin(), A.end());
        long long ret = 0;
        stack<State> stk;
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && stk.top().H < A[i].second)
                stk.pop();
            if (!stk.empty() && stk.top().H == A[i].second) {
                State e = stk.top();
                long long X = A[i].first;
                long long N = e.n;
                long long S = N*X%MOD * X%MOD;
                S = (S - X*2%MOD*e.sum%MOD + e.sqsum)%MOD;
                e.sum = (e.sum + X)%MOD;
                e.sqsum = (e.sqsum + X*X%MOD)%MOD;
                e.n++;
                ret = (ret + S)%MOD;
                stk.pop(), stk.push(e);
            } else {
                long long X = A[i].first;
                stk.push(State(A[i].second, X, X*X%MOD, 1));
            }
        }
        ret = (ret + MOD)%MOD;
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

D. Costly Labels

版本 1

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 128;
const int MAXM = 1048576;
struct Node {
    int x, y, cap;
    int cost;// x->y, v
    int next;
} edge[MAXM];
class MinCost {
public:
    int e, head[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
    int dis[MAXN];
    int n;
    const int INF = 0x3f3f3f3f;
    void Addedge(int x, int y, int cap, int cost) {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].next = head[x], head[x] = e++;
        edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
        edge[e].next = head[y], head[y] = e++;
    }
    pair<int, int> mincost(int s, int t) {
        int mncost = 0;
        int flow, totflow = 0;
        int i, x, y;
        while(1) {
        	for (int i = 0; i < n; i++)
        		dis[i] = INF;
            int oo = dis[0];
            dis[s] = 0;
            deque<int> Q;
            Q.push_front(s);
            while(!Q.empty()) {
                x = Q.front(), Q.pop_front();
                inq[x] = 0;
                for(i = head[x]; i != -1; i = edge[i].next) {
                    y = edge[i].y;
                    if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                        dis[y] = dis[x] + edge[i].cost;
                        pre[y] = x, record[y] = i;
                        if(inq[y] == 0) {
                            inq[y] = 1;
                            if(Q.size() && dis[Q.front()] > dis[y])
                                Q.push_front(y);
                            else
                                Q.push_back(y);
                        }
                    }
                }
            }
            if(dis[t] == oo)
                break;
            flow = 0x3f3f3f3f;
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                flow = min(flow, edge[ri].cap);
            }
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                edge[ri].cap -= flow;
                edge[ri^1].cap += flow;
                edge[ri^1].cost = -edge[ri].cost;
            }
            totflow += flow;
            mncost += dis[t] * flow;
        }
        return make_pair(mncost, totflow);
    }
    void init(int n) {
    	this->n = n;
        e = 0;
        for (int i = 0; i <= n; i++)
            head[i] = -1;
    }
} g;
int N, K, P;
int costG[1024][32];
vector<int> treeG[1024];
long long dp[1024][32];	// dp[subtree: u][color of u: c] = mincost, don't care penalty P
long long dpv[1024];
void dfs(int u, int p) {
    for (int i = 0; i < K; i++)
        dp[u][i] = costG[u][i];
    for (auto &v : treeG[u]) {
        if (v == p)	continue;
        dfs(v, u);
        
        int cost = P;
        for (auto &adj_v : treeG[v]) {
            if (adj_v == u)	continue;
            cost += dpv[adj_v];
        }
        
        if (treeG[v].size() > K) {
            for (int i = 0; i < K; i++)
                dp[u][i] += cost;
        } else {
            // find disjoint-color by maximum weighted matching
            for (int i = 0; i < K; i++) {	// u-color
                int source = 0, sink = treeG[v].size()+K+1;
                g.init(treeG[v].size()+K+2);
                for (int j = 0; j < K; j++) {
                    if (j == i)	continue;
                    g.Addedge(treeG[v].size()+j+1, sink, 1, 0);
                }
                for (int j = 0; j < treeG[v].size(); j++) {
                    int adj_v = treeG[v][j];
                    if (adj_v == u)	continue;
                    for (int k = 0; k < K; k++) {
                        if (k == i)	continue;
                        g.Addedge(j+1, treeG[v].size()+k+1, 1, dp[adj_v][k]);
                    }
                    g.Addedge(source, j+1, 1, 0);
                }
                pair<int, int> mm = g.mincost(source, sink);
                dp[u][i] += min(cost, mm.first);
            }
        }
    }
    dpv[u] = INT_MAX;
    for (int i = 0; i < K; i++)
        dpv[u] = min(dpv[u], dp[u][i]);
}
long long final(int v) {
    int cost = P;
    for (auto &adj_v : treeG[v])
        cost += dpv[adj_v];
    
    if (treeG[v].size() > K)
        return cost;
    // find disjoint-color by maximum weighted matching
    for (int i = 0; i < K; i++) {	// u-color
        int source = 0, sink = treeG[v].size() + K + 1;
        g.init(treeG[v].size()+K+2);
        for (int j = 0; j < K; j++) {
            g.Addedge(j+treeG[v].size()+1, sink, 1, 0);
        }
        for (int j = 0; j < treeG[v].size(); j++) {
            int adj_v = treeG[v][j];
            for (int k = 0; k < K; k++)
                g.Addedge(j+1, treeG[v].size()+k+1, 1, dp[adj_v][k]);
            g.Addedge(source, j+1, 1, 0);
        }
        
        pair<int, int> mm = g.mincost(source, sink);
        cost = min(cost, mm.first);
    }
    return cost;
}
int main() {
    int testcase, cases = 0;	
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &K, &P);
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < K; j++) {
                scanf("%d", &costG[i][j]);
            }
        }
        
        for (int i = 1; i <= N; i++)
            treeG[i].clear();
        for (int i = 1; i < N; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
            treeG[x].push_back(y);
            treeG[y].push_back(x);
        }
        
        dfs(1, -1);
        
        long long ret = INT_MAX;
        for (int i = 0; i < K; i++)
            ret = min(ret, dp[1][i]);
        ret += final(1);
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

版本 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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 128;
const int MAXM = 1048576;
struct Node {
    int x, y, cap;
    int cost;// x->y, v
    int next;
} edge[MAXM];
class MinCost {
public:
    int e, head[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
    int dis[MAXN];
    int n;
    const int INF = 0x3f3f3f3f;
    void Addedge(int x, int y, int cap, int cost) {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].next = head[x], head[x] = e++;
        edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
        edge[e].next = head[y], head[y] = e++;
    }
    pair<int, int> mincost(int s, int t) {
        int mncost = 0;
        int flow, totflow = 0;
        int i, x, y;
        while(1) {
        	for (int i = 0; i < n; i++)
        		dis[i] = INF;
            int oo = dis[0];
            dis[s] = 0;
            deque<int> Q;
            Q.push_front(s);
            while(!Q.empty()) {
                x = Q.front(), Q.pop_front();
                inq[x] = 0;
                for(i = head[x]; i != -1; i = edge[i].next) {
                    y = edge[i].y;
                    if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                        dis[y] = dis[x] + edge[i].cost;
                        pre[y] = x, record[y] = i;
                        if(inq[y] == 0) {
                            inq[y] = 1;
                            if(Q.size() && dis[Q.front()] > dis[y])
                                Q.push_front(y);
                            else
                                Q.push_back(y);
                        }
                    }
                }
            }
            if(dis[t] == oo)
                break;
            flow = 0x3f3f3f3f;
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                flow = min(flow, edge[ri].cap);
            }
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                edge[ri].cap -= flow;
                edge[ri^1].cap += flow;
                edge[ri^1].cost = -edge[ri].cost;
            }
            totflow += flow;
            mncost += dis[t] * flow;
        }
        return make_pair(mncost, totflow);
    }
    void init(int n) {
    	this->n = n;
        e = 0;
        for (int i = 0; i <= n; i++)
            head[i] = -1;
    }
} g;
int N, K, P;
int costG[1024][32];
vector<int> treeG[1024];
long long dp[1024][32][32];	// dp[subtree: u][color of u: c][color of u'parent: c]
long long dpv[1024][32];
void dfs(int u, int p) {
    for (auto &v : treeG[u]) {
        if (v == p)	continue;
        dfs(v, u);
    }
    
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            int cost = costG[u][i] + P;
            for (auto &v : treeG[u]) {
                if (v == p)	continue;
                cost += dpv[v][i];
            }
            dp[u][i][j] = cost;
            
            if (treeG[u].size() > K)
                continue;
                
            int source = 0, sink = treeG[u].size()+K+1;
            g.init(treeG[u].size()+K+2);
            for (int k = 0; k < K; k++) {
                if (k == j && p != -1)	continue;	// parent color
                g.Addedge(treeG[u].size()+k+1, sink, 1, 0);
            }
            int branch = 0;
            for (int it = 0; it < treeG[u].size(); it++) {
                int v = treeG[u][it];
                if (v == p)	continue;
                branch++;
                for (int k = 0; k < K; k++) {
                    if (k == j && p != -1)	continue;
                    g.Addedge(it+1, treeG[u].size()+k+1, 1, dp[v][k][i]);
                }
                g.Addedge(source, it+1, 1, 0);
            }
            
            pair<int, int> mm = g.mincost(source, sink);
            if (mm.second != branch)
                continue;
            dp[u][i][j] = min(dp[u][i][j], (long long) mm.first + costG[u][i]);
        }
    }
    
    for (int i = 0; i < K; i++) {
        dpv[u][i] = INT_MAX;
        for (int j = 0; j < K; j++)
            dpv[u][i] = min(dpv[u][i], dp[u][j][i]);
    }
}
int main() {
    int testcase, cases = 0;	
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &K, &P);
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < K; j++) {
                scanf("%d", &costG[i][j]);
            }
        }
        
        for (int i = 1; i <= N; i++)
            treeG[i].clear();
        for (int i = 1; i < N; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
            treeG[x].push_back(y);
            treeG[y].push_back(x);
        }
        
        dfs(1, -1);
        
        long long ret = INT_MAX;
        for (int i = 0; i < K; i++)
            for (int j = 0; j < K; j++)
                ret = min(ret, dp[1][i][j]);
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b685. 高中組第五題-課堂抽籤

Problem

$N$ 個人抽籤決定跟誰同一組，請問在某些籤已經決定好的情況下，求恰好分成 $M$ 組的抽籤方法數。

轉換成 $N$ 個節點，恰好形成 $M$ 個環的方法數。

## Sample Input ##

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

Sample Output

1
2
0
1

Solution

在此特別感謝 lwc (Wei Chen Liao) 提供思路。

手動暴力打表後，上網蒐到 A125714 Alfred Moessner’s factorial triangle. 恰好是這個數列的答案。

由於每一個人的籤不重複，若把他抽到的籤當作指向出去的邊，那麼保證這一個點恰好一個出邊和一個入邊。當所有籤抽滿後，圖看起來是好幾個環。

遞迴定義 dp[i][j] 表示有 $i$ 個節點和 $j$ 個環。考慮新加入得點要抽到哪一個籤，加入到 $j$ 個環的情況，則是把某一個環的某一個位置打開加入，或者自身形成一個環，最後得到 dp[i][j] = dp[i-1][j-1] + (i-1)*dp[i-1][j]

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 <bits/stdc++.h>
using namespace std;
const int MAXN = 1024;
const long long MOD = 1000007;
long long dp[MAXN][MAXN];
int A[MAXN], used[MAXN];
int main() {
    dp[0][0] = dp[1][1] = 1;
    for (int i = 2; i < MAXN; i++) {
        for (int j = 1; j <= i; j++)
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * (i-1))%MOD;
    }
    int testcase, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        int a = n, b = 0;
        memset(used, 0, sizeof(used));
        for (int i = 1; i <= n; i++) {
            if (used[i])
                continue;
            int x = i, cnt = 0;
            while (x && used[x] == 0)
                used[x] = 1, x = A[x], cnt++;
            a -= cnt-1;
            if (x == i)	m--;
            if (x == 0)	b++;
        }
        if (m < 0)
            puts("0");
        else
            printf("%lld\n", dp[b][m]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12415 - Digit Patterns

Problem

讀入一個 regex，一個主字串 $s$，請問有不同的 $i$ 滿足 $s$ 的子字串 s[j...i] 匹配 regex。

正規表達式長度最多 500，主字串 $s$ 長度最多 $10^7$。

Sample Input

1
2
3
4
6 1(2+3)*4
012345
2 00*(10+100)*
00100

Sample Output

1
2
5
1 2 4 5

Solution

隔了一年才解決它，這一題很明顯地在編譯器的範疇，要將一個 regex 轉換成 NFA 甚至 DFA。一開始設想轉換成 DFA，但長度 500 轉換成 DFA，用狀態壓縮的方式狀態增長非常大，不知道是不是指數成長，上傳就得到 Runtime Error。

將 regex 轉換成 NFA (nondeterministic finite automata) 並不難，但節點會很多且存在很多 $a \overset{\varepsilon}{\rightarrow} b$ 這種類型的邊。在解析 regular expression 時，用線性 $\mathcal{O}(n)$ 或者是 $\mathcal{O}(n^2)$ 都沒關係。因為在計算答案至少 $\mathcal{O}(10^7)$。

得到最原生的 NFA 後，接下來要思考怎麼找到匹配的子字串 $s_{j, i}$，維護可轉移的狀態集合 $S$，若當前 $S$ 中存在 acceptable 狀態，則找到一個 $i$ 解。依序加入字符 $s_i$，維護 $S$ 的做法如下：

  • 將起始狀態丟入 $S$，計算閉包 (closure)，也就是所有 $a \overset{\varepsilon}{\rightarrow} b$ 能連到的狀態都應該被丟入 $S$。
  • 定義下一個狀態集合 $S'$，在 $S$ 中的每一個狀態 $q$，都嘗試藉由 $s_i$ 轉移到 $q'$，將所有 $q'$ 丟入 $S'$ 中。
  • 若 $\text{closure}(S')$ 存在 acceptable 狀態，則 $i$ 是一組解。
  • $S = \text{closure}(S' + \mathit{q}_{start})$。

上面的算法並沒有錯，但原生的 NFA 產生方式在計算閉包時很慢，過多的邊和重複狀態導致。因此需要重建邊，預處理每一個字符轉移，移除所有 $a \overset{\varepsilon}{\rightarrow} b$，這麼一來就能在時限內通過。時間複雜度 $\mathcal{O}(|s| \times (\text{state} + \text{edge}))$

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
#include <bits/stdc++.h>
using namespace std;
const int MAXSTATE = 32767;
const int epsilon = 0;
int toIndex(char c) {
    return c - '0' + 1;
}
struct State {
    vector<State*> trans[11];
    int ac, label;
    State() {
        ac = label = 0;
        for (int i = 0; i < 11; i++)
            trans[i].clear();
    }
} _mem[MAXSTATE];
int nodesize = 0;
State *newState() {
    assert(nodesize < MAXSTATE);
    State *p = &_mem[nodesize++];
    *p = State();
    return p;
}
struct NFA {
    State *st, *ac;
    NFA() {
        st = ac = NULL;
    }
    NFA(char c) {
        st = newState(), ac = newState();
        ac->ac = 1;
        st->trans[toIndex(c)].push_back(ac);
    }
    NFA(NFA L, char c) {	// (A)*
        st = ac = NULL;
        if (c != '*')
            return ;
        st = newState(), ac = newState();
        ac->ac = 1;
        st->trans[epsilon].push_back(L.st);
        L.st->trans[epsilon].push_back(L.ac);
        L.ac->trans[epsilon].push_back(L.st);
        L.ac->trans[epsilon].push_back(ac);
        L.ac->ac = 0;
    }
    NFA(NFA L, NFA R, char c) {
        if (R.st == NULL) {
            st = L.st, ac = L.ac;
            return;
        }
        if (c == '|') {
            st = newState(), ac = newState();
            ac->ac = 1;
            st->trans[epsilon].push_back(L.st);
            st->trans[epsilon].push_back(R.st);
            L.ac->trans[epsilon].push_back(ac);
            R.ac->trans[epsilon].push_back(ac);
            L.ac->ac = R.ac->ac = 0;
        } else if (c == '&') {
            st = newState(), ac = newState();
            ac->ac = 1;
            st->trans[epsilon].push_back(L.st);
            L.ac->trans[epsilon].push_back(R.st);
            R.ac->trans[epsilon].push_back(ac);
            L.ac->ac = R.ac->ac = 0;
        }
    }
};
NFA parser(string exp) {
    if (exp.length() == 0)
        return NFA();
    if (exp.length() == 1)
        return NFA(exp[0]);
        
    int l = 0, pos = -1;
    for (int i = 0; i < exp.length(); i++) {
        if (exp[i] == '(') {
            l++;
        } else if (exp[i] == ')') {
            l--;
        } else if (exp[i] == '+') {
            if (l == 0) {
                pos = i;
                break;
            }
        }
    }
    
    if (pos != -1) {
        NFA L = parser(exp.substr(0, pos));
        NFA R = parser(exp.substr(pos+1));
        return NFA(L, R, '|');
    }
    
    int hasStar = 0;
    string ls, rs;
    
    if (exp[0] == '(') {
        for (int i = 0; i < exp.length(); i++) {
            if (exp[i] == '(') {
                l++;
            } else if (exp[i] == ')') {
                l--;
                if (l == 0) {	// (...)...
                    if (i+1 < exp.length() && exp[i+1] == '*') {	// (...)*...
                        hasStar = 1;
                        ls = exp.substr(1, i-1), rs = exp.substr(i+2);
                    } else {	// (...)...
                        ls = exp.substr(1, i-1), rs = exp.substr(i+1);
                    }
                    break;
                }
            }
        }
    } else {	// ...(...) or ...*... or ......
        for (int i = 0; i < exp.length(); i++) {
            if (exp[i] == '(') {
                l++;
            } else if (exp[i] == ')') {
                l--;
            }
            if (l == 0) {
                if (i+1 < exp.length() && exp[i+1] == '*') {
                    hasStar = 1;
                    ls = exp.substr(0, i+1), rs = exp.substr(i+2);
                } else {
                    ls = exp.substr(0, i+1), rs = exp.substr(i+1);
                }
                break;
            }
        }
    }
    for (int i = 0; rs.length() > 0; ) {
        while (i < rs.length() && rs[i] == '*')
            i++;
        rs = rs.substr(i);
        break;
    }
    NFA L = parser(ls);
    NFA R = parser(rs);
    if (hasStar)
        L = NFA(L, '*');
    return NFA(L, R, '&');
}
State *gmap[MAXSTATE];
int relabel(NFA A) {
    int size = 0;
    State *u, *v;
    queue<State*> Q;
    Q.push(A.st), A.st->label = ++size;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        gmap[u->label] = u;
        for (int it = 0; it < 11; it++) {
        	for (int i = 0; i < u->trans[it].size(); i++) {
        		v = u->trans[it][i];
                if (v->label == 0) {
                    v->label = ++size;
                    Q.push(v);
                }
            }
        }
    }
    return size;
}
char s[16777216];
int used[MAXSTATE], ACable[MAXSTATE];
int closure(vector<int> &A, int x, int cases) {
    queue<int> Q;
    State *u;
    int accept = 0;
    if (used[x] != cases)
        A.push_back(x), used[x] = cases;
    Q.push(x);
    while (!Q.empty()) {
        x = Q.front(), Q.pop();
        u = gmap[x];
        accept |= u->ac;
        if (u->trans[epsilon].size() == 0)
            continue;
        for (auto &y : u->trans[epsilon]) {
            if (used[y->label] != cases) {
                Q.push(y->label), used[y->label] = cases;
                A.push_back(y->label);
            }
        }
    }
    return accept;
}
void rebuild(int n, int ctype) {
    memset(ACable, 0, sizeof(ACable));
    memset(used, 0, sizeof(used));
    int cases = 0;
    for (int i = 1; i <= n; i++) {
        cases++;
        vector<int> cc;
        closure(cc, i, cases);
        for (int j = 1; j <= ctype; j++) {
            set<int> S;
            for (int k = 0; k < cc.size(); k++) {
                State *u = gmap[cc[k]];
                for (auto &p : u->trans[j])
                    S.insert(p->label);
                ACable[i] |= u->ac;
            }
            State *u = gmap[i];
            u->trans[j].clear();
            for (auto &x : S)
                u->trans[j].push_back(gmap[x]);
        }
    }
}
int main() {
    int n, m;
    char regex[512];
    while (scanf("%d %s", &n, regex) == 2) {
        nodesize = 0;	// global
        NFA nfa = parser(regex);
        m = relabel(nfa);
        rebuild(m, n);
        scanf("%s", s);
        
        memset(used, 0, sizeof(used));
        int cases = 0, flag = 0;
        
        vector<int> A;
        cases++;
        A.push_back(1);
        for (int i = 0; s[i]; i++) {
            vector<int> next;
            cases++;
            int accept = 0;
            for (int j = 0; j < A.size(); j++) {
                int x = A[j];
                State *u = gmap[x];
                if (u->trans[toIndex(s[i])].size() == 0)
                    continue;
                for (auto &y : u->trans[toIndex(s[i])]) {
                    if (used[y->label] != cases) {
                        used[y->label] = cases, next.push_back(y->label);
                        accept |= ACable[y->label];
                    }
                }
            }
            if (used[1] != cases)
                used[1] = cases, next.push_back(1);
            A = next;
            if (accept) {
                if (flag)	putchar(' ');
                flag = 1;
                printf("%d", i+1);
            }
        }
        puts("");
    }
    return 0;
}
/*
6 1(2+3)*4
012345
2 00*(10+100)*
00100
*/
Read More +
解題區/出題解題

[讀檔操作] 有限記憶體排序數組

背景

現在的系統架構中，內存 (Memory，台灣翻譯：記憶體，大陸翻譯：內存) 的大小仍無法完全像硬碟機一樣。如檔案大小 64GB，內存只有 4GB，處理檔案無法全部 In Memory，當然最近的硬體技術也逐漸朝著 All In Memory 的方式進行加速。回過頭來，在內存不足的情況下，來練習如何處理檔案大小遠大於內存的情況吧。

題目描述

給予一個 binary file 的檔案名稱，裡面用 4 個位元組為一個 signed 32-bit 整數，有數個直到 EOF，請排序後以 binary mode 導入 stdout 輸出。

輸入格式

標準輸入串流只有一行一個字串，表示檔案名稱 $F$。檔案大小最多 16 MB，而你的程序被限制最多使用 4 MB 的內存。

每個整數 $x$，限制條件 $0 \le x \le 10^9$

輸出格式

輸出在標準串流以 binary mode 下，請避開使用 console 輸出，會因為特殊字元 (如 「嗶」一聲) 導致系統嚴重當機。

範例輸入

1
1.dat

範例輸出

1
... binary mode 無法顯示

提示

download p10068-in.dat

1
2
3
4
5
6
7
8
9
morris821028@morris821028-PC MINGW64 ~/Desktop/10068
$ ./sort2.exe >test.out
1.dat
morris821028@morris821028-PC MINGW64 ~/Desktop/10068
$ xxd test.out
00000000: 0000 0000 0100 0000 0100 0000 0100 0000  ................
00000010: 0300 0000 0400 0000 0500 0000 0500 0000  ................
00000020: 0800 0000 0900 0000                      ........

1.dat 以 binary file 儲存 10 個 4 bytes 整數，依序為 5, 9, 3, 5, 0, 1, 1, 8, 4, 1，排序後即為 0, 1, 1, 1, 3, 4, 5, 5, 8, 9。

由於限制內存使用量，無法寫入暫存檔案，可利用多次讀檔完成。

Solution

乍看之下，這一題是最常見的 external sort (外部排序)，外部排序需要額外寫檔案，由於記憶體用量計算，一寫檔案會計算到使用的記憶體中，實際上這一題不寫檔也是能解決的。

  • 給定要排序的數據範圍
  • 二分搜尋可容納的排序範圍，利用平衡樹或者 hash 來完成計算 <某整數, 某整數出現個數>
  • 將可容納到 hash 的所有數字排序，再將其直接寫到輸出檔案。
  • 不斷地遞增二分搜尋的左邊邊界。
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define swap(x, y) {int t; t = x, x = y, y = t;}
int fsize(FILE *fp) {
    int prev = ftell(fp);
    fseek(fp, 0L, SEEK_END);
    int size = ftell(fp);
    fseek(fp, prev, SEEK_SET);
    return size;
}
#define USAGEMEM (2<<20)
#define MAXELE ((2<<20)/8)
int A[MAXELE];
#define HSIZE 100007
#define HNODE 50000
typedef struct HashNode {
    int f, cnt;
    struct HashNode *next;
} HashNode;
HashNode *hhead[HSIZE], hnodes[HNODE];
int nodesize = 0;
int cmp(const void *x, const void *y) {
    return ((HashNode*) x)->f - ((HashNode*) y)->f;
}
unsigned int hash(int f) {
    unsigned int a = 63689, b = 378551;
    unsigned int value = 0;
    value = value * a + f, a = a * b;
    return value;
} 
void initHash() {
    memset(hhead, 0, sizeof(hhead));
    nodesize = 0;
}
int insertHash(int f) {
    unsigned int hidx = hash(f)%HSIZE;
    for (HashNode *p = hhead[hidx]; p != NULL; p = p->next) {
        if (f == p->f) {
        	p->cnt++;
            return 1;
        }
    }
    if (nodesize >= HNODE)	return 0;
    HashNode s = {.f = f, .cnt = 1, .next = NULL};
    hnodes[nodesize] = s;
    hnodes[nodesize].next = hhead[hidx];
    hhead[hidx] = &hnodes[nodesize];
    nodesize++;
    return 1;
}
int merge_int(FILE *fp, int l, int r) {
    initHash();
    int ret = 0, x, n = 0;
    fseek(fp, 0, SEEK_SET);
    while ((n = fread(A, sizeof(int), MAXELE, fp))) {
        for (int i = 0; i < n; i++) {
            if (A[i] >= l && A[i] <= r) {
                if (!insertHash(A[i]))
                    return 0;
            }
        }
    }
    return 1;
}
#ifdef _WIN32
#include <fcntl.h>
#endif
int block_process(FILE *fp) {
    int base = 0;
    int l, r, mid, ret;
    l = base, r = 1000000000, ret = 0;
#ifdef _WIN32
    if (setmode(fileno(stdout), O_BINARY) == -1) {
        perror("Cannot set stdout to binary mode");
        return 2;
    }
#endif
#ifdef __linux__
    FILE *const out = fdopen(dup(fileno(stdout)), "wb");
#endif
    while (l <= r) {
        mid = (l + r)/2;
        int status = merge_int(fp, base, mid);
        if (status == 1) {
            l = mid + 1, r = 1000000000;
            base = mid + 1;
            qsort(hnodes, nodesize, sizeof(HashNode), cmp);
            for (int i = 0; i < nodesize; i++) {
                int x = hnodes[i].f;
                for (int j = hnodes[i].cnt-1; j >= 0; j--) {
#ifdef _WIN32
                    fwrite(&x, sizeof(int), 1, stdout);
#endif
#ifdef __linux__
                    fwrite(&x, sizeof(int), 1, out);
#endif
                }
                ret += hnodes[i].cnt;
            }
        } else {
            r = mid - 1;
        }
    }
    return ret;
}
int main() {
    char fName[128];
    scanf("%s", fName);
    FILE *fin = fopen(fName, "rb");
    
    int n = fsize(fin) / sizeof(int);
    block_process(fin);
    return 0;
}
Read More +
解題區/出題解題

[讀檔操作] 有限記憶體找中位數

背景

現在的系統架構中，內存 (Memory，台灣翻譯：記憶體，大陸翻譯：內存) 的大小仍無法完全像硬碟機一樣。如檔案大小 64GB，內存只有 4GB，處理檔案無法全部 In Memory，當然最近的硬體技術也逐漸朝著 All In Memory 的方式進行加速。回過頭來，在內存不足的情況下，來練習如何處理檔案大小遠大於內存的情況吧。

題目描述

給予一個 binary file 的檔案名稱，裡面用 4 個位元組為一個 signed 32-bits 整數，有數個直到 EOF，保證恰好有奇數個，請輸出中位數為何？

輸入格式

標準輸入串流只有一行一個字串，表示檔案名稱 $F$。檔案大小最多 16 MB，而你的程序被限制最多使用 4 MB 的內存。

每個整數 $x$，限制條件 $0 \le x \le 10^9$

輸出格式

輸出一行整數 $Median$ 為 binary file 的中位數。

範例輸入

1
p10067-in.dat

範例輸出

1
97537111

提示

二分搜尋，分桶

download p10067-in.dat

p10067-in.dat

1
2
3
10825098
97537111
208681850

Solution

這一個問題很久以前見過，對岸通常叫做「海量資料找中位數」約束在記憶體不夠的情況下，如何高效率找到中位數，操作時允許重複讀檔。

遲遲沒有 Online Judge 進行記憶體用量檢測以及開放讀寫檔案，如今有機會擔任台灣大學計算機程式設計的課程助教，架了一個允許亂來的 Online Judge - Judge Girl (中文翻譯：批改娘系統)，讀寫檔案也不會被封鎖！洽詢 網站，目前只針對課堂學生開放。

回到問題，題目給訂 16MB 的整數序列，最多 $n = 4 \times 10^6$，由於記憶體不足沒辦法直接宣告陣列大小為 $n$ 的整數陣列，又由於數字可能會重複，就沒辦法利用 bitmask 進行壓縮，只能倚靠不斷地讀檔案進行計算。若以數值範圍 $[0, V]$，大致放分成兩種策略

  • 二分搜尋 (AC, 250ms)，效率 $\mathcal{O}(V \log V)$，開檔次數 $\mathcal{O}(\log V)$。
  • 分桶算法 (AC, 70ms)，效率 $\mathcal{O}(N)$，開檔次數 $\mathcal{O}(1)$。

讀取檔案時，在有限記憶體空間，配置一塊作為緩衝區，一次讀入一坨子序列，一個一個讀取效率非常差，別輕忽從磁碟讀取資料的速度。剩餘空間再進行紀錄用途。從效能比較 二分搜尋 慢於 分桶算法。

二分搜尋

二分答案 $x$，接著線性掃描序列，計算有多少個整數小於等於 $x$，藉此找到中位數。

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>
int fsize(FILE *fp) {
    int prev = ftell(fp);
    fseek(fp, 0L, SEEK_END);
    int size = ftell(fp);
    fseek(fp, prev, SEEK_SET);
    return size;
}
#define MAXELE (3<<20)/4
int countLess(FILE *fp, int ans) {
    static int A[MAXELE];
    int ret = 0, x, n = 0;
    fseek(fp, 0, SEEK_SET);
    while ((n = fread(A, sizeof(int), MAXELE, fp))) {
        for (int i = 0; i < n; i++)
            ret += A[i] <= ans;
    }
    return ret;
}
int main() {
    char fName[128];
    scanf("%s", fName);
    FILE *fin = fopen(fName, "rb");
    
    int n = fsize(fin) / sizeof(int);
    
    int m = n/2 + 1;
    int l = 0, r = 1000000000, mid, ret = 0;
    
    while (l <= r) {
        mid = (l + r)/2;
        int tn = countLess(fin, mid);
        if (tn < m)
            l = mid + 1, ret = mid+1;
        else
            r = mid - 1;
    }
    printf("%d\n", ret);
    return 0;
}

分桶算法

分桶算法分成兩次掃瞄，假設內存分配最多 $I$ 個 32bits 整數 ($I \ll N$)。

  • 由於記憶體限制大小關係，將數值範圍分成 $I$ 堆，如 [0, V/I-1]、[V/I, 2V/I-1]、… 等，計算區間範圍內的個數，讀取一次檔案，可以得到中位數介於 [iV/I, (i+1)V/I-1]。
  • 接著再劃分一次，直到區間長度為 1，中位數便可得到。
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
#include <stdio.h>
#include <assert.h>
#include <string.h>
int fsize(FILE *fp) {
    int prev = ftell(fp);
    fseek(fp, 0L, SEEK_END);
    int size = ftell(fp);
    fseek(fp, prev, SEEK_SET);
    return size;
}
#define MAXELE ((1<<20)/4)
static int A[MAXELE];
static int B[MAXELE];
int countLess(FILE *fp, int ans) {
    int ret = 0, x, n = 0;
    fseek(fp, 0, SEEK_SET);
    while ((n = fread(A, sizeof(int), MAXELE, fp))) {
        for (int i = 0; i < n; i++)
            ret += A[i] <= ans;
    }
    return ret;
}
int main() {
    char fName[128];
    scanf("%s", fName);
    FILE *fin = fopen(fName, "rb");
    
    int n = fsize(fin) / sizeof(int);
    
    int m = n/2 + 1;
    int l = 0, r = 1000000000, mid, ret = 0;
    
    int WIDTH = r, SHIFT;
    
    for (SHIFT = 1; (1<<SHIFT) < MAXELE; SHIFT++);
    WIDTH = r / (1<<SHIFT);
    
    memset(B, 0, sizeof(B));
    fseek(fin, 0, SEEK_SET);
    while ((n = fread(A, sizeof(int), MAXELE, fin))) {
        for (int i = 0; i < n; i++) {
            assert((A[i]>>SHIFT) < MAXELE);
            B[A[i]>>SHIFT]++;
        }
    }
    
    int BASE = 0, SELECT;
    for (int i = 0, sum = m; i < MAXELE; i++) {
        sum -= B[i];
        if (sum <= 0) {
            BASE = i * (1<<SHIFT);
            SELECT = sum + B[i];
            break;
        }
    }
    
    memset(B, 0, sizeof(B));
    fseek(fin, 0, SEEK_SET);
    while ((n = fread(A, sizeof(int), MAXELE, fin))) {
        for (int i = 0; i < n; i++) {
            if (A[i] - BASE < MAXELE && A[i] >= BASE)
                B[A[i] - BASE]++;
        }
    }
    for (int i = 0, sum = SELECT; i < MAXELE; i++) {
        sum -= B[i];
        if (sum <= 0) {
            printf("%d\n", i + BASE);
            break;
        }
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

2016 Facebook Hacker Cup Round 1

Facebook Hacker Cup Round 1

A. Coding Contest Creation

給 $N$ 個整數序列，每一個整數表示題目難度，可以在序列中插入整數，目標在序列中依序挑出 4 個整數作為比賽題目配置，並且要求不改變原本序列順序，滿足題目難度嚴格遞增，相鄰題目難度不大於 10，請問至少加入幾道題目。 (意即要插入題目的數量使得序列長度被 4 整除。)

最保守的方式 DP，只需要 $\mathcal{O}(N)$ 時間，記錄狀態 dp[i] 表示前 i 個 (不含) 整數滿足前述要求至少要插入幾個數，得到

$$dp[i] = min(dp[i], dp[j] + 4 - (i-j+1)), \; i -3 \le j \le i, \; c_{j, i} + (i-j+1)\le 4$$

，計算 $c_{j, i}$ 列出 $A_j, A_{j+1}, ..., A_{i}$ 得知至少要插入幾個數，貪心計算兩兩數字之間的差值 $\textit{diff}_k$，$c_{j, i} = \sum (\left \lceil \frac{\textit{diff}_k}{10} \right \rceil - 1)$。每一個轉移最多 4 次，故時間複雜度 $\mathcal{O}(N)$。

B. Laundro, Matt

小夥伴有 $L$ 件未洗衣物，洗衣店有 $N$ 台洗衣機和 $M$ 台烘衣機，洗衣機和烘衣機一次只能處理一件衣物，而對於每一台洗衣機對於衣物都有不同的處理時間 $W_i$，烘衣機則固定每 $D$ 時間就能烘好一次衣物。小夥伴可以暫存洗好衣物的籃子無限大，同時移動衣物的時間快到可忽略，請問至少要隔多久才能帶著所有洗好烘好的衣物離開洗衣店。

時間軸模擬題，用 priority queue 維護時間軸，在每一個時間戳記下檢查事件發生。模擬兩台機器交換衣物會稍微複雜，事件定義有三種：

  1. 某洗衣機可以在 $t_i$ 時間完成洗好一件衣服，下一次事件發生則是 $t_i + W_i$。不考慮何時放入衣物，每一次抓最近可完成的洗衣機進行清洗，直接當作洗好。
  2. 若有空的烘衣機，將洗好但未烘的衣物放入烘衣機，並將此烘衣機設定忙碌。並且標記 $t_i + D$ 時間此烘衣機會從忙碌變成閒置。
  3. 從忙碌變成閒置的烘衣機，記錄有多少衣物洗好烘好。

時間複雜度 $\mathcal{O}(L \log (N+M))$。

C. Yachtzee

宅宅的退休工程師想建造遊艇，預算總額從 $[A, B]$ 隨機地挑一個，請問建造所剩餘金額的期望值為何。建造策略如下：

  1. 造遊艇分成 $N$ 個步驟，每一個步驟各自有其預算 $C_i$。
  2. 造完一艘後，便著手建造下一艘，
  3. 直到某一個步驟預算不夠，便放下手上的計劃。(可能建造出半艘船)

數學期望值計算，時間複雜度 $\mathcal{O}(N)$，窮舉在每一個步驟罷工，因為卡在區間 $[A, B]$，計算剩餘金額在此步驟停止會稍微複雜。一艘船需要的預算為 $C$，那麼在某些情況 $C_i$ 會完全被 $[A, B]$ 包含，累計期望值 $\frac{0+C_i}{2}$，接著針對部分在區間 $[A, B]$ 的邊界情況。計算方法很多，在此也不多作解釋。

D. Boomerang Tournament

$2^N$ 個人進行樹狀單淘汰賽，給予每名選手互打的獲勝結果，在還沒公佈對局樹狀圖之前，請問每名選手預期能得到的最好和最壞名次為何。排名為嚴格多於自己的勝場數的選手個數。

選手最多 16 位，直接來個 $\mathcal{O}(16!)$ 絕對不行。當然樹狀圖的對稱性也許足以讓數量變得在時間內可窮舉完畢，但寫起來也複雜許多。

因此，利用位元壓縮 dp[參與選手集合][勝者] = 1/0 記錄子樹的情況，只需要 $\mathcal{O}(2^{16} \times 16)$ 個狀態總數，在集合合併處理需要窮舉子集合，由於我們只需要窮舉特定集合大小，複雜度不會到 $\mathcal{O}(3^{16})$ 這麼慘。合併時根據兩子樹的勝者相對打，同時紀錄兩位可夠晉級的最大最小回合數即可。

### Solution ###

#### A. Coding Contest Creation ####

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 <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 131072;
const int LMAX = 0x3f3f3f3f;
int dp[MAXN];
int main() {
    int testcase, n, x;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        vector<int> A;
        for (int i = 0; i < n; i++)
            scanf("%d", &x), A.push_back(x);
        
        for (int i = 0; i <= n; i++)
            dp[i] = LMAX;
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            vector<int> S;
            for (int j = 0; j < 4 && i+j < n; j++) {
                if (j && A[i+j] <= A[i+j-1])
                    break;
                S.push_back(A[i+j]);
                int inner = 0;
                for (int k = 0; k < j; k++) {
                    int diff = S[k+1] - S[k];
                    inner += max(diff / 10 + (diff % 10 != 0) - 1, 0);
                }
//                printf("[%2d,%2d] %d %d\n", i, j, inner, (int) S.size());
                if (inner + S.size() <= 4) {
//                    printf("update %d = %d from %d\n", i+j+1, dp[i] + 4 - (int) S.size(), dp[i]);
                    dp[i+j+1] = min(dp[i+j+1], dp[i] + 4 - (int) S.size());
                }
            }
        }
        printf("Case #%d: %d\n", ++cases, dp[n]);
    }
    return 0;
}

B. Laundro, Matt

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
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 131072;
const int LMAX = 0x3f3f3f3f;
int main() {
    int testcase;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int L, N, M, D, W, target;
        multiset< pair<long long, int> > EMPTYN;
        multiset<long long> EMPTYM;
        set<long long> timeline;
        multiset< pair<long long, int> > S;
        scanf("%d %d %d %d", &L, &N, &M, &D);
        for (int i = 0; i < N; i++) {
            scanf("%d", &W);
            EMPTYN.insert({W, W});
            timeline.insert(W);
        }
        
        target = L;
        int basket = 0;
        int complete = 0;
        long long ret = 0;
        timeline.insert(0);
        while (timeline.size() != 0) {
            long long time = *timeline.begin();
            timeline.erase(timeline.begin());
            while (L != 0 && EMPTYN.begin()->first <= time) {
                pair<long long, int> e = *EMPTYN.begin();
                EMPTYN.erase(EMPTYN.begin());
                EMPTYN.insert({e.first+e.second, e.second});
                timeline.insert(e.first+e.second);
                L--, basket++;
            }
            while (!EMPTYM.empty() && *EMPTYM.begin() <= time) {
                EMPTYM.erase(EMPTYM.begin());
                M++;
                complete++;
                if (complete == target)
                    ret = time;
            }
            while (basket > 0 && M > 0) {
                basket--, M--;
                EMPTYM.insert(time + D);
                timeline.insert(time + D);
            }
        }
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

C. Yachtzee

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 <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN = 131072;
const int LMAX = 0x3f3f3f3f;
long long C[MAXN];
double f(double l, double r) {
//    printf("[%lf, %lf]\n", l, r);
    return (r - l) * (r + l) / 2;
}
int main() {
    int testcase;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N;
        double A, B;
        scanf("%d %lf %lf", &N, &A, &B);
        for (int i = 0; i < N; i++) {
            scanf("%lld", &C[i]);
        }
        
        double ret = 0;
        double sum = 0, pre = 0;
        for (int i = 0; i < N; i++)
            sum += C[i];
        for (int i = 0; i < N; i++) {
            double pp = ceil(A / sum);
            double qq = floor(B / sum);
            int st = pp, ed = qq;
            set<int> S;
            for (int j = max(0, st-3); j <= st+3; j++) {
                if (S.count(j))
                    continue;
                double l = j * sum + pre, r = j * sum + pre + C[i];
                if (max(l, A) <= min(r, B)) {
                    ret += f(max(l, A) - (j * sum + pre), min(r, B) - (j * sum + pre));
                }
                S.insert(j);
            }
            for (int j = max(0, ed-3); j <= ed+3; j++) {
                if (S.count(j))
                    continue;
                double l = j * sum + pre, r = j * sum + pre + C[i];
                if (max(l, A) <= min(r, B)) {
                    ret += f(max(l, A) - (j * sum + pre), min(r, B) - (j * sum + pre));
                }
                S.insert(j);
            }
            
            ret += f(0, C[i]) * max((ed-3) - (st+3)-1, 0);
            pre += C[i];
        }
        
        ret /= (B - A);
        printf("Case #%d: %.9lf\n", ++cases, ret);
    }
    return 0;
}
/*
 5
 2 100 200
 100 100
 2 100 200
 50 100
*/

D. Boomerang Tournament

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 <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN = 131072;
int g[16][16];
int dp[1<<17][16];
int main() {
    int testcase;
    int cases = 0, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                scanf("%d", &g[i][j]);
        }
        
        int ret[16][2], A[16];
        A[0] = n/2;
        for (int i = 1; i < n; i++)
            A[i] = A[i-1]/2;
        for (int i = 0; i < n; i++)
            ret[i][0] = 0, ret[i][1] = __builtin_ffs(n)-1;
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++)
            dp[1<<i][i] = 1;
        int round[64] = {1};
        for (int i = 0; i < 5; i++)
            round[1<<i] = i;
        for (int i = 0; i < (1<<n); i++) {
            int cnt = __builtin_popcount(i);
            if (cnt != (cnt & (-cnt)))
                continue;
            if (cnt == 1)
                continue;
            for (int j = (i-1)&i; j; j = (j-1)&i) {
                if (__builtin_popcount(j) != cnt/2)
                    continue;
                for (int p = 0; p < n; p++) {
                    if (dp[j][p])
                    for (int q = 0; q < n; q++) {
                        if (dp[i^j][q]) {
                            if (g[p][q]) {
                                dp[i][p] = 1;
//                                printf("%d %d %d\n", cnt, p, q);
                                ret[p][0] = max(ret[p][0], round[cnt]);
                                ret[q][1] = min(ret[q][1], round[cnt]-1);
                            } else {
//                                printf("%d %d %d\n", cnt, q, p);
                                dp[i][q] = 1;
                                ret[p][1] = min(ret[p][1], round[cnt]-1);
                                ret[q][0] = max(ret[q][0], round[cnt]);
                            }
                        }
                    }
                }
            }
        }
//        for (int i = 0; i < n; i++) {
//            printf("[%d] %d\n", i, dp[(1<<n)-1][i]);
//        }
        printf("Case #%d:\n", ++cases);
        
        int rank[16];
        for (int i = 0, sum = 0; i < n; i++) {
            sum += n>>(i+1);
            if ((1<<i) == n)
                rank[i] = 1;
            else
                rank[i] = n - sum + 1;
        }
        for (int i = 0; i < n; i++) {
            int a = ret[i][0];
            int b = ret[i][1];
//            if (ret[i][1] != n) a = max(a, ret[i][1]);
//            if (ret[i][0] != -1) b = min(b, ret[i][0]);
            printf("%d %d\n", rank[a], rank[b]);
        }
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

2016 Facebook Hacker Cup 資格賽

好一陣子沒用 C++ 解題，感覺新鮮。嗯 … 

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

Facebook Hacker Cup 2016 Qualification Round

A. Boomerang Constellations

給予在星空下每顆星的座標，找出由三點構成回力鏢樣貌的組合個數，需滿足一點到兩點距離相等。

窮舉所有可能 $\mathcal{O}(N^3)$ 將會 TLE。窮舉回力鏢中心座標 $O$，統計其餘點到 $O$ 的距離，對於相同距離計數，套用組合公式 $C(n, 2)$ 加總，時間複雜度 $\mathcal{O}(n^2 \log n)$

B. High Security

給予只有兩排的長形棋盤狀的營地，雇用最少警衛監視每一塊區域，有些區域會因遮蔽物擋住警衛視線，而警衛只能監視平行兩軸的連續相鄰格子。求最少警衛個數。

第一眼覺得是 flow 可解，但求最少的模型建不太出來 Orz，就決定貪心。在同一行，連續片段上必然放置一個警衛，優先將連續片段總數匹配另一行連續個數恰好為一，剩下的情況再利用連續個數恰好一個的相互匹配。

C. The Price is Correct

參與一場遊戲，獎品價值為 $P$，給訂 $N$ 個正整數序列，挑選連續的序列總和小於等於 $P$ 即可獲得獎品，請問有多少挑選方式。

由於是序列為正整數，前綴和具有單調性，滑動窗口統計方法數只需要 $\mathcal{O}(N)$。最懶得方式是直接二分搜尋 $\mathcal{O}(n \log n)$。

D. Text Editor

從 $N$ 個不同的單字中，打印恰好 $K$ 個輸出在螢幕上，操作有三種 1. 在尾端插入一個字符 2. 刪除字串尾端一個字符 3. 將緩衝區的字串印出來，並且在操作結束後，緩衝區大小為 0。求最少操作個數為何？

第一次遐想，由於要最少操作個數，想必前綴相似的都必須連續，因此先對所有單字排序，接著按照順序 DP。先不考慮操作 3，最後一定恰好為 $K$ 次，只需要考慮插入和刪除操作，維護最後一個在緩衝區為單字 $i$，轉移到下一個單字 $j$ 的成本是 len(Wi) + len(Wj) - LCP[i, j]*2 (刪除前面 $W_i$ 的後綴再加入 $W_j$ 的後綴)，因此要預處理 LCA[i, j]，題目給訂範圍應該不用套用 Trie 或者是 Suffix Array 進行查找，暴力計算即可。定義 DP[i][k] 表示目前打了 $k$ 個單字，最後一個單字恰好為 $i$ 的最少操作次數。在 DP 部分，時間複雜度 $\mathcal{O}(N^2 K)$。

Solution

Sol. A. Boomerang Constellations

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 <bits/stdc++.h>
using namespace std;
#define MAXN 2048
long long X[MAXN], Y[MAXN];
int main() {
    int testcase, cases = 0, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        long long ret = 0;
        for (int i = 0; i < n; i++)
            scanf("%lld %lld", &X[i], &Y[i]);
        
        for (int i = 0; i < n; i++) {
            map<long long, int> R;
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;
                long long dist = 0;
                dist += (X[i] - X[j])*(X[i] - X[j]);
                dist += (Y[i] - Y[j])*(Y[i] - Y[j]);
                R[dist]++;
            }
            for (auto &p : R)
                ret += p.second * (p.second-1)/2;
        }
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

Sol. B. High Security

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 <bits/stdc++.h>
using namespace std;
#define MAXN 1024
char g[2][MAXN];
int main() {
    int testcase, cases = 0, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        scanf("%s%s", g[0], g[1]);
        int ret = 0;
        int A[2][MAXN] = {}, B[2][MAXN] = {};
        int used[MAXN] = {};
        int gid = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] != '.') 
                    continue;
                int x = j, cnt = 0;
                while (x < n && g[i][x] == '.')
                    x++, cnt++;
                x = j;
                gid++, ret++;
                while (x < n && g[i][x] == '.')
                    A[i][x] = gid, B[i][x] = cnt, x++;
                j = x;
            }
        }
        
//		for (int i = 0; i < 2; i++) {
//			for (int j = 0; j < n; j++)
//				printf("%d", A[i][j]);
//			puts("");
//		}
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] != '.')
                    continue;
                if (B[i][j] == 1)
                    continue;
                if (used[A[i][j]])
                    continue;
                int x = j;
                while (x < n && g[i][x] == '.') {
                    if (g[!i][x] == '.' && !used[A[!i][x]] && B[!i][x] == 1) {
                        used[A[!i][x]] = 1;
                        ret--;
                        break;
                    }
                    x++;
                }
                while (x < n && g[i][x] == '.')
                    x++;
                j = x;
            }
        }
        
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] != '.')
                    continue;
                if (used[A[i][j]])
                    continue;
                if (B[i][j] == 1) {
                    if (g[!i][j] == '.' && !used[A[!i][j]] && B[!i][j] == 1) {
                        used[A[!i][j]] = 1;
                        ret--;
                    }
                }
            }
        }
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}

Sol. C. The Price is Correct

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 131072;
int N;
long long P, B[MAXN], C[MAXN];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %lld", &N, &P);
        for (int i = 1; i <= N; i++)
            scanf("%lld", &B[i]);
        C[0] = 0;
        for (int i = 1; i <= N; i++)
            C[i] = C[i-1] + B[i];
            
        long long ret = 0;
        for (int i = 1; i <= N; i++) {
            int idx = (int) (lower_bound(C, C + N+1, C[i] - P) - C);
            ret += i - idx;
        }
        printf("Case #%d: %lld\n", ++cases, ret);
    }
    return 0;
}

Sol. D. Text Editor

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
#include <bits/stdc++.h>
using namespace std;
const int MAXS = 131072;
const int MAXN = 512;
const long long LLMAX = 1LL<<60;
char s[MAXS];
int common[MAXN][MAXN];
long long dp[MAXN][MAXN];
int main() {
    int testcase, cases = 0;
    int N, K;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &K);
        vector<string> A;
        
        A.push_back("");
        for (int i = 0; i < N; i++) {
            scanf("%s", s);
            A.push_back(s);
        }
        
        sort(A.begin(), A.end());
        N = A.size();
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                int cnt = 0, x = i, y = j;
                for (int k = 0; k < A[x].length() && k < A[y].length(); k++) {
                    if (A[x][k] != A[y][k])
                        break;
                    cnt++;
                }
                common[i][j] = common[j][i] = cnt;
            }
        }
        
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++)
                dp[i][j] = LLMAX;
        }
        dp[0][0] = 0;
//		for (int i = 0; i < N; i++)
//			printf("%s\n", A[i].c_str());
            
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < K; j++) {
                if (dp[i][j] == LLMAX)
                    continue;
                for (int k = i+1; k < N; k++) {
                    long long t = 0;
                    t += A[k].length() - common[i][k];
                    t += A[i].length() - common[i][k];
                    dp[k][j+1] = min(dp[k][j+1], dp[i][j] + t);
                }
//				printf("%d %d - %lld\n", i, j, dp[i][j]);
            }
        }
        
        long long ret = LLMAX;
        for (int i = 0; i < N; i++)
            ret = min(ret, dp[i][K] + (long long) A[i].length());
        printf("Case #%d: %lld\n", ++cases, ret+K);
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b500. 子字串集合

Problem

給予一個字串 $S$，求出所有子字串的集合，將集合內除了空字串以外的字串照字典順序輸出。

Sample Input

1
SLEEP

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
E
EE
EEP
EP
L
LE
LEE
LEEP
P
S
SL
SLE
SLEE
SLEEP

Solution

新手上路練習題，沒打算考很難的操作，即便如此信任也破產，看來出成變態題的機會高一點導致釣不到人來寫。

直觀作法是窮舉所有子字串，去掉重複即可，時間複雜度 $O(N^3)$，由於 $N = 500$ 也要考慮輸出的成本，所以不可能出太大。儘管如此，來比較算法之間的空間和時間用量。

首先，最常見到的 set 作法，若直接儲存字串空間用量 $O(N^3)$，為了避免空間太多，可以自己寫一個 compare function 來完成，因此 set 只要記錄子字串的起始位置和長度即可，時間複雜度 $O(N^3)$，空間降到 $O(N^2)$。

接著，進入到後期，常用到字典樹 trie，若把所有後綴插入到字典中，接著在 trie 走訪輸出所有結果即可，時間複雜度 $O(N^2)$，空間 $O(N^2 \times 26)$。可以使用 double-array trie 捨棄掉一點時間，降低節點的空間使用量。

最後，比較強悍的後綴自動機，在劉汝佳的書上主要是用 DAWG (directed acyclic word graph) 來描述 suffix automaton，後綴自動機可以在線構造，時間和空間複雜度都是 $O(N)$，後綴自動機可以接受 $S$ 所有的後綴，關於建造時間和狀態總數的證明可以參考 《Suffix Automaton 杭州外国语学校 陈立杰》 的簡報。

若不想這麼詳細的證明狀態總數和時間複雜度，可以從 AC 自動機的建構概念來思考，一樣有 fail 指針，來維護當一個後綴失去匹配，移除前綴要移動到的狀態。特別的是，每一次增加最多兩個節點，最後一次增加的節點為 accept state (後綴自動機只有一個或兩個 accept state)，其中一個節點是解決當前字串的後綴長度 1 的轉移。

根據這一題的需求，走訪一次後綴自動機就能印出所有子字串。

  • set 解法一 AC (0.2s, 25.2MB)
  • set 解法二 AC (0.4s, 3.8MB)
  • trie AC (0.1s, 12.1MB)
  • Double-array trie AC (0.2s, 7.7MB)
  • 後綴自動機 suffix automaton AC (64ms, 240KB)

後綴自動機

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
#include <bits/stdc++.h>
class SuffixAutomaton {
public:
    static const int MAXN = 500<<1;
    static const int MAXC = 26;
    struct Node {
        Node *next[MAXC], *pre;
        int step;
        Node() {
            pre = NULL, step = 0;
            memset(next, 0, sizeof(next));
        }
    } _mem[MAXN];
    int size;
    Node *root, *tail;	
    void init() {
        size = 0;
        root = tail = newNode();
    }
    Node* newNode() {
        Node *p = &_mem[size++];
        *p = Node();
        return p;
    }
    int toIndex(char c) { return c - 'A'; }
    char toChar(int c) { return c + 'A'; }
    void add(char c, int len) {
        c = toIndex(c);
        Node *p, *q, *np, *nq;
        p = tail, np = newNode();
        np->step = len;
        for (; p && p->next[c] == NULL; p = p->pre)
            p->next[c] = np;
        tail = np;
        if (p == NULL) {
            np->pre = root;
        } else {
            if (p->next[c]->step == p->step+1) {
                np->pre = p->next[c];
            } else {
                q = p->next[c], nq = newNode();
                *nq = *q;
                nq->step = p->step + 1;
                q->pre = np->pre = nq;
                for (; p && p->next[c] == q; p = p->pre)
                    p->next[c] = nq;
            }
        }
    }
    void build(const char *s) {
        init();
        for (int i = 0; s[i]; i++)
            add(s[i], i+1);
    }
    void dfs(Node *u, int idx, char path[]) {
        for (int i = 0; i < MAXC; i++) {
            if (u->next[i]) {
                path[idx] = toChar(i);
                path[idx+1] = '\0';
                puts(path);
                dfs(u->next[i], idx+1, path);
            }
        }
    }
    void print() {
        char s[1024];
        dfs(root, 0, s);
    } 
} SAM;
int main() {
    char s[1024];
    while (scanf("%s", s) == 1) {
        SAM.build(s);
        SAM.print();
    }
    return 0;
}

set ver 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h> 
using namespace std;
int main() {
    char s[512];
    while (scanf("%s", s) == 1) {
        set<string> S;
        int n = strlen(s);
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                char c = s[j+1];
                s[j+1] = '\0';
                S.insert(s+i);
                s[j+1] = c;
            }
        }
        for (auto &x : S)
            puts(x.c_str());
    }
    return 0;
}

set ver 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
#include <bits/stdc++.h> 
using namespace std;
char s[512];
struct cmp {
    bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
        for (int i = 0; i < a.second && i < b.second; i++) {
            if (s[a.first+i] != s[b.first+i])
                return s[a.first+i] < s[b.first+i];
        }
        return a.second < b.second;
    }
};
int main() {
    while (scanf("%s", s) == 1) {
        set< pair<int, int>, cmp > S;
        int n = strlen(s);
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                S.insert({i, j-i+1});
            }
        }
        for (auto &x : S) {
            int base = x.first, len = x.second;
            char c = s[base+len];
            s[base+len] = '\0';
            puts(s + base);
            s[base+len] = c;
        }
    }
    return 0;
}

trie

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 <bits/stdc++.h> 
using namespace std;
class Trie {
public:
    static const int MAXN = 130000;
    static const int MAXC = 26;
    struct Node {
        Node *next[MAXC];
        void init() {
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXN];
    Node *root;
    int size;
    Node* newNode() {
    	assert(size < MAXN);
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = 0;
        root = newNode();
    }
    inline int toIndex(char c) {
        return c - 'A';
    }
    inline int toChar(char c) {
        return c + 'A';
    }
    void insert(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] = newNode();
            p = p->next[idx];
        }
    }
    void dfs(Node *u, int idx, char path[]) {
        for (int i = 0; i < MAXC; i++) {
            if (u->next[i]) {
                path[idx] = toChar(i);
                path[idx+1] = '\0';
                puts(path);
                dfs(u->next[i], idx+1, path);
            }
        }
    }
    void print() {
        char s[1024];
        dfs(root, 0, s);
    }
} tree;
char s[1024];
int main() {
    while (scanf("%s", s) == 1) {
        int n = strlen(s);
        tree.init();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                char c = s[j+1];
                s[j+1] = '\0';
                tree.insert(s+i);
                s[j+1] = c;
            }
        }
        tree.print();
    }
    return 0;
}

DA trie

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
#include <bits/stdc++.h> 
using namespace std;
class DATrie {
public:
    static const int MAXN = 500000;
    static const int MAXC = 27;
    struct Node {
        int check, base, fail, val;
    } A[MAXN + MAXC];
    int node_size, mem_size, emp_size;
    //
    int son_pos[MAXC], find_pos;
    inline int toIndex(char c) {
        return c - 'A' + 1;
    }
    inline int toChar(char c) {
        return c + 'A' - 1;
    }
    inline bool isEMPTY(int u) {
    	return u < MAXN && A[u].check < 0 && A[u].base < 0;
    }
    void init() {
        for (int i = 1; i < MAXN; i++)
            A[i].check = -(i+1), A[i].base = -(i-1);
        for (int i = MAXN; i < MAXN + MAXC; i++)
            A[i].check = INT_MAX;
        A[MAXN-1].check = -1, A[1].base = -(MAXN-1);
        A[0].check = -1, A[0].base = 0;
        node_size = mem_size = emp_size = 0, find_pos = 1;
    }
    inline void rm_node(int x) {
        if (find_pos == x)	find_pos = abs(A[x].check);
        A[-A[x].base].check = A[x].check;
        A[-A[x].check].base = A[x].base;
        node_size++;
        mem_size = max(mem_size, x);
    }
    inline void ad_node(int x) {
        A[x].check = MAXN, A[x].base = MAXN;
        emp_size++;
    }
    bool insert(const char *s) {
        int st = 0, to, c;
        int flag = 0;
        for (int i = 0; s[i]; i++) {
            c = toIndex(s[i]);
            to = abs(A[st].base) + c;	
            if (st == abs(A[to].check)) {
                st = to;
            } else if (isEMPTY(to)) {
                rm_node(to); 
                A[to].check = st, A[to].base = to;
                st = to;
            } else {
                int son_sz = 0;
                int pos = find_empty(st, c, son_sz);
                relocate(st, pos, son_sz-1);
                i--; 
            }
        }
        A[st].base = -abs(A[st].base);
        return 1;
    }
    int find(const char *s) {
        int st = 0, to, c;
        for (int i = 0; s[i]; i++) {
            c = toIndex(s[i]);
            to = abs(A[st].base) + c;
            if (st == abs(A[to].check))
                st = to;
            else
                return 0;
        }
        return A[st].base < 0;
    }
    int find_empty(int st, int c, int &sz) {
        sz = 0;
        int bs = abs(A[st].base);
        for (int i = 1, j = bs+1; i < MAXC; i++, j++) {
            if (abs(A[j].check) == st)
                son_pos[sz++] = i;
        }
        son_pos[sz++] = c;
        int mn_pos = min(son_pos[0], c) - 1;
        for (; find_pos && (find_pos < bs || find_pos < mn_pos); find_pos = abs(A[find_pos].check));
        for (; find_pos; find_pos = abs(A[find_pos].check)) {
            int ok = 1;
            for (int i = 0; i < sz && ok; i++)
                ok &= isEMPTY(find_pos + son_pos[i] - mn_pos);
            if (ok)
                return find_pos - mn_pos;
        }
        printf("Memory Leak -- %d\n", find_pos);
        exit(0);
        return -1;
    }
    void relocate(int st, int to, int sz) {	// move ::st -> ::to
        for (int i = sz-1; i >= 0; i--) {
            int a = abs(A[st].base) + son_pos[i];	// old
            int b = to + son_pos[i];			// new
            rm_node(b);
            A[b].check = st, A[b].base = A[a].base;
            int vs = abs(A[a].base);
            for (int j = 1, k = vs+1; j < MAXC; j++, k++) {
                if (abs(A[k].check) == a)
                    A[k].check = b;
            }
            ad_node(a);
        }
        A[st].base = (A[st].base < 0 ? -1 : 1) * to;
    }
    void dfs(int u, int idx, char path[]) {
        for (int i = 1; i < MAXC; i++) {
            int to = abs(A[u].base) + i;
            if (u == abs(A[to].check)) {
                path[idx] = toChar(i);
                path[idx+1] = '\0';
                puts(path);
                dfs(to, idx+1, path);
            }
        }
    }
    void print() {
        char s[1024];
        dfs(0, 0, s);
    }
} tree;
char s[1024];
int main() {
    while (scanf("%s", s) == 1) {
        int n = strlen(s);
        tree.init();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                char c = s[j+1];
                s[j+1] = '\0';
                tree.insert(s+i);
                s[j+1] = c;
            }
        }
        tree.print();
    }
    return 0;
}
Read More +