解題區►解題區 - UVa

UVa 1000 - Airport Configuration

Problem

機場有一個長形走廊，其中南側是搭機處，北側是下機處。

給予很多城市間旅客的數量，從城市 A 到城市 B 的旅客 X 人會在這個機場上進行轉換。

現在讀入機場的放置口設定 (順序)，請問每一種設定所產生的負載為何？

Sample Input

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

Sample Output

1
2
3
4
5
6
Configuration Load
    2         119
    1         122
Configuration Load
    2         300
    1         600

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
#include <stdio.h> 
#include <algorithm>
#include <vector>
#include <stdlib.h>
using namespace std;
int main() {
	int n;
	while (scanf("%d", &n) == 1 && n) {
		int A[32][32] = {}, x, city_id, dest, k;
		int north[32], south[32];
		for (int i = 0; i < n; i++) {
			scanf("%d %d", &city_id, &k);
			for (int j = 0; j < k; j++) {
				scanf("%d %d", &dest, &x);
				A[city_id][dest] += x;
			}
		}
		vector< pair<int, int> > ret;
		for (; scanf("%d", &city_id) == 1 && city_id;) {
			for (int i = 0; i < n; i++)
				scanf("%d", &north[i]);
			for (int i = 0; i < n; i++)
				scanf("%d", &south[i]);
			int load = 0;
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					load += A[north[i]][south[j]] * (abs(i - j) + 1);
			ret.push_back(make_pair(load, city_id));
		}
		sort(ret.begin(), ret.end());
		puts("Configuration Load");
		for (int i = 0; i < ret.size(); i++) {
			printf("%5d         %d\n", ret[i].second, ret[i].first);
		}
	}
	return 0;
}
Read More +
解題區►出題解題

[ACM 題目] 順來逆受

Problem

「其實雙親不准我在家裡畫漫畫。」
「是嗎？你都畫些什麼啊」
「乃是在下 x 大哥的原創本是也。」
「還有，薰是普通人」
「薰姐，功的反義詞是什麼？」
「什麼？是守嗎？」
「薰姐，剛才我說的話請你全忘記吧。」

在一個 N 個城市的國家，每個城市之間用 M 條邊相連。隨著時間，它們開始分裂，彼此會開始斷訊，無法聯絡到相鄰的城市。定時回報某個城市可以藉由間接或直接連絡的城市個數。

操作：

  • D i：移除輸入順序 i 個連接邊。
  • Q i：輸出城市 i 能聯絡的城市個數。

Sample Input

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

Sample Output

1
2
3
5
2
3

Solution

1
Read More +
學校課程►通識課程

[通識] 文明的進程 Week 6

公私領域的分裂，在不同的場合下，擁有的心理、情緒反應會有所不同。在某些場合 渴望愉悅 是必要的行為，抑制住反而有失禮儀。相反地， 否認愉悅 也是有場合是必須的。例如在家裡與在社交場所，在家裡可以因為有家人關係，表現得自然不過，如果什麼都抑制住，反而稱不上家人相處。而在社交場所，即使討厭一個人，也不能在臉上表現出來。

比中指 辱罵別人其實是很文明的舉止，因為並沒有實施暴力行為，是一種克制自我的行為。然而，比中指仍然稱不上是好的禮儀，但已經進步很多。

裸體代表的就是 自然 、 本相 ，查看其背後的涵義，這在很多理論上作為依據－抗議的主旨。 求自然 、 求真相 。

關於小組報告的大綱如下：

  • 為什麼主題有關文明化？
  • 看時間軸中，行為是怎麼形成的？
  • 約束人們做了哪些事情，思考了那些事情。
  • 約束－身分－環境，三者彼此之間的相互關係。
  • 在不同的時空背景下，又有什麼差別？是甚麼原因造成的？

特別注意報告要點：

  • 請說大家沒想過的，觀眾都等著你給的 surprise

本周報告

無處不在的文明教育（家庭、學校、公共空間與媒體）

家庭

談什麼？不談什麼？

首先是性教育、生與死，小時候不談這些，但隨著長大成人就會依依序序跟家裡長輩們談談，關於性、生後事 … 等一些比較嚴肅的話題。

看不看 A 片？寫不寫遺書？A 片的命名如何文明化？

PTT A片取什麼名字最安全？
大陸尋奇、舌尖上的日本、微積分、幫爸爸抓的、流體力學、日文初級音聽檢定 … 等

最後老師特別贊助：取名為 文明的進程 。

學校

環保意識的培養？

其實我認為學校文明教育從蔣公那時開始到現在就很有不同，學三民主義的課程到現在九年一貫課程，中間經歷了相當多的轉變。老一輩的人三民主義的日子，學著書上的精神，造就他們的價值觀。而我們學習到的只有宏觀歷史，而少了點歷史仇視，沒有嚮往開國元老，敬重政治人物的努力。

小學從品德教育開始，在國中之後便不怎麼有時間上這些，原本有 課 上，變成用條例規範，逐漸地，我們可以開始閱讀 規則 並且知道要遵守。

公共空間與媒體

媒體很有趣，從小看到大，可以說是一個群體訓練場，看著畫面猜著下面給的標題是否符合，已經快要變成一場遊戲，只要八九不離十，就有十足把握出門跟別人談談這些。在一個單向的管道中，從媒體為何而來？人們疏離開始說起，又或者不想跟別人談這個主題，需要一個媒介替你轉達！

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

UVa 12833 - Daily Potato

Problem

找到迴文是起頭和結尾都是字符 c，並且 c 在中間出現 X 次

參考範例輸入，六個詢問 (a, 2) (b, 2) (c, 2) … 他把字符弄再一起，例如第一個 (a, 2) 來說，起頭為 a 且中間要出現恰好 2 次 a，主字串中只看到 abccba 和 aa。

Sample Input

1
2
3
4
5
6
1
8
abccbaab
6
abcabc
2 2 2 1 1 3

Sample Output

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

Solution

因為要恰好 X 個，對於每組詢問基本上只會有 n 個位置，當作起頭，然後 O(1) 檢查迴文即可。就算分 26 組下去，還是 TLE。

O(1) 檢查的方式按照 manacher’s algorithm 的做法，

manacher’s algorithm 算法核心，在 O(n) 時間內找到最長迴文子字串。


圖片與算法來源 here

可以將每組詢問壓到 O(log n) 以下，我們知道從每一個中心展開的最長迴文，也代表可以記錄展開的時候，恰好以某個字符開頭的最大總數。

對於每一組詢問，保證每一個中心最多當過一次迴文中心，因此只要總數大於等於指定個數，保證可以湊出來。

其 A[i][c] 表示以位置 i 為中心，起頭是字符 c，出現最多的 c 個數。之後問 c x 輸出有多少 A[i][c] >= 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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXL 262144
char S[MAXL], C[MAXL], T[MAXL];
int dp[MAXL], n, m;
int A[MAXL][26], SUM[MAXL][26];
void exbuild(char S[]) { // manacher's algorithm
	n = strlen(S), m = 2 * n + 1;
    int mx = 0, idx = 0;
    int ans = 0;
	T[0] = '$', T[m] = '#', T[m + 1] = '\0';
	for (int i = 0; i < n; i++)
    	T[i * 2 + 1] = '#', T[i * 2 + 2] = S[i];
    //
    memset(SUM[0], 0, sizeof(SUM[0]));
    for (int i = 1; i < m; i++) {
    	memcpy(SUM[i], SUM[i-1], sizeof(SUM[0]));
    	if ('a' <= T[i] && T[i] <= 'z')
    		SUM[i][T[i] - 'a']++;
    }
    //
    for (int i = 1; i < m; i++) {
        if (mx > i) {
        	memcpy(A[i], A[2 * idx - i], sizeof(A[2 * idx - i]));
            dp[i] = min(dp[2 * idx - i], mx - i);
            if (dp[2 * idx - i] >= mx - i) {
            	int r = idx - (mx - idx), l = 2 * idx - i - dp[2 * idx - i];
            	for (int j = 0; j < 26; j++) {
            		A[i][j] -= (SUM[r][j] - SUM[l][j]) * 2;
            	}
        	}
        } else {
        	for (int j = 0; j < 26; j++)
        		A[i][j] = SUM[i][j] - SUM[i-1][j];
            dp[i] = 1;
        }
        for(; T[i-dp[i]] == T[i+dp[i]]; dp[i]++)
        	if ('a' <= T[i+dp[i]] && T[i+dp[i]] <= 'z')
				A[i][T[i-dp[i]] - 'a'] += 2;
        if(dp[i] + i > mx)		mx = dp[i] + i, idx = i;
    }
//    for (int i = 1, j = 0; i < m; i ++, j++)
//    	printf("[%02d] %c %d\n", i, T[i], dp[i]);
}
vector<int> M[2][26];
void prepare() {
	for (int i = 0; i < 26; i++)
		M[0][i].clear(), M[1][i].clear();
	for (int i = 1; i < m; i++) {
//		printf("%c ", T[i]);
		for (int j = 0; j < 26; j++) {
			M[A[i][j]&1][j].push_back(A[i][j]);
//			printf("%d ", A[i][j]);
		}
//		puts("");
	}
	for (int i = 0; i < 26; i++) {
		sort(M[0][i].begin(), M[0][i].end());
		sort(M[1][i].begin(), M[1][i].end());
	}
}
void query(int x, char c) {
	if (x == 0)	{puts("0"); return;}
	int p = (int) (lower_bound(M[x&1][c - 'a'].begin(), M[x&1][c - 'a'].end(), x) - M[x&1][c - 'a'].begin());
	printf("%d\n", int(M[x&1][c - 'a'].size() - p));
}
int main() {
	freopen("in.txt", "r+t", stdin);
	freopen("out2.txt", "w+t", stdout); 
	int testcase, N, Q, cases = 0;
	int x;
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d %s", &N, S);
		scanf("%d %s", &Q, C);
		exbuild(S);
		prepare();
		printf("Case %d:\n", ++cases);
		for (int i = 0; i < Q; i++) {
			scanf("%d", &x);
			query(x, C[i]);
		}
	}
    return 0;
}
/*
1
8
abccbaab
6
abcabc
2 2 2 1 1 3
1000
6
abaaba
7
aaaaaab
5 4 3 2 1 0 2
123
10
ccecabebcb
10
ebddcdacad
5 6 2 5 5 5 5 1 9 9
10
abbbbeaaba
10
cbabcabcec
2 0 1 8 5 6 2 4 8 1
10
baddaeaecb
10
bbdebdbedd
1 5 5 6 2 9 9 1 5 0
*/
Read More +
解題區►解題區 - UVa

UVa 12830 - A Football Stadium

Problem

在一個 L x W 的區域中，有 N 個點障礙物，要在其中找到一個最大空白矩形，中間不包含任何障礙物。

Sample Input

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

Sample Output

1
2
3
Case 1: 18
Case 2: 81
Case 3: 25

Solution

x, y 軸兩個都要做嘗試基底的動作。考慮一下都是 x = ? 當做基底時, 如果 y 值與窮舉點一樣, 那麼可選上或選下, 但無法決定哪個好，但是可以被決定於 y = ? 當做基底時的窮舉。整體效率是 O(n*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
#include <stdio.h>
#include <algorithm>
using namespace std;
// same 10043 - Chainsaw Massacre.
struct Pt {
    int x, y;
    Pt(int a = 0, int b = 0):
        x(a), y(b){}
    bool operator<(const Pt &p) const {
        if(p.x != x)
            return x < p.x;
        return y < p.y;
    }
};
bool cmp(Pt a, Pt b) {
    if(a.y != b.y)
        return a.y < b.y;
    return a.x < b.x;
}
Pt tree[3000];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        int h, w;
        int x, y;
        scanf("%d %d", &h, &w);
        int op, i, j;
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        	scanf("%d %d", &tree[i].x, &tree[i].y);
        tree[n++] = Pt(0, 0);
        tree[n++] = Pt(h, w);
        tree[n++] = Pt(h, 0);
        tree[n++] = Pt(0, w);
		sort(tree, tree+n);
        int area = 0;
        for(i = 0; i < n; i++) {
            int mny = 0, mxy = w;
            for(j = i+1; j < n; j++) {
                area = max(area, (tree[j].x-tree[i].x)*(mxy-mny));
                if(tree[j].x == tree[i].x)
                    continue;
                if(tree[j].y > tree[i].y)
                    mxy = min(mxy, tree[j].y);
                else
                    mny = max(mny, tree[j].y);
            }
        }
        sort(tree, tree+n, cmp);
        for(i = 0; i < n; i++) {
            int mnx = 0, mxx = h;
            for(j = i+1; j < n; j++) {
                area = max(area, (tree[j].y-tree[i].y)*(mxx-mnx));
                if(tree[j].y == tree[i].y)
                    continue;
                if(tree[j].x > tree[i].x)
                    mxx = min(mxx, tree[j].x);
                else
                    mnx = max(mnx, tree[j].x);
            }
        }
        printf("Case %d: %d\n", ++cases, area);
    }
    return 0;
}
Read More +
解題區►解題區 - UVa

UVa 1479 - Graph and Queries

Problem

給 N 個點、M 條邊的無向圖，現在有三種操作：

  • D X ：刪除輸入編號 X 的邊
  • Q X K ：詢問與 X 相同連通元件中，節點權重第 K 大。
  • C X V ：將節點 X 權重修改成 V。

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
3 3 
10 
20 
30 
1 2 
2 3 
1 3 
D 3 
Q 1 2 
Q 2 1 
D 2 
Q 3 2 
C 1 50
Q 1 1
E
3 3 
10 
20 
20 
1 2 
2 3 
1 3 
Q 1 1 
Q 1 2 
Q 1 3 
E 
0 0

Sample Output

1
2
Case 1: 25.000000 
Case 2: 16.666667

Solution

可以看出，如果順著做會比較繁瑣，分裂總是比合併來的痛苦，根據并查集的概念，將其變成合併操作。

我們逆著輸入順序處理，根據離線的方式，可以預測最後會分裂到甚麼情況、最後某個節點帶什麼權重，分別將其建造一個平衡樹。刪除一條邊相當於加入一條邊，并查集看出好比兩個平衡樹合併，修改一個節點權重相當於回朔前一個版本的值。

而要在平衡樹中查找第 k 大元素不能用 STL，這裡用比較簡單的 treap，編程複雜度比較低。

treap 的效率取決於每個節點攜帶的隨機權重，事先用內存池撒過一次亂數，之後需要再從內存池提取，之後就不撒亂數，蛋疼的是竟然活生生掛掉了。還是乖乖 srand(514); 偷懶不想用 new 加快效率什麼的，實在囧

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXN 65536
#define MAXM 65536
#define MAXQ (1<<20)
struct node;
node *null;
struct node {
    node *lson, *rson;
    int key, value, size;
    
    node(int x = 0, int s = 1):key(x), size(s) {
        lson = rson = null;
    }
    void update() {
        if (this != null)
            size = lson->size + rson->size + 1;
    }
} nodes[MAXQ], *root[MAXN];
struct treap {
    int bufIdx;
    node *getNode(int val) {
        node *ret = &nodes[bufIdx++];
        *ret = node(val);
        ret->value = rand();
        return ret;
    }
    void rotate(node* &a, int dir) { // dir {0: left, 1: right}
        node *p;
        if (dir == 0) {
            p = a->rson;
            a->rson = p->lson;
            p->lson = a;
        } else {
            p = a->lson;
            a->lson = p->rson;
            p->rson = a;
        }
        a->update(), p->update();
        a = p;
    }
    void insert(node* &a, int val) {
        if (a == null)
            a = getNode(val);
        else {
            if (val < a->key) {
                insert(a->lson, val);
                if (a->lson->value > a->value)
                    rotate(a, 1);
            } else {
                insert(a->rson, val);
                if (a->rson->value > a->value)
                    rotate(a, 0);
            }
        }
        a->update();
    }
    void remove(node* &a, int val) {
        if (a->key == val) {
            if (a->lson == null)
                a = a->rson;
            else if (a->rson == null)
                a = a->lson;
            else {
                if (a->lson->value > a->rson->value)
                    rotate(a, 1), remove(a->rson, val);
                else
                    rotate(a, 0), remove(a->lson, val);
            }
        } else if (val < a->key) {
            remove(a->lson, val);
        } else {
            remove(a->rson, val);
        }
        a->update();
    }
    void merge(node* &from, node* &to) {
        if (from->lson != null)
            merge(from->lson, to);
        if (from->rson != null)
            merge(from->rson, to);
        insert(to, from->key); // delete node `from`, need use delete replace pool.
    }
    node* kth_element(node* &a, int k) {
        if (a == null || k <= 0 || k > a->size)	return null;
        if (k == a->lson->size + 1)
            return a;
        if (k <= a->lson->size)
            return kth_element(a->lson, k);
        else
            return kth_element(a->rson, k - a->lson->size - 1);
    }
    node* rkth_element(node* &a, int k) {
        if (a == null || k <= 0 || k > a->size)	return null;
        if (k == a->rson->size + 1)
            return a;
        if (k <= a->rson->size)
            return rkth_element(a->rson, k);
        else
            return rkth_element(a->lson, k - a->rson->size - 1);
    }
    int lower_dist(node* &a, int val) {
        if (a == null)	return 1;
        if (a->value < val)
            return a->lson->size + 1 + lower_dist(a->rson, val);
        else
            return lower_dist(a->lson, val);
    }
    int upper_dist(node* &a, int val) {
        if (a == null)	return 1;
        if (a->value > val)
            return a->rson->size + 1 + upper_dist(a->lson, val);
        else
            return upper_dist(a->rson, val);
    }
    void print(node *ver) {
        if (ver == null)	return;
        print(ver->lson);
        printf("print %d %d\n", ver->key, ver->size);
        print(ver->rson);
    }
    void init() {
        bufIdx = 0;
        null = &nodes[bufIdx++];
        null->size = 0, null->lson = null->rson = null, null->value = 0;
    }
} tree;
char cmd[MAXQ][4];
int QX[MAXQ], QY[MAXQ], edgeX[MAXM], edgeY[MAXM], w[MAXN];
int parent[MAXN], weight[MAXN];
int findp(int x) {
    return parent[x] == x ? x : (parent[x] = findp(parent[x]));
}
void joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)	return;
    if (weight[x] > weight[y]) {
        parent[y] = x, weight[x] += weight[y];
        tree.merge(root[y], root[x]);
        
    } else {
        parent[x] = y, weight[y] += weight[x];
        tree.merge(root[x], root[y]);
    }
}
void initDisjointSet(int n)  {
    for (int i = 1; i <= n; i++)
        parent[i] = i, weight[i] = 1;
}
void changeVertex(int u, int val) {
    int r = findp(u);
    tree.remove(root[r], w[u]);
    tree.insert(root[r], val);
    w[u] = val;
}
int main() {
    //    freopen("in.txt", "r+t", stdin);
    //    freopen("out.txt", "w+t", stdout);
    int n, m, q, t;
    int cases = 0;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        tree.init();
        for (int i = 1; i <= n; i++)
            scanf("%d", &w[i]);
        for (int i = 1; i <= m; i++)
            scanf("%d %d", &edgeX[i], &edgeY[i]);
        int exists[MAXM] = {};
        for (int i = 1; i <= m; i++)
            exists[i] = 1;
        for (q = 0; scanf("%s", cmd[q]) == 1 && cmd[q][0] != 'E'; q++) {
            if (cmd[q][0] == 'D')
                scanf("%d", &QX[q]), exists[QX[q]] = 0;
            else if (cmd[q][0] == 'C')
                scanf("%d %d", &QX[q], &QY[q]), t = QY[q], QY[q] = w[QX[q]], w[QX[q]] = t;
            else if (cmd[q][0] == 'Q')
                scanf("%d %d", &QX[q], &QY[q]);
        }
        
        for (int i = 1; i <= n; i++)
            root[i] = null;
        for (int i = 1; i <= n; i++)
            tree.insert(root[i], w[i]);
        initDisjointSet(n);
        for (int i = 1; i <= m; i++)
            if (exists[i] == 1)
                joint(edgeX[i], edgeY[i]);
        
        double ret = 0, cnt = 0;
        for (int i = q - 1; i >= 0; i--) {
            if (cmd[i][0] == 'D')
                joint(edgeX[QX[i]], edgeY[QX[i]]);
            else if (cmd[i][0] == 'C')
                changeVertex(QX[i], QY[i]);
            else if (cmd[i][0] == 'Q') {
                cnt++;
                node* v = tree.rkth_element(root[findp(QX[i])], QY[i]);
                if (v == null)	/*puts("undefined")*/;
                else 			ret += v->key/*, printf("kth %d\n", v->key)*/;
            }
        }
        ret /= cnt;
        printf("Case %d: %lf\n", ++cases, ret);
    }
    return 0;
}
/*
 3 3
 10
 20
 30
 1 2
 2 3
 1 3
 D 3
 Q 1 2
 Q 2 1
 D 2
 Q 3 2
 C 1 50
 Q 1 1
 E
 */
Read More +
解題區►解題區 - UVa

UVa 12825 - Happy Robot

Problem

機器人一開始在原點 (0, 0)，並且面向東方 (East)。會按照以下三種指令做事。

  • L: turn left 方向往左轉，ex. 往北變成往西
  • R: turn right 方向往右轉，ex. 往北變成往東
  • F: go forward one step，依照當前方向往前走一步

指令中會有 ? 表示可以插入三種其中一種操作，請問機器人分別能走到的 x, y 最大最小值為何。

Sample Input

1
2
3
F?F
L??
LFFFRF

Sample Output

1
2
3
Case 1: 1 3 -1 1
Case 2: -1 1 0 2
Case 3: 1 1 3 3

Solution

動態規劃，把 x, y 分開考慮，同時維護 4 個方向的最大最小值。

定義 dp[i][dir][min/max] : 執行前 i 個指令，在 dir 方向上的最大最小值。

遞迴公式請參照代碼。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int main() {
	char s[1024];
	int cases = 0;
	while (scanf("%s", s) == 1) {
		int dpx[1024][4][2], dpy[1024][4][2];
		// [N E S W][min/max]
		const int dx[4] = {0, 1, 0, -1};
		const int dy[4] = {1, 0, -1, 0};
		int n = strlen(s);
		for (int i = 0; i <= n; i++)
			for (int j = 0; j < 4; j++) {
				dpx[i][j][0] = INF, dpx[i][j][1] = -INF;
				dpy[i][j][0] = INF, dpy[i][j][1] = -INF;
			}
		dpx[0][1][0] = 0, dpx[0][1][1] = 0;
		dpy[0][1][0] = 0, dpy[0][1][1] = 0;
		for (int i = 0; i < n; i++) {
			if (s[i] == 'F' || s[i] == '?') {
				for (int j = 0; j < 4; j++) {
					dpx[i+1][j][0] = min(dpx[i+1][j][0], dpx[i][j][0] + dx[j]);
					dpx[i+1][j][1] = max(dpx[i+1][j][1], dpx[i][j][1] + dx[j]);
					dpy[i+1][j][0] = min(dpy[i+1][j][0], dpy[i][j][0] + dy[j]);
					dpy[i+1][j][1] = max(dpy[i+1][j][1], dpy[i][j][1] + dy[j]);
				}
			} 
			if (s[i] == 'R' || s[i] == '?') {
				for (int j = 0; j < 4; j++) {
					dpx[i+1][(j+1)%4][0] = min(dpx[i+1][(j+1)%4][0], dpx[i][j][0]);
					dpx[i+1][(j+1)%4][1] = max(dpx[i+1][(j+1)%4][1], dpx[i][j][1]);
					dpy[i+1][(j+1)%4][0] = min(dpy[i+1][(j+1)%4][0], dpy[i][j][0]);
					dpy[i+1][(j+1)%4][1] = max(dpy[i+1][(j+1)%4][1], dpy[i][j][1]);
				}
			}
			if (s[i] == 'L' || s[i] == '?') {
				for (int j = 0; j < 4; j++) {
					dpx[i+1][(j+3)%4][0] = min(dpx[i+1][(j+3)%4][0], dpx[i][j][0]);
					dpx[i+1][(j+3)%4][1] = max(dpx[i+1][(j+3)%4][1], dpx[i][j][1]);
					dpy[i+1][(j+3)%4][0] = min(dpy[i+1][(j+3)%4][0], dpy[i][j][0]);
					dpy[i+1][(j+3)%4][1] = max(dpy[i+1][(j+3)%4][1], dpy[i][j][1]);
				}
			}
//			for (int j = 0; j < 4; j++) {
//				printf("%d %d %d %d\n", dpx[i][j][0], dpx[i][j][1], dpy[i][j][0], dpy[i][j][1]);
//			}
//			puts("--");
		}
		int mnx = INF, mxx = -INF, mny = INF, mxy = -INF;
		for (int i = 0; i < 4; i++) {
			mnx = min(mnx, dpx[n][i][0]);
			mxx = max(mxx, dpx[n][i][1]);
			mny = min(mny, dpy[n][i][0]);
			mxy = max(mxy, dpy[n][i][1]);
		}
		printf("Case %d: %d %d %d %d\n", ++cases, mnx, mxx, mny, mxy);
	}
	return 0;
}
Read More +
解題區►出題解題

[ACM 題目] 動態前綴

Problem

某 M 「給一個字串 S，接著詢問操作 [l, r] 告訴區間內是否剛好為一個迴文？」
學弟 「用最長迴文的方式去想嗎？」
某 M 「我沒有標準答案哦 wwww，吾等還在想能不能離線 O(1)。」

暗自敲著 UVa 另外一題類似題說著，就算能 O(1) 檢查迴文，區間還是要窮舉 O(n)，在此宣告某 M 陣亡－ Time Limit 。

某 M 心想，假解也是不錯選擇，單純詢問迴文肯定會被 manacher’s algorithm 秒掉 (O(1) - O(n))。如果詢問 [l, r] 的子字串是否符合 pattern AA (例如 abcabc，其中 A = abc)，也會被 suffix array、suffix tree 解決 (O(log n) - O(n log n)/O(n))。

百般無奈之下，也許這題就這樣定好了：

C p x：將字串位置 p 修改成字符 x。
Q p q：求子字串 S.substr(p) 和 S.substr(q) 的最長共同前綴長度。

1
2
3
4
5
6
7
8
void change(char s[], int p, int x) {
	s[p] = x;
}
int query(char s[], int p, int q) {
	int ret = 0;
	for (; s[p] == s[q] && s[p] && s[q]; p++, q++, ret++);
	return ret;
}

Sample Input

1
2
3
4
5
abcdabcc
3
Q 0 4
C 3 c
Q 0 4

Sample Output

1
2
3
4

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
const long long mod = 100000007LL;
#define MAXN (1<<17)
char S[MAXN];
long long base[MAXN];
long long tree[MAXN<<1];
long long build(int k, int l, int r) {
	assert(l <= r);
	if (l == r)
		return tree[k] = (S[l] % mod);
	int m = (l + r)/2;
	build(k<<1, l, m);
	build(k<<1|1, m+1, r);
	tree[k] = (tree[k<<1] * base[r - m] + tree[k<<1|1]) %mod;
}
void modify(int k, int l, int r, int x, int v) {
	if (l == r) {
		tree[k] = v;
		return;
	}
	int m = (l + r)/2;
	if (x <= m)
		modify(k<<1, l, m, x, v);
	else
		modify(k<<1|1, m+1, r, x, v);
	tree[k] = (tree[k<<1] * base[r - m]%mod + tree[k<<1|1]) %mod;
}
long long query(int k, int l, int r, int x, int y) {
	assert(l >= 0 && l <= r);
	if (x <= l && r <= y) {
		return tree[k];
	}
	int m = (l + r)/2;
	if (y <= m)
		return query(k<<1, l, m, x, y);
	else if(x > m)
		return query(k<<1|1, m+1, r, x, y);
	else {
		long long p, q;
		p = query(k<<1, l, m, x, y);
		q = query(k<<1|1, m+1, r, x, y);
		return (p * base[min(y, r) - m]%mod + q) %mod;
	}
}
int main() {
	freopen("in.txt", "r+t", stdin);
	freopen("out.txt", "w+t", stdout); 
	base[0] = 1;
	for (int i = 1; i < MAXN; i++) 
		base[i] = (base[i-1] * 2)%mod;
	char cmd[8], s[8];
	int Q, p, q, n;
	while (scanf("%s", S) == 1) {
		n = strlen(S);
		build(1, 0, n - 1);
		scanf("%d", &Q);
		for (int i = 0; i < Q; i++) {
			scanf("%s", cmd);
			if (cmd[0] == 'Q') {
				scanf("%d %d", &p, &q);
				if (p == q) {
					printf("%d\n", n - p);
					continue;
				} else if (S[p] != S[q]) {
					puts("0");
					continue;
				}
				int l = 0, r = min(n - p, n - q) - 1, m, ret = 0;
				long long hp, hq;
				while (l <= r) {
					m = (l + r)/2;
					hp = query(1, 0, n-1, p, p + m);
					hq = query(1, 0, n-1, q, q + m);
					if (hp == hq)
						l = m + 1, ret = m;
					else
						r = m - 1;
				}
				printf("%d\n", ret + 1);
			} else {
				scanf("%d %s", &p, s);
				S[p] = s[0];
				modify(1, 0, n - 1, p, s[0]);
			}
		}
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12538 - Version Controlled IDE

Problem

題目有三種字符串的操作：

  • 1 p s: 在當前字串位置 p 後插入 s 字串。
  • 2 p c: 將當前字串位置 p 後面連續 c 個字符移除。
  • 3 v p c: 在版本號 v 的字串中，在位置 p 之後印出 c 個字元。

由於怕離線處理，因此輸入的數值會進行加密，加密的原則－每個數字會增加數值 d，其 d 為當前打印字符 c 的個數。

Sample Input

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

Sample Output

1
2
3
bcdef
bcg
bxyc

Solution

代碼算法詳見 《可持久化數據結構研究》杭州外國語學校－陳立杰　那篇所寫的 Treap(樹堆)。

這題的離線作法是預先紀錄需要的版本號位置，在邊處理的時候隨時保存答案，以免造成記憶體過大儲存。既然他進行了加密，可見我們不能把每一個版本號的字串儲存，這就是其麻煩之處。

接下來說明的作法，是將每個字符當作節點，在一個二元搜尋樹上，利用中序走訪的結果表示一個字串。

可持久化 Treap

Treap 主要概念是平衡樹，也就是儲存有序的結構，支持插入、刪除、查找數字。冠上可持久化平衡樹，就是一個維護歷史版本的平衡樹。

Treap 每一個節點具有 <key, value>，仍然是一個二元搜尋樹，但同時也是一個 heap。單純看 key 呈現一個二元搜尋樹，如果看 value 則會是 heap。key 跟 value 是挺像的，我的代碼誤打了名稱。而 Treap 效率完全取決於隨機決定的 value 值進行平衡調整。

對於可持久化 Treap 而言，是一個具有平衡樹特性，但不需要做任何旋轉操作的樹。每一次將修改操作替代為一個增加節點的方式 ( 用增加替代修改 的精神)，在記憶體耗量就是 O(m log n)，m 是其操作，log n 是樹內結構的期望深度。每一次操作期望只修改 log n 個節點。

操作定義

這裡只會講到可持久化，拆分成兩個操作，而原本的插入、刪除、查找都可以利用這兩個操作完成。

$$\text{ treap merge(treap a, treap b) } \\ < \text{treap, treap} > \text{ split(treap a, int n) }$$
  • merge a b : 將兩個 Treap a, b 進行合併成一個 Treap。
  • split a n : 將 Treap a 拆成前 n 小個元素為一個 Treap，剩餘為另一個 Treap。

插入一個元素相當於 split 一次，將兩個部分中間放置一個元素後，依序將其 merge 起來。

刪除一個元素相當於 split 兩次，將中間單一元素的 Treap 忽略，將第一和第三部分的 Treap merge 起來。

merge()

$$\text{ treap merge(treap a, treap b) }$$
  • 若 a, b 其中一個是 null treap，回傳另一個非空樹。
  • 若 $key(a) \le key(b)$
    讓 a 的左子樹不變，而 a 的右子樹變成 $merge(right(a), b)$ 的 treap 結果。
  • 若 $key(a) >key( b)$
    讓 b 的右子樹不變，而 b 的左子樹變成 $merge(a, left(b))$ 的 treap 結果。

split()

$$< \text{treap, treap} > \text{ split(treap a, int n) }$$
  • 若 $size(left(a)) \le n \\ \left \{ l, r \right \} = split(left(a), n)$ ，並且將 a 的左子樹改成 r。返回結果 $\left \{ l, a \right \}$
  • 若 $size(left(a)) > n \\ \left \{ l, r \right \} = split(right(a), n - size(left(a)) - 1)$ ，並且將 a 的右子樹改成 l。返回結果 $\left \{ a, r \right \}$

另解

在 g++ 头文件中，<ext/rope>中有成型的块状链表，在 using namespace __gnu_cxx; 空间中，其操作十分方便。

不用手刻，而且歷史版本的儲存速度也是 O(1)，裡面應該進行了很多記憶體控管。沒有細讀過，但是其支持相當厲害。看到這一篇代碼被不到百行的流程搞定。不過塊狀鏈表的複雜度仍然是 $O(n^{1.5})$，比起隨機的可持久化 treap 還是慢了些。

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
#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXN (1<<23)
#define MAXQ 65536
struct node;
node *null;
struct node {
	node *lson, *rson;
	int key, size;
	char label; // user def label
	
	node(char c = 0, int s = 1):label(c), size(s) {
		lson = rson = null;
		key = rand();
	}
	void update() {
		size = 1;
		size += lson->size + rson->size;	
	}
} nodes[MAXN], *root[MAXQ];
struct treap {
	int bufIdx = 0;
	int prob_c; // this problem need.
	node* getNode(node* u) {
		node *ret;
		if (u == null) {
			return u;
		} else {
			ret = &nodes[bufIdx++];
			*ret = *u;
			return ret;
		}
	}
	node* merge(node* a, node* b) {
		if (a == null)	return getNode(b);
		if (b == null)	return getNode(a);
		node *ret;
		if (a->key < b->key) {
			ret = getNode(a);
			ret->rson = merge(a->rson, b);
		} else {
			ret = getNode(b);
			ret->lson = merge(a, b->lson);
		}
		ret->update();
		return ret;
	}
	void split(node* a, node* &l, node* &r, int n) {
		if (n == 0) {
			l = null, r = getNode(a);
		} else if (a->size <= n) {
			l = getNode(a), r = null;
		} else if (a->lson->size >= n) {
			r = getNode(a);
			split(a->lson, l, r->lson, n);
			r->update();
		} else {
			l = getNode(a);
			split(a->rson, l->rson, r, n - (a->lson->size) - 1);
			l->update();
		}
	}
	void build(node* &a, int l, int r, char s[]) {
		if (l > r)	return ;
		int m = (l + r) /2;
		node u = node(s[m]), *p = &u, *q;
		a = getNode(p), p = null, q = null;
		build(p, l, m-1, s);
		build(q, m+1, r, s);
		p = merge(p, a);
		a = merge(p, q);
		a->update();
	}
	void insert(node* &a, node *ver, int pos, char s[]) {
		node *p, *q, *r;
		int n = strlen(s);
		split(ver, p, q, pos);
		build(r, 0, n - 1, s);
		p = merge(p, r);
		a = merge(p, q);
	}
	void remove(node* &a, node *ver, int pos, int n) {
		node *p, *q, *r;
		split(ver, p, q, pos - 1);
		split(q, q, r, n);
		a = merge(p, r);
	}
	void print(node *ver) {
		if (ver == null)	return;
		print(ver->lson);
		if (ver->label == 'c')	prob_c++; // this problem need
		putchar(ver->label);
		print(ver->rson);
	}
	void printdebug(node *ver) {
		if (ver == null)	return;
		print(ver->lson);
		putchar(ver->label);
		print(ver->rson);
	}
	void traversal(node *ver, int pos, int n) {
		node *p, *q, *r;
		split(ver, p, q, pos - 1);
		split(q, q, r, n);
		print(q);
	}
	void init() {
		bufIdx = 0; 
		prob_c = 0;
		null = &nodes[bufIdx++];
		null->size = 0;
	}
} tree;
int main() {
	int n;
	while (scanf("%d", &n) == 1) {
		tree.init();
		int cmd, v, p, c, verIdx;
		char s[128];
		root[verIdx = 0] = null;
		for (int i = 0; i <= n; i++)
			root[i] = null;
		for (int i = 0; i < n; i++) {
			scanf("%d", &cmd);
			if (cmd == 1) {
				scanf("%d %s", &p, s);
				p -= tree.prob_c;
				tree.insert(root[verIdx + 1], root[verIdx], p, s);
				verIdx++;
			} else if (cmd == 2) {
				scanf("%d %d", &p, &c);
				p -= tree.prob_c, c -= tree.prob_c;
				tree.remove(root[verIdx + 1], root[verIdx], p, c);
				verIdx++;
			} else {
				scanf("%d %d %d", &v, &p, &c);
				v -= tree.prob_c, p -= tree.prob_c, c -= tree.prob_c;
				tree.traversal(root[v], p, c);
				puts("");
			}
		}
	}
	return 0;
}
/*
6
1 0 abcdefgh
2 4 3
3 1 2 5
3 3 3 4
1 4 xy
3 5 4 6
*/
Read More +
解題區►解題區 - UVa

UVa 12821 - Double Shortest Paths

Problem

給一張圖，點與點之間有條有向路徑，每條路徑上有兩個權重，第一次從起點到終點經過這條邊時，消耗 d，而如果在第二次經過時，將消耗 d + a。保證 d <= d+a。(第二次經過同一條邊時，困難度會增加。)

求兩條從起點到終點的路徑花費最小。

Sample Input

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

Sample Output

1
2
Case 1: 23
Case 2: 24

Solution

直接套用最少費用流，對於輸入給定的一條邊 u->v，增加兩條容量為 1，路徑花費分別為 d 和 d+a，求起點到終點流量 = 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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <deque>
using namespace std;
struct Node {
    int x, y, cap, cost;// x->y, v
    int next;
} edge[100005];
int e, head[505], dis[505], prev[505], record[505], inq[505];
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++;
}
int mincost(int s, int t) {
    int mncost = 0, flow, totflow = 0;
    int i, x, y;
    while(1) {
        memset(dis, 63, sizeof(dis));
        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;
                    prev[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 = oo;
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for(x = t; x != s; x = prev[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 mncost;
}
int main() {
    int n, m, cases = 0;
    int x, y, d, a;
    while(scanf("%d %d", &n, &m) == 2) {
        e = 0;
        memset(head, -1, sizeof(head));
        int source = n + 1, sink = n + 2;
        for (int i = 0; i < m; i++) {
        	scanf("%d %d %d %d", &x, &y, &d, &a);
        	addEdge(x, y, 1, d);
        	addEdge(x, y, 1, d + a);
        }
        addEdge(source, 1, 2, 0);
        addEdge(n, sink, 2, 0);
        printf("Case %d: %d\n", ++cases, mincost(source, sink));
    }
    return 0;
}
/*
4 4
1 2 5 1
2 4 6 0
1 3 4 0
3 4 9 1
4 4
1 2 5 10
2 4 6 10
1 3 4 10
3 4 9 10
*/
Read More +