解題區/解題區 - 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 +
解題區/解題區 - UVa

UVa 1352 - Colored Cubes

Problem

給予最多 4 個骰子，修改最少的面，使得每個骰子同構。

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
33
34
35
36
37
38
3 
scarlet green blue yellow magenta cyan 
blue pink green magenta cyan lemon 
purple red blue yellow cyan green 
2 
red green blue yellow magenta cyan 
cyan green blue yellow magenta red 
2 
red green gray gray magenta cyan 
cyan green gray gray magenta red 
2 
red green blue yellow magenta cyan 
magenta red blue yellow cyan green 
3 
red green blue yellow magenta cyan 
cyan green blue yellow magenta red 
magenta red blue yellow cyan green 
3 
blue green green green green blue 
green blue blue green green green 
green green green green green sea-green 
3 
red yellow red yellow red yellow 
red red yellow yellow red yellow 
red red red red red red 
4 
violet violet salmon salmon salmon salmon 
violet salmon salmon salmon salmon violet 
violet violet salmon salmon violet violet 
violet violet violet violet salmon salmon 
1 
red green blue yellow magenta cyan 
4 
magenta pink red scarlet vermilion wine-red 
aquamarine blue cyan indigo sky-blue turquoise-blue 
blond cream chrome-yellow lemon olive yellow 
chrome-green emerald-green green olive vilidian sky-blue 
0

Sample Output

1
2
3
4
5
6
7
8
9
10
4 
2 
0 
0 
2 
3 
4 
4 
0 
16

Solution

由於每個骰子有 24 種同構排列，複雜度 O(24^4)。

將排列對齊後，使用貪心算法，將每一個 column 找到最多相同元素，剩餘的就是最少修改元素。

類似漢明距離的最少修改。順便將之前的代碼重新構造。

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
struct DICE {
    int dice[6]; // front, right, up, back, left, down
    void rightTurn() {
    	static int t;
    	t = dice[0], dice[0] = dice[4];
    	dice[4] = dice[3], dice[3] = dice[1], dice[1] = t;
    }
    void upTurn() {
    	static int t;
    	t = dice[0], dice[0] = dice[5];
    	dice[5] = dice[3], dice[3] = dice[2], dice[2] = t;
    }
    void clockwise() {
        static int t;
        t = dice[2], dice[2] = dice[4];
        dice[4] = dice[5], dice[5] = dice[1], dice[1] = t;
    }
    void print() {
        for (int i = 0; i < 6; i++)
            printf("%d ", dice[i]);
        puts("");
    }
    vector<DICE> generate() {
        vector<DICE> ret;
        DICE tmp = *this;
        
        for (int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
            	ret.push_back(tmp);
                tmp.clockwise();
            }        
            tmp.rightTurn();
        }
        tmp.upTurn();
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 4; j++) {
                ret.push_back(tmp);
                tmp.clockwise();
            }        
            tmp.upTurn(), tmp.upTurn();
        }
        return ret;
    }
    bool operator<(const DICE &x) const {
        for (int i = 0; i < 6; i++)
            if (dice[i] != x.dice[i])
                return dice[i] < x.dice[i];
        return false;
    }
    bool operator==(const DICE &x) const {
        for (int i = 0; i < 6; i++)
            if (dice[i] != x.dice[i])
                return false;
        return true;
    }
};
int path[8];
vector<DICE> kind[8];
vector<DICE> permutation;
int ret = 0x3f3f3f3f, N;
int counter[32];
void dfs(int idx) {
    if (idx == N) {
        int ch = 0;
        for (int i = 0; i < 6; i++) {
            int mx = 0;
            memset(counter, 0, sizeof(counter));
            for (int j = 0; j < N; j++)
                mx = max(mx, ++counter[kind[j][path[j]].dice[i]]);
            ch += N - mx;
            if (ch >= ret)	return ;
        }
        ret = min(ret, ch); 
        return ;
    }
    for (int i = 0; i < kind[idx].size(); i++) {
        path[idx] = i;
        dfs(idx+1);
    }
}
int main() {
    DICE p;
    for (int i = 0; i < 6; i++)
    	p.dice[i] = i;
    permutation = p.generate();
    
    char s[128];
    while (scanf("%d", &N) == 1 && N) {
    	map<string, int> colors;
    	for (int i = 0; i < N; i++) {
    		int v[6];
    		for (int j = 0; j < 6; j++) {
    			scanf("%s", s);
    			int &x = colors[s];
    			if (x == 0)	x = colors.size();
    			v[j] = x;
    		}
    		DICE D;
    		D.dice[0] = v[0], D.dice[1] = v[1], D.dice[2] = v[2];
    		D.dice[5] = v[3], D.dice[4] = v[4], D.dice[3] = v[5];
    		
    		kind[i] = D.generate();
    		sort(kind[i].begin(), kind[i].end());
    		kind[i].resize(unique(kind[i].begin(), kind[i].end()) - kind[i].begin());
//    		printf("%d\n", kind[i].size());
    	}
    	
    	ret = 0x3f3f3f3f;
    	dfs(0);
    	printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1364 - Knights of the Round Table

Problem

圓桌武士要圍一桌，由於騎士很多，他們彼此憎恨的關係也越來越複雜，梅林被聘請來計劃會議的圓桌位置，騎士們的座位必須符合下列條件，否則將會無法開會。

  • 彼此憎恨的騎士不可相鄰
  • 圓桌要恰好奇數個人，否則無法進行投票

由於是圓桌，每個騎士都恰好有兩個鄰居，梅林只想知道誰絕對沒有辦法參與圓桌，求出絕對無法參與圓桌會議的騎士個數，並不用最大化圓桌的最大人數。

Sample Input

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

Sample Output

1
2

Solution

首先，一個簡單的特性，二分圖如果存在環，則保證沒有奇環，因為從 X 集合出去到 Y 集合，再回到 X 集合，保證環的路徑一定經過偶數條邊。同時，存在奇環的圖，一定不是二分圖。

二分圖不存在奇環，存在奇環的圖一定不是二分圖

藉由這個道理，這題還需要點特性，如果這張圖存在奇環，對於一個 BCC (雙向連通元件)，則滿足所有點都可以在一個奇環上。有可能一個點同時在奇環或者是偶環。

這個證明也很簡單，BCC 在元件中，定義拿走任一條邊 e(u, v)，u 和 v 之間仍然存在一條路徑。那麼可以知道對於一個奇環上的點 x 和 y，以及奇環外一點 u，若 e(x, u) 存在，則 e(u, y) 也存在，則會產生兩個環，其中一個環一定是奇數。擴散下去，所有在 BCC 元件的點，都會在一個奇環上。

BCC 存在奇環，每一個點都至少在一個奇環上

很久沒寫 BCC，一直以來寫 cut point (關節點) 和 cut edge (bridge) 的機會比較高，都忘了 BCC 的寫法。一張圖，拆成 BCC 時，每一個節點可能存在數個 BCC 元件中。

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
// BCC
#include <stdio.h> 
#include <string.h>
#include <vector> 
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 1024;
class BCC {
public:
    vector<int> g[MAXN], bcc[MAXN];
    stack< pair<int, int> > stk;
    int n;
    int vfind[MAXN], findIdx;
    int visited[MAXN];
    int bcc_tmp[MAXN], bccCnt, cutPt[MAXN];
    int dfs(int u, int p) {
        visited[u] = 1;
        vfind[u] = ++findIdx;
        
        int mn = vfind[u], branch = 0, t;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (!visited[v]) {
                stk.push(make_pair(u, v));
                t = dfs(v, u);
                mn = min(mn, t), branch++;
                if (t >= vfind[u]) {
                    pair<int, int> e;
                    bcc[++bccCnt].clear();
                    do {
                        e = stk.top(), stk.pop();
                        if (bcc_tmp[e.first] != bccCnt)
                            bcc[bccCnt].push_back(e.first), bcc_tmp[e.first] = bccCnt;
                        if (bcc_tmp[e.second] != bccCnt)
                            bcc[bccCnt].push_back(e.second), bcc_tmp[e.second] = bccCnt;
                    } while (e != make_pair(u, v));
                    cutPt[u] = 1;
                }
            } else if (vfind[v] < vfind[u] && v != p) {
                stk.push(make_pair(u, v));
                mn = min(mn, vfind[v]);
            }
        }
        if (p < 0 && branch == 1)	cutPt[u] = 0;
        return mn;
    }
    void findBCC() {
        while (!stk.empty())	stk.pop();
        memset(visited, 0, sizeof(visited));
        memset(bcc_tmp, 0, sizeof(bcc_tmp));
        bccCnt = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                findIdx = 0;
                dfs(i, -1);
            }
        }
    }
    void addEdge(int x, int y) {
        g[x].push_back(y), g[y].push_back(x);
    }
    void init(int n) {
        this->n = n;
        for (int i = 0; i < n; i++)
            g[i].clear();
    }
} g;
int A[MAXN][MAXN];
int belong[MAXN], color[MAXN];
int isBipartite(int u) {
    for (int i = 0; i < g.g[u].size(); i++) {
        int v = g.g[u][i];
        if (belong[u] != belong[v])	
            continue;
        if (color[v] == color[u])
            return false;
        if (!color[v]) {
            color[v] = 3 - color[u];
            if (!isBipartite(v))
                return false;
        }
    }
    return true;
}
int main() {
    int n, m, x, y;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        memset(A, 0, sizeof(A));
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y), x--, y--;
            A[x][y] = A[y][x] = 1;
        }
        
        g.init(n);
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (!A[i][j]) {
                    g.addEdge(i, j);
//					printf("%d %d --\n", i, j);
                }
            }
        }
        
        g.findBCC();
        
        memset(belong, 0, sizeof(belong));
        int onOddCycle[MAXN] = {};
        for (int i = 1; i <= g.bccCnt; i++) {
            for (int j = 0; j < g.bcc[i].size(); j++) {
                belong[g.bcc[i][j]] = i, color[g.bcc[i][j]] = 0;
//				printf("%d ", g.bcc[i][j]);
            }
//			puts("");
            memset(color, 0, sizeof(color));
            color[g.bcc[i][0]] = 1;
            if (!isBipartite(g.bcc[i][0])) { // 
                for (int j = 0; j < g.bcc[i].size(); j++)
                    onOddCycle[g.bcc[i][j]] = 1;
            }
        }
        
        int ret = n;
        for (int i = 0; i < n; i++)
            ret -= onOddCycle[i];
        printf("%d\n", ret);
    }
    return 0;
}
/*
7 9
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 1
4 5
1 2
2 3
3 4
4 1
2 4
4 4
1 2
2 3
3 1
1 4
5 5
1 4
1 5
2 5
3 4
4 5
12 3
8 7
2 3
4 2
7 12
4 7
5 6
1 7
2 1
1 3
2 7
5 1
6 3
6 7
3 7
3 4
4 1
0 0
*/
Read More +
解題區/解題區 - 其他題目

HDU 5097 - Page Rank

Problem

配合上一篇巨量資料的學習，利用馬可夫過程找到 Page Rank。

Sample Input

1
2
3
4
5
4
0111
0011
0001
0100

Sample Output

1
0.15 1.49 0.83 1.53

Solution

然而 Page Rank 計算主要分成兩種，一種是指派所有的 Page Rank 總合為 S，如果加起來不足 S，則把不足的部分平攤給所有節點，這麼一來計算誤差就可以被碾平，但這樣會會因為太多網頁，而導致單一 Rank 過小。

另外一種，則單純倚靠隨機的全局擴散，雖然會有計算誤差，持續做下去一樣會收斂。

為了加快速度，將公式的$1 - \beta$ 提出，沒有必要將一個稀疏矩陣變成稠密矩陣，如果每一個矩陣元素都加上$\frac{1 - \beta}{N}$ 會導致整個矩陣不存在非 0 的元素，而事實上 0 的元素是相當多的。這麼一來每次迭代的效率為$O(E)$，而非$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
#include <stdio.h>
#include <math.h>
#include <vector>
#include <string.h>
using namespace std;
// Markov process, math
const int MAXN = 4096;
const int MAXIT = 9999;
class PageRank {
public:
    const double eps = 1e-10;
    vector<int> g[MAXN], invg[MAXN];
    vector<double> r;
    int N;
    double beta, S;
    void init(int n, double beta) {
        this->N = n;
        this->beta = beta;
        for (int i = 0; i < n; i++)
            g[i].clear(), invg[i].clear();
    }
    void addEdge(int u, int v) {
        g[u].push_back(v);
        invg[v].push_back(u);
    }
    bool isComplete(vector<double> &a, vector<double> &b) {
        double e = 0;
        for (int i = (int) a.size() - 1; i >= 0; i--) {
            e += (a[i] - b[i]) * (a[i] - b[i]);
        }
        return e < eps;
    }
    void compute() {
        vector<double> next_r(N, 0);
        r.resize(N, 1.0);
        
        for (int it = 0; it < MAXIT; it++) {
            for (int i = 0; i < N; i++) {
                double tmp = 0;
                for (int j = 0; j < invg[i].size(); j++) {
                    int x = invg[i][j];
                    tmp += r[x] / g[x].size();
                }
                next_r[i] = tmp * beta + (1.0 - beta);
            }
            if (isComplete(r, next_r)) {
                r = next_r;
                return ;
            }
            r = next_r;
        }
    }
} g;
char s[MAXN][MAXN];
int main() {
    const double beta = 0.85f;
    int N;
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++)
            scanf("%s", s[i]);
        
        g.init(N, beta);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (s[i][j] == '1') {
                    g.addEdge(i, j);
                }
            }
        }
        
        g.compute();
        
        for (int i = 0; i < N; i++) {
            printf("%.2lf%c", g.r[i], i == N - 1 ? '\n' : ' ');
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 11214 - Guarding the Chessboard

Problem

用最少的皇后，覆蓋盤面中所有的 ‘X’。皇后之間的相互攻擊可以忽略不理。

Sample Input

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

Sample Output

1
2
Case 1: 5
Case 2: 1

Solution

直接套 DLX 最小重複覆蓋的模板，但是單純使用會狂 TLE。額外加上初始貪心，找到搜索的第一把剪枝條件，這一個貪心使用每次找盤面上能覆蓋最多 ‘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
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXV 0x3f3f3f3f
#define MAXE 1048576
#define MAXC 1048576
#define MAXR 65536
class DLX {
public:
    struct DacingLinks {
        int left, right;
        int up, down;
        int ch, rh;
        int data; // extra info
    } DL[MAXE];
    int s[MAXC], o[MAXR], head, size, Ans, findflag;
    void Remove(int c) {
        static int i;
        for(i = DL[c].down; i != c; i = DL[i].down) {
            DL[DL[i].right].left = DL[i].left;
            DL[DL[i].left].right = DL[i].right;
            s[DL[i].ch]--;
        }
    }
    void Resume(int c) {
        static int i;
        for(i = DL[c].down; i != c; i = DL[i].down) {
            DL[DL[i].right].left = i;
            DL[DL[i].left].right = i;
            s[DL[i].ch]++;
        }
    }
    int used[MAXC] = {};
    int H() {
        static int c, ret, i, j, time = 0;
        for(c = DL[head].right, ++time, ret = 0; c != head; c = DL[c].right) {
            if(used[c] != time) {
                ret ++, used[c] = time;
                for(i = DL[c].down; i != c; i = DL[i].down)
                    for(j = DL[i].right; j != i; j = DL[j].right)
                        used[DL[j].ch] = time;
            }
        }
        return ret;
    }
    void DFS(int k) {
        if(k + H() >= Ans) return;
        if(DL[head].right == head) {
            Ans = min(Ans, k);
            return;
        }
        int t = MAXV, c = 0, i, j;
        for(i = DL[head].right; i != head; i = DL[i].right) {
            if(s[i] < t) {
                t = s[i], c = i;
            }
        }
        for(i = DL[c].down; i != c; i = DL[i].down) {
            o[k] = i;
            Remove(i);
            for(j = DL[i].right; j != i; j = DL[j].right) Remove(j);
            DFS(k+1);
            for(j = DL[i].left; j != i; j = DL[j].left) Resume(j);
            Resume(i);
            if (findflag) break;
        }
    }
    int new_node(int up, int down, int left, int right) {
        assert(size < MAXE);
        DL[size].up = up, DL[size].down = down;
        DL[size].left = left, DL[size].right = right;
        DL[up].down = DL[down].up = DL[left].right = DL[right].left = size;
        return size++;
    }
    void addrow(int n, int Row[], int data) {
        int a, r, row = -1, k;
        for(a = 0; a < n; a++) {
            r = Row[a];
            DL[size].ch = r, s[r]++;
            DL[size].data = data;
            if(row == -1) {
                row = new_node(DL[DL[r].ch].up, DL[r].ch, size, size);
                DL[row].rh = a;
            }else {
                k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
                DL[k].rh = a;
            }
        }
    }
    void init(int m) {
        size = 0;
        head = new_node(0, 0, 0, 0);
        int i;
        for(i = 1; i <= m; i++) {
            new_node(i, i, DL[head].left, head);
            DL[i].ch = i, s[i] = 0;
        }
    }
} dlx;
const int dx[8] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[8] = {1, -1, 0, 1, -1, 0, 1, -1};
int greedy(int n, int m, char g[][16]) {
    int ret = 0;
    while (true) {
        int has = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'X') {
                    has = 1;
                }
            }
        }
        if (!has)   break;
        int mx = 0, bx = 0, by = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int cnt = 0;
                for (int k = 0; k < 8; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    while (x >= 0 && x < n && y >= 0 && y < m) {
                        if (g[x][y] == 'X')
                            cnt++;
                        x += dx[k], y += dy[k];
                    }
                }
                if (g[i][j] == 'X')
                    cnt++;
                if (cnt > mx)
                    mx = cnt, bx = i, by = j;
            }
        }
        for (int k = 0; k < 8; k++) {
            int x = bx + dx[k], y = by + dy[k];
            while (x >= 0 && x < n && y >= 0 && y < m) {
                if (g[x][y] == 'X')
                    g[x][y] = '.';
                x += dx[k], y += dy[k];
            }
        }
        if (g[bx][by] == 'X')
            g[bx][by] = '.';
        ret++;
    }
    return ret;
}
int main() {
    int cases = 0;
    int n, m;
    char g[16][16];
    while (scanf("%d %d", &n, &m) == 2 && n) {
        int cover_col = 0, A[16][16] = {};
        for (int i = 0; i < n; i++)
            scanf("%s", g[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'X') {
                    A[i][j] = ++cover_col;
                }
            }
        }
        dlx.init(cover_col);
   
        int row[2028], rowSize = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                rowSize = 0;
                for (int k = 0; k < 8; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    while (x >= 0 && x < n && y >= 0 && y < m) {
                        if (g[x][y] == 'X')
                            row[rowSize++] = A[x][y];
                        x += dx[k], y += dy[k];
                    }
                }
                if (g[i][j] == 'X')
                    row[rowSize++] = A[i][j];
                sort(row, row + rowSize);
                if (rowSize) {
                    dlx.addrow(rowSize, row, i * m + j);
                }
            }
        }
        dlx.Ans = greedy(n, m, g);
        dlx.DFS(0);
        printf("Case %d: %d\n", ++cases, dlx.Ans);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1683 - In case of failure

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
2 
10 
17 41 
0 34 
24 19 
8 28 
14 12 
45 5 
27 31 
41 11 
42 45 
36 27 
15 
0 0 
1 2 
2 3 
3 2 
4 0 
8 4 
7 4 
6 3 
6 1 
8 0 
11 0 
12 2 
13 1 
14 2 
15 0

Sample Output

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
200 
100 
149 
100 
149 
52 
97 
52 
360 
97 
5 
2 
2 
2 
5 
1 
1 
2 
4 
5 
5 
2 
2 
2 
5

Solution

KD Tree

計算幾何中的資料結構 KD-tree，雖然不算完美，一開始先進行 random search，先找到基礎的剪枝條件，隨後掛上啟發式進行搜索。

KD-tree 的效能在 D 度空間，區間詢問 (回報區域中的所有點或求區域極值) 的效能約為 O(n^(1-1/d))。我不會估算找鄰近點對的效能。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 262144
#define MAXD 2
#define INF (1LL<<60)
class kdTree {
public:
    struct PointD {
        long long d[MAXD];
        int label;
    };
    struct Node {
        Node *lson, *rson;
        int label;
    };
    struct cmp {
        bool operator()(const PointD* x, const PointD* y) const {
            if (x->d[sortDidx] != y->d[sortDidx])
                return x->d[sortDidx] < y->d[sortDidx];
            return x->label < y->label;
        }
    };
    struct pQcmp {
        bool operator() (pair<long long, int> &a, pair<long long, int> &b) const {
            if (a.first != b.first)	return a.first < b.first;
            return a.second < b.second;
        }
    };
    static int sortDidx;
    priority_queue<pair<long long, int>, vector< pair<long long, int> >, pQcmp> pQ; // <dist, label>
    Node buf[MAXN], *root;
    PointD pt[MAXN], *A[MAXN];
    int bufsize, K, qM, n;
    long long Q[MAXD], max_dist;
    void prepare(int n) {
        this->n = n;
        bufsize = 0;
        for (int i = 0; i < n; i++)
            A[i] = &pt[i];
        root = build(0, 0, n - 1);
    }
    Node* build(int k, int l, int r) {
        if(l > r)	return NULL;
        int m = (l + r)/2;
        Node *ret = &buf[bufsize++];
        sortDidx = k;
        nth_element(A + l, A + m, A + r + 1, cmp());
        ret->label = A[m]->label, ret->lson = ret->rson = NULL;
        if(l != r) {
            ret->lson = build((k+1)%K, l, m-1);
            ret->rson = build((k+1)%K, m+1, r);
        }
        return ret;
    }
    long long dist(int idx) {
        long long ret = 0;
        for(int i = 0; i < K; i++)
            ret += (long long)(pt[idx].d[i] - Q[i]) * (pt[idx].d[i] - Q[i]);
        return ret;
    }
    long long h_func(long long h[]) {
        long long ret = 0;
        for(int i = 0; i < K; i++)	ret += h[i];
        return ret;
    }
    void findNearest(Node *u, int k, long long h[]) {
        if(u == NULL || h_func(h) >= max_dist)
            return;
        long long d = dist(u->label);
        if (d <= max_dist) {
            pQ.push(make_pair(d, u->label));
            while (pQ.size() >= qM + 1)
                max_dist = pQ.top().first, pQ.pop();
        }
        long long old_hk = h[k];
        if (Q[k] <= pt[u->label].d[k]) {
            if (u->lson != NULL)
                findNearest(u->lson, (k+1)%K, h);
            if (u->rson != NULL) {
                h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
                findNearest(u->rson, (k+1)%K, h);
                h[k] = old_hk;
            }
        } else {
            if(u->rson != NULL)
                findNearest(u->rson, (k+1)%K, h);
            if (u->lson != NULL) {
                h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
                findNearest(u->lson, (k+1)%K, h);
                h[k] = old_hk;
            }
        }
    }
    void randomSearch(int ban) {
        max_dist = INF;
        long long d;
        for (int i = 0; i < 100; i++) {
            int x = rand()%n;
            if (x == ban)	continue;
            d = dist(x);
            if (d <= max_dist) {
                pQ.push(make_pair(d, x));
                while (pQ.size() >= qM + 1)
                    max_dist = pQ.top().first, pQ.pop();
            }
        }
    }
    void query(long long p[], int M, int ban) {
        for (int i = 0; i < K; i++)
            Q[i] = p[i];
        max_dist = INF, qM = M;
        long long h[MAXD] = {};
        randomSearch(ban);
        findNearest(root, 0, h);
        vector<int> ret;
        while (!pQ.empty())
            ret.push_back(pQ.top().second), pQ.pop();
        for (int i = (int) ret.size() - 1; i >= 0; i--) {
            if (ret[i] == ban)	continue;
            printf("%lld\n", dist(ret[i]));
            break;
        }
    }
};
int kdTree::sortDidx;
kdTree tree;
int main() {
    int n;
    long long p[MAXD];
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        tree.K = 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++)
                scanf("%lld", &tree.pt[i].d[j]);
            tree.pt[i].label = i;
        }
        tree.prepare(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++)
                p[j] = tree.pt[i].d[j];
            tree.query(p, 2, i);
        }
    }
    return 0;
}
/*
 2
 10
 17 41
 0 34
 24 19
 8 28
 14 12
 45 5
 27 31
 41 11
 42 45
 36 27
 15
 0 0
 1 2
 2 3
 3 2
 4 0
 8 4
 7 4
 6 3
 6 1
 8 0
 11 0
 12 2 
 13 1 
 14 2 
 15 0
 */

Delaunay

關於 Delaunay triangulation 在此就不說明，由於是 Voronoi Diagram，就可以找到所有相鄰的點。

效能是 O(n log n)，而平面上的邊為線性 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <assert.h>
#include <string.h>
#include <list>
using namespace std;
#define eps 1e-8
#define MAXN (1048576)
#define MAXV 262144
struct Point {
    double x, y;
    int id;
    Point(double a = 0, double b = 0, int c = -1):
    x(a), y(b), id(c) {}
    Point operator-(const Point &a) const {
        return Point(x - a.x, y - a.y);
    }
    Point operator+(const Point &a) const {
        return Point(x + a.x, y + a.y);
    }
    Point operator*(const double a) const {
        return Point(x * a, y * a);
    }
    Point operator/(const double a) const {
        return Point(x / a, y / a);
    }
    bool operator<(const Point &a) const {
        if (fabs(x - a.x) > eps)	return x < a.x;
        if (fabs(y - a.y) > eps)	return y < a.y;
        return false;
    }
    bool operator==(const Point &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator!=(const Point &a) const {
        return !(fabs(x - a.x) < eps && fabs(y - a.y) < eps);
    }
    void read(int id = -1) {
        this->id = id;
    }
    double dist(Point b) {
        return hypot(x - b.x, y - b.y);
    }
    double dist2(Point b) {
        return (x - b.x) * (x - b.x) + (y - b.y) * (y - b.y);
    }
    void print() {
        printf("point (%lf, %lf)\n", x, y);
    }
};
struct Point3D {
    double x, y, z;
    Point3D(double a = 0, double b = 0, double c = 0):
    x(a), y(b), z(c) {}
    Point3D(Point p) {
        x = p.x, y = p.y, z = p.x * p.x + p.y * p.y;
    }
    Point3D operator-(const Point3D &a) const {
        return Point3D(x - a.x, y - a.y, z - a.z);
    }
    double dot(Point3D a) {
        return x * a.x + y * a.y + z * a.z;
    }
};
struct Edge {
    int id;
    list<Edge>::iterator twin;
    Edge(int id = 0) {
        this->id = id;
    }
};
int cmpZero(double v) {
    if (fabs(v) > eps)	return v > 0 ? 1 : -1;
    return 0;
}
double cross(Point o, Point a, Point b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
Point3D cross(Point3D a, Point3D b) { // normal vector
    return Point3D(a.y * b.z - a.z * b.y
                   , -a.x * b.z + a.z * b.x
                   , a.x * b.y - a.y * b.x);
}
int inCircle(Point a, Point b, Point c, Point p) {
    if (cross(a, b, c) < 0)
        swap(b, c);
    Point3D a3(a), b3(b), c3(c), p3(p);
    //	printf("%lf %lf %lf\n", a3.x, a3.y, a3.z);
    //	printf("%lf %lf %lf\n", b3.x, b3.y, b3.z);
    //	printf("%lf %lf %lf\n", c3.x, c3.y, c3.z);
    //	printf("%lf %lf %lf\n", p3.x, p3.y, p3.z);
    b3 = b3 - a3, c3 = c3 - a3, p3 = p3 - a3;
    Point3D f = cross(b3, c3); // normal vector
    return cmpZero(p3.dot(f)); // check same direction, in: < 0, on: = 0, out: > 0
}
int intersection(Point a, Point b, Point c, Point d) { // seg(a, b) and seg(c, d)
    return cmpZero(cross(a, c, b)) * cmpZero(cross(a, b, d)) > 0
    && cmpZero(cross(c, a, d)) * cmpZero(cross(c, d, b)) > 0;
}
class Delaunay {
public:
    list<Edge> head[MAXV]; // graph
    Point p[MAXV];
    int n, rename[MAXV];
    void init(int n, Point p[]) {
        for (int i = 0; i < n; i++)
            head[i].clear();
        for (int i = 0; i < n; i++)
            this->p[i] = p[i];
        sort(this->p, this->p + n);
        for (int i = 0; i < n; i++)
            rename[p[i].id] = i;
        this->n = n;
        divide(0, n - 1);
    }
    void addEdge(int u, int v) {
        head[u].push_front(Edge(v));
        head[v].push_front(Edge(u));
        head[u].begin()->twin = head[v].begin();
        head[v].begin()->twin = head[u].begin();
    }
    void divide(int l, int r) {
        if (r - l <= 1) { // #point <= 2
            for (int i = l; i <= r; i++)
                for (int j = i+1; j <= r; j++)
                    addEdge(i, j);
            return;
        }
        int mid = (l + r) /2;
        divide(l, mid);
        divide(mid + 1, r);
        
        list<Edge>::iterator it;
        int nowl = l, nowr = r;
        
        //		printf("divide %d %d\n", l, r);
        for (int update = 1; update; ) { // find left and right convex, lower common tangent
            update = 0;
            Point ptL = p[nowl], ptR = p[nowr];
            for (it = head[nowl].begin(); it != head[nowl].end(); it++) {
                Point t = p[it->id];
                double v = cross(ptR, ptL, t);
                if (cmpZero(v) > 0 || (cmpZero(v) == 0 && ptR.dist2(t) < ptR.dist2(ptL))) {
                    nowl = it->id, update = 1;
                    break;
                }
            }
            if (update)	continue;
            for (it = head[nowr].begin(); it != head[nowr].end(); it++) {
                Point t = p[it->id];
                double v = cross(ptL, ptR, t);
                if (cmpZero(v) < 0 || (cmpZero(v) == 0 && ptL.dist2(t) < ptL.dist2(ptR))) {
                    nowr = it->id, update = 1;
                    break;
                }
            }
        }
        
        addEdge(nowl, nowr); // add tangent
        //		printf("add base %d %d\n", nowl, nowr);
        for (int update = 1; true;) {
            update = 0;
            Point ptL = p[nowl], ptR = p[nowr];
            int ch = -1, side = 0;
            for (it = head[nowl].begin(); it != head[nowl].end(); it++) {
                //				ptL.print(), ptR.print(), p[it->id].print();
                if (cmpZero(cross(ptL, ptR, p[it->id])) > 0
                    && (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0))
                    ch = it->id, side = -1;
                //				printf("test L %d %d %d\n", nowl, it->id, inCircle(ptL, ptR, p[ch], p[it->id]));
            }
            for (it = head[nowr].begin(); it != head[nowr].end(); it++) {
                if (cmpZero(cross(ptR, p[it->id], ptL)) > 0
                    && (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0))
                    ch = it->id, side = 1;
                //				printf("test R %d %d %d\n", nowr, it->id, inCircle(ptL, ptR, p[ch], p[it->id]));
            }
            if (ch == -1)	break; // upper common tangent
            //			printf("choose %d %d\n", ch, side);
            if (side == -1) {
                for (it = head[nowl].begin(); it != head[nowl].end(); ) {
                    if (intersection(ptL, p[it->id], ptR, p[ch])) {
                        head[it->id].erase(it->twin);
                        head[nowl].erase(it++);
                    } else
                        it++;
                }
                nowl = ch;
                addEdge(nowl, nowr);
            } else {
                for (it = head[nowr].begin(); it != head[nowr].end(); ) {
                    if (intersection(ptR, p[it->id], ptL, p[ch])) {
                        head[it->id].erase(it->twin);
                        head[nowr].erase(it++);
                    } else
                        it++;
                }
                nowr = ch;
                addEdge(nowl, nowr);
            }
        }
    }
    
    vector< pair<int, int> > getEdge() {
        vector< pair<int, int> > ret;
        list<Edge>::iterator it;
        for (int i = 0; i < n; i++) {
            for (it = head[i].begin(); it != head[i].end(); it++) {
                if (it->id < i)
                    continue;
                //				printf("DG %d %d\n", i, it->id);
                ret.push_back(make_pair(p[i].id, p[it->id].id));
            }
        }
        return ret;
    }
} tool;
#define INF (1LL<<60)
Point p[MAXV];
long long ret[MAXV];
int main() {
    int testcase, n;
    long long x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lld %lld", &x, &y);
            p[i] = Point(x, y, i);
        }
        tool.init(n, p);
        vector< pair<int, int> > DG = tool.getEdge();
        for (int i = 0; i < n; i++) {
            ret[i] = INF;
        }
        for (int i = 0; i < DG.size(); i++) {
            x = DG[i].first, y = DG[i].second;
            long long v = (long long) (p[x].x - p[y].x) * (long long) (p[x].x - p[y].x) +
            (long long) (p[x].y - p[y].y) * (long long) (p[x].y - p[y].y);
            ret[x] = min(ret[x], v);
            ret[y] = min(ret[y], v);
        }
        for (int i = 0; i < n; i++) {
            printf("%lld\n", ret[i]);
        }
    }
    return 0;
}
/*
 2
 10
 17 41
 0 34
 24 19
 8 28
 14 12
 45 5
 27 31
 41 11
 42 45
 36 27
 15
 0 0
 1 2
 2 3
 3 2
 4 0
 8 4
 7 4
 6 3
 6 1
 8 0
 11 0
 12 2
 13 1
 14 2
 15 0
 */
Read More +
解題區/解題區 - UVa

UVa 1679 - Easy Geometry

Problem

在凸多邊形內部找一最大空白矩形 (平行兩軸)。多邊形頂點數最多 10 萬個。

Sample Input

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

Sample Output

1
2
3.5 2.5 5.5 4.5
1 1 7 4

Solution

三分內嵌三分再內嵌二分，幾何算法從函數觀點下手的有趣題目。

首先，觀察矩形在 x 軸的情況，觀察矩形左側 left.x，最大空白矩形面積呈現凸性，而在 left.x 下，right.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
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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <assert.h>
#include <vector>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    double length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
//		angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
#define MAXN 131072
#define INF 1e+30
Pt D[MAXN];
double ret;
Pt retLpt, retRpt;
double getArea(vector<Pt> &upper, vector<Pt> &lower, double lx, double rx) {
    int p, q;
    Pt a, b, c, d;
    p = (int) (lower_bound(upper.begin(), upper.end(), Pt(lx, INF)) - upper.begin());
    q = (int) (lower_bound(lower.begin(), lower.end(), Pt(lx, INF)) - lower.begin());
    assert(p > 0 && q > 0);
    a = getIntersect(Seg(Pt(lx, 1), Pt(lx, -1)), Seg(upper[p], upper[p-1]));
    b = getIntersect(Seg(Pt(lx, 1), Pt(lx, -1)), Seg(lower[q], lower[q-1]));
    p = (int) (lower_bound(upper.begin(), upper.end(), Pt(rx, INF)) - upper.begin());
    q = (int) (lower_bound(lower.begin(), lower.end(), Pt(rx, INF)) - lower.begin());
    assert(p > 0 && q > 0);
    c = getIntersect(Seg(Pt(rx, 1), Pt(rx, -1)), Seg(upper[p], upper[p-1]));
    d = getIntersect(Seg(Pt(rx, 1), Pt(rx, -1)), Seg(lower[q], lower[q-1]));
    double area = (rx - lx) * (min(a.y, c.y) - max(b.y, d.y));
    if (area > ret) {
        ret = area;
        retLpt = Pt(lx, max(b.y, d.y));
        retRpt = Pt(rx, min(a.y, c.y));
    }
    return area;
}
double search(vector<Pt> &upper, vector<Pt> &lower, double lx) {
    double l = lx, r = upper[upper.size()-1].x, mid, midmid, md, mmd;
    double ret = 0;
    for (int it = 0; it < 100; it++) {
        mid = (l + r)/2;
        midmid = (mid + r)/2;
        md = getArea(upper, lower, lx, mid);
        mmd = getArea(upper, lower, lx, midmid);
        ret = max(ret, md);
        if (md < mmd)
            l = mid;
        else
            r = midmid;
    }
    return ret;
}
double findMaxRectangle(vector<Pt> upper, vector<Pt> lower) {
    double mnx, mxx;
    mnx = upper[0].x, mxx = upper[upper.size()-1].x;
    double l = mnx, r = mxx, mid, midmid, md, mmd;
    double ret = 0;
    for (int it = 0; it < 100; it++) {
        mid = (l + r)/2;
        midmid = (mid + r)/2;
        md = search(upper, lower, mid);
        mmd = search(upper, lower, midmid);
        ret = max(ret, md);
        if (md < mmd)
            l = mid;
        else
            r = midmid;
    }
    return ret;
}
int main() {
    int N;
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++)
            D[i].read(); // clockwise order
        double mnx = INF, mxx = -INF;
        for (int i = 0; i < N; i++) {
            mnx = min(mnx, D[i].x);
            mxx = max(mxx, D[i].x);
        }
        vector<Pt> upper, lower;
        Pt Lpt = Pt(mnx, -INF), Rpt = Pt(mxx, INF);
        int lst, rst;
        for (int i = 0; i < N; i++) {
            if (cmpZero(D[i].x - mnx) == 0) {
                if (Lpt < D[i]) {
                    Lpt = D[i], lst = i;
                }
            }
            if (cmpZero(D[i].x - mxx) == 0) {
                if (D[i] < Rpt) {
                    Rpt = D[i], rst = i;
                }
            }
        }
        while (true) {
            upper.push_back(D[lst]);
            if (cmpZero(D[lst].x - mxx) == 0)
                break;
            lst = (lst + 1)% N;
        }
        while (true) {
            lower.push_back(D[rst]);
            if (cmpZero(D[rst].x - mnx) == 0)
                break;
            rst = (rst + 1)% N;
        }
        reverse(lower.begin(), lower.end());
        ret = 0;
        double area = findMaxRectangle(upper, lower);
//		printf("%lf\n", area);
        printf("%lf %lf %lf %lf\n", retLpt.x, retLpt.y, retRpt.x, retRpt.y);
    }
    return 0;
}
/*
4
5 1
2 4
3 7
7 3
5
1 1
1 4
4 7
7 4
7 1
*/
Read More +
解題區/解題區 - UVa

UVa 1676 - GRE Words Revenge

Problem

操作有二種，學習單詞以及給一篇文章，詢問學習單詞出現總次數。

輸入有經過加密，其加密的位移量為上一次詢問答案。

Sample Input

1
2
3
4
5
6
7
8
9
2
3
+01
+01
?01001
3
+01
?010
?011

Sample Output

1
2
3
4
5
Case #1:
2
Case #2:
1
0

Solution

如果是靜態，則可以想到 AC 自動機自然可以解決，但是 AC 自動機卻不支持動態建造。

為了滿足操作，可以利用快取記憶體的方式，進行分層，將小台 AC 自動機不斷重新建造，當小台 AC 自動機的節點總數大於某個值時，將其與大台 AC 自動機合併。合併操作必須是線性的，不要去重新插入每一個單詞。

特別小心有重複的單詞出現的小台或者是大台的操作，如果有重複必須忽略。雖然在理論上，分兩層操作的總複雜度高於倍增分層 (2, 4, 6, 8, …)，但是實作後，倍增分層一直 TLE。

然而這一題還有一種更困難的作法，詳見劉汝佳那本書，估計是一個動態後綴樹自動機 …

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#define MAXCHAR 2
#define MAXS (5000005)
#define MAXNODE 526288
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
class ACmachine {
public:
    struct Node {
        Node *next[MAXCHAR], *fail;
        int cnt, val;
        void init() {
            fail = NULL;
            cnt = val = 0;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size;
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = 0;
        root = getNode();
    }
    int toIndex(char c) {
        return c - '0';
    }
    void dfs(Node *p, Node *q) {
        for (int i = 0; i < MAXCHAR; i++) {
            if (q->next[i]) {
                Node *u = p->next[i], *v = q->next[i];
                if (u == NULL)
                    p->next[i] = getNode(), u = p->next[i];
                u->cnt |= v->cnt;
                dfs(u, v);
            }
        }
    }
    void merge(const ACmachine &other) {
        dfs(root, other.root);
    }
    void insert(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        p->cnt = 1;
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
    void build() { // AC automation
        queue<Node*> Q;
        Node *u, *p;
        Q.push(root), root->fail = NULL;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] == NULL)
                    continue;
                Q.push(u->next[i]);
                p = u->fail;
                while (p != NULL && p->next[i] == NULL)
                    p = p->fail;
                if (p == NULL)
                    u->next[i]->fail = root;
                else
                    u->next[i]->fail = p->next[i];
                u->next[i]->val = u->next[i]->fail->val + u->next[i]->cnt;
            }
        }
    }
    int query(const char str[]) {
        Node *u = root, *p;
        int matched = 0;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            while (u->next[idx] == NULL && u != root)
                u = u->fail;
            u = u->next[idx];
            u = (u == NULL) ? root : u;
            p = u;
            matched += p->val;
        }
        return matched;
    }
    void free() {
        return ;
        // owner memory pool version
        queue<Node*> Q;
        Q.push(root);
        Node *u;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] != NULL) {
                    Q.push(u->next[i]);
                }
            }
            delete u;
        }
    }
};
char s[MAXS];
void decodeString(char s[], int L) {
    static char buf[MAXS];
    int n = (int) strlen(s);
    L %= n;
    for (int i = L, j = 0; i < n; i++, j++)
        buf[j] = s[i];
    for (int i = 0, j = n - L; i < L; i++, j++)
        buf[j] = s[i];
    for (int i = 0; i < n; i++)
        s[i] = buf[i];
}
ACmachine cache, disk;
int main() {
    int testcase, cases = 0;
    int N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        printf("Case #%d:\n", ++cases);
        int L = 0; // encrypted key
        int cFlag = 0, dFlag = 0;
        cache.init(), disk.init();
        for (int i = 0; i < N; i++) {
            scanf("%s", s);
            decodeString(s+1, L);
            //            printf("%s\n", s);
#define THRESHOLD 4096
            if (s[0] == '+') {
                if (disk.find(s+1) || cache.find(s+1))
                    continue;
                cache.insert(s+1), cFlag = 0;
                if (cache.size > THRESHOLD) {
                    disk.merge(cache), dFlag = 0;
                    cache.free();
                    cache.init(), cFlag = 0;
                }
            } else {
                if (!cFlag) cache.build();
                if (!dFlag) disk.build();
                int ret = disk.query(s+1) + cache.query(s+1);
                printf("%d\n", ret);
                L = ret;
            }
        }
        disk.free(), cache.free();
    }
    return 0;
}
/*
 99999
 10
 +01
 +110
 ?010
 +110
 +00
 +0
 ?001001
 ?001001
 +110110
 ?1101001101
 
 6
 +01
 +110
 +110
 +00
 +0
 ?001001
 
 20
 +101001011
 ?110100
 +11010100
 ?0011001101
 +111011
 ?00010011
 +0111010110
 +0000101
 +0
 +11000
 ?1
 +1010101
 +0001
 +0110
 +0111101111
 ?1100
 +0111
 +1001
 ?0110111011
 ?1010010100
 
 10
 +00
 ?010110100
 +0100000100
 +111
 +000000
 ?0000110
 +110
 +00
 +0011
 ?101001
 
 5
 +0
 +1000100
 +01
 +0
 ?1110010011
 
 2
 3
 +01
 +01
 ?01001
 3
 +01
 ?010
 ?011
 */
Read More +