解題區►解題區 - UVa

UVa 12804 - The Necronomicon of Computing

Problem

給一段簡單的組合語言，有三種指令。

  1. 判斷指令：有可能跳到第 x 個指令，不然就會執行下一行指令。
  2. 計算指令：計算完，執行下一行指令。
  3. 跳躍指令：直接跳躍到第 x 個指令。

判斷這支程式是否有機會停止、或者是進入無限迴圈、還是一直都會結束。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
3
3
A
A
J 1
5
A
J 4
J 5
C 3
A
4
A
A
C 2
A

Sample Output

1
2
3
NEVER
ALWAYS
SOMETIMES

Solution

知道指令與指令之間的關係，不仿建造一個有向圖，判斷使否存在一個環，根據 BFS 若沒有辦法抵達終點，

  • 沒有辦法抵達終點，有環，保證程式會進入無限迴圈。
  • 有辦法抵達終點，有環，有機會停止。
  • 其他－總會停止。
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
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MAXN 1024
vector<int> g[MAXN];
char cmd[MAXN][16];
int N[MAXN], used[MAXN], instk[MAXN];
int loopflag, endflag;
void dfs(int u) {
	instk[u] = 1, used[u] = 1;
	for (int i = 0; i < g[u].size(); i++) {
		if (used[g[u][i]] == 0)
			dfs(g[u][i]);
		if (instk[g[u][i]] == 1)
			loopflag = 1;
	}
	instk[u] = 0;
}
int main() {
	int testcase, L;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &L);
		for (int i = 0; i <= L + 1; i++)
			g[i].clear();
		for (int i = 1; i <= L; i++) {
			scanf("%s", cmd[i]);
			if (cmd[i][0] == 'A') {
				g[i].push_back(i+1);
			} else if (cmd[i][0] == 'J') {
				scanf("%d", &N[i]);
				g[i].push_back(N[i]);
			} else if (cmd[i][0] == 'C') {
				scanf("%d", &N[i]);
				g[i].push_back(N[i]);
				g[i].push_back(i+1);
			}
		}
		memset(used, 0, sizeof(used));
		memset(instk, 0, sizeof(instk));
		loopflag = 0, endflag = 0;
		dfs(1);
		endflag = used[L + 1];
		if (loopflag == 0 && endflag == 1)
			puts("ALWAYS");
		else if (loopflag == 1 && endflag == 0)
			puts("NEVER");
		else
			puts("SOMETIMES");
	}
	return 0;
}
/*
3
3
A
A
J 1
5
A
J 4
J 5
C 3
A
4
A
A
C 2
A
*/
Read More +
解題區►解題區 - UVa

UVa 12803 - Arithmetic Expressions

Problem

給一個浮點數的五則運算表達式，計算其值。

Sample Input

1
2
3
4
3
( 3.00 + 4.50 )
( 5.00 - ( 2.50 * 3.00 ) )
( ( 7.00 / 3.00 ) + ( 4.00 - ( 3.00 * 7.00 ) ) )

Sample Output

1
2
3
7.50
-2.50
-14.67

Solution

中序表達轉換成後序表達，隨後再使用 stack 完成計算。

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
#include <stdio.h>
#include <stack>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
int priority_op(char c) {
    switch(c) {
        case '(':return 0;
        case '+': case '-':return 1;
        case '*': case '/':return 2;
    }
    return -1;
}
void trans(char infix[], char buffer[]) {
    int len = strlen(infix);
    char *ptr = buffer;
    stack<char> op;
    *ptr = '\0';
    for(int i = 0; i < len; i++) {
    	if (infix[i] == ' ')	continue;
        if(infix[i] >= '0' && infix[i] <= '9' || 
			(infix[i] == '-' && infix[i+1] >= '0' && infix[i+1] <= '9')) {
			while (infix[i] >= '0' && infix[i] <= '9' || 
				(infix[i] == '-' && infix[i+1] >= '0' && infix[i+1] <= '9') || infix[i] == '.') {
            	sprintf(ptr, "%c", infix[i]), i++;
            	while(*ptr)    ptr++;
        	}
        	sprintf(ptr, " ");
            while(*ptr)    ptr++;
        	i--;
        }else {
            if(infix[i] == ')') {
                while(!op.empty() && op.top() != '(') {
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                op.pop();
            } else {
                if(infix[i] != '(')
                while(!op.empty() && priority_op(op.top()) >= priority_op(infix[i])) {
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                op.push(infix[i]);
            }
        }
    }
    while(!op.empty()) {
        sprintf(ptr, "%c ", op.top()), op.pop();
        while(*ptr) ptr++;
    }
}
int isOper(char c) {
    switch(c) {
        case '(':return 1;
        case '+': case '-':return 1;
        case '*': case '/':return 1;
    }
    return 0;
}
double calcPostfix(char postfix[]) {
	stringstream sin(postfix);
	string token;
    stack<double> stk;
    double a, b, c;
    while (sin >> token) {
    	if (token.length() == 1 && isOper(token[0])) {
            b = stk.top(), stk.pop();
            a = stk.top(), stk.pop();
            switch(token[0]) {
                case '+': a = a+b;break;
                case '-': a = a-b;break;
                case '*': a = a*b;break;
                case '/': a = a/b;break;
            }
            stk.push(a);
    	} else {
    		stringstream cc(token);
    		cc >> c;
    		stk.push(c);
    	}
    }
    return stk.top();
}
char infix[262144], postfix[262144];
int main() {
	int testcase;
	scanf("%d", &testcase);
	while (getchar() != '\n');
	while (testcase--) {
		gets(infix);
		trans(infix, postfix);
		printf("%.2lf\n", calcPostfix(postfix));
	}
	return 0;
}
/*
3
( 3.00 + 4.50 )
( 5.00 - ( 2.50 * 3.00 ) )
( ( 7.00 / 3.00 ) + ( 4.00 - ( 3.00 * 7.00 ) ) )
*/
Read More +
解題區►解題區 - 其他題目

ZJOI 2012 DAY2 灾难

Problem

阿米巴是小强的好朋友。
阿米巴和小强在草原上捉蚂蚱。小强突然想，如果蚂蚱被他们捉灭绝了，那么吃蚂蚱的小鸟就会饿死，而捕食小鸟的猛禽也会跟着灭绝，从而引发一系列的生态灾难。
学过生物的阿米巴告诉小强，草原是一个极其稳定的生态系统。如果蚂蚱灭绝了，小鸟照样可以吃别的虫子，所以一个物种的灭绝并不一定会引发重大的灾难。
我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的有向图来描述生物之间的关系：
一个食物网有N个点，代表N种生物，如果生物x可以吃生物y，那么从y向x连一个有向边。
这个图没有环。
图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光合作用来生存； 而有连出边的点代表的都是消费者，它们必须通过吃其他生物来生存。
如果某个消费者的所有食物都灭绝了，它会跟着灭绝。
我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么会跟着一起灭绝的生物的种数。
举个例子：在一个草场上，生物之间的关系是：

如果小强和阿米巴把草原上所有的羊都给吓死了，那么狼会因为没有食物而灭绝，而小强和阿米巴可以通过吃牛、牛可以通过吃草来生存下去。所以，羊的灾难值是1。但是，如果草突然灭绝，那么整个草原上的5种生物都无法幸免，所以，草的灾难值是4。
给定一个食物网，你要求出每个生物的灾难值。

Input

第一行是一个正整数N，表示生物的种数。生物从1标号到N。
接下来N行，每行描述了一个生物可以吃的其他生物的列表，格式为用空格隔开的若干个数字，每个数字表示一种生物的标号，最后一个数字是0表示列表的结束。

Output

包含N行，每行一个整数，表示每个生物的灾难值。

Sample Input

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

Sample Output

1
2
3
4
5
4
1
0
0
0

Solution

解法參照網路各位大神，效率為 O(E log V)，必須為 DAG 圖。

题目大意 ：给你一个有向可拓扑图，入度为零的点成为源点，然后考虑每一个点，假若删掉了他以及对应的边，那么除他外有多少个点不可达源点。

算法 ：按拓扑序遍历N个点，将距每个点最近的必须通过的点设为它的父亲，构造出一棵树。对于每个点，若向它连边的点只有一个，其父亲就是向它连边的点；若向它连边的点不只一个，其父亲是向它连边的所有点的最近公共祖先。删掉每个点后不可达点个数就是其子树的节点个数。

這個做法接近貪婪思路，建造一個瓶頸樹，建造的過程找到最鄰近的瓶頸，而瓶頸的找法根據 LCA 完成。

  • 建造完，利用 dfs 計算子樹大小，發生 stackoverflow，系統恰好沒有抓到，改用 bfs 計算就 A 過。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <stdio.h> 
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
// http://oi.nks.edu.cn/showproblem?problem_id=2646 
#define MAXN 65536
#define LOGMAXN 17
vector<int> g[MAXN], invg[MAXN], tree[MAXN];
int indeg[MAXN] = {};
vector<int> toposort(vector<int> g[], int n) {
	vector<int> ret;
	queue<int> Q;
	int u, v;
	for (int i = 0; i <= n; i++)
		indeg[i] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < g[i].size(); j++)
			indeg[g[i][j]]++;
	}
	for (int i = 1; i <= n; i++) {
		if (indeg[i] == 0)
			Q.push(i);
	}
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		ret.push_back(u);
		for (int i = 0; i < g[u].size(); i++) {
			v = g[u][i];
			if (--indeg[v] == 0)
				Q.push(v);
		}
	}
	return ret;
}
int depth[MAXN], parent[MAXN][LOGMAXN];
int getLCA(int x, int y) {
	int dist, i;
	if (depth[x] < depth[y])	swap(x, y);
	dist = depth[x] - depth[y];
	for (int i = 0; dist; i++, dist /= 2) {
		if (dist&1)	x = parent[x][i];
	}
	for (i = 0; x != y;) {
		if (parent[x][i] != parent[y][i] || (i == 0 && parent[x][i] == parent[y][i])) {
			x = parent[x][i];
			y = parent[y][i];
			i++;
		} else {
			i--;
		}
	}
	return x;
}
void buildTree(vector<int> &topo, vector<int> g[], int n) {
	for (int i = 1; i <= n; i++)
		tree[i].clear();
	int u, v;
	parent[0][0] = -1, depth[0] = 0;
	for (int i = 0; i < topo.size(); i++) {
		u = topo[i];
		if (g[u].size() == 0) {
			depth[u] = 1, parent[u][0] = 0;
			continue;
		}
		int lca = g[u][0];
		for (int j = 0; j < g[u].size(); j++)
			v = g[u][j], lca = getLCA(lca, v);
		depth[u] = depth[lca] + 1;
		parent[u][0] = lca;
		tree[lca].push_back(u);
		for (int i = 0; parent[u][i]; i++) {
			parent[u][i+1] = parent[parent[u][i]][i];
		}
	}
}
int used[MAXN], subtree[MAXN];
void sumTree(int n) {
	queue<int> Q;
	int u, v;
	for (int i = 1; i <= n; i++) {
		subtree[i] = 1;
		indeg[i] = tree[i].size();
		if (tree[i].size() == 0)	Q.push(i);
	}
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		v = parent[u][0];
		indeg[v]--;
		subtree[v] += subtree[u];
		if (indeg[v] == 0)
			Q.push(v);
	}
}
int main() {	
	int n, x, y, u, v;
	while(scanf("%d", &n) == 1) {
		for (int i = 0; i <= n; i++)
			g[i].clear(), invg[i].clear();
		for (int i = 1; i <= n; i++) {
			while (scanf("%d", &x) == 1 && x) {
				g[i].push_back(x);
				invg[x].push_back(i);
			}
		}
		vector<int> topo = toposort(invg, n);
		buildTree(topo, g, n);
		sumTree(n);
		for (int i = 1; i <= n; i++)
			printf("%d\n", subtree[i] - 1);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 1629 - Cake slicing

Problem

切割長方形蛋糕，使得每一塊上恰好有一個莓果，每一次切割的花費即線長，求最小花費。

Sample Input

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

Sample Output

1
Case 1: 5

Solution

利用 DP 精神，考慮每一個地方都去切割，定義 dp[x][y][w][h] 為左上角座標 (x, y)，其長寬 (w, h) 的長方形蛋糕的最小花費。

沒有辦法對於連續空白之間只取一次切割，如果只切一次縱切的，切著左右兩側的橫切個數將會影響很大，所以每個位置都要嘗試。

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
#include <stdio.h> 
#include <algorithm>
#include <string.h>
using namespace std;
int N, M, K;
int g[32][32], sum[32][32];
int dp[32][32][32][32], used[32][32][32][32], testcase = 0;
int getArea(int x, int y, int w, int h) {
	return sum[x + w-1][y + h-1] - sum[x-1][y + h-1] - sum[x + w-1][y-1] + sum[x-1][y-1];
}
int dfs(int x, int y, int w, int h) {
	if (used[x][y][w][h] == testcase)
		return dp[x][y][w][h];
	if (getArea(x, y, w, h) < 2)
		return 0;
	used[x][y][w][h] = testcase;
	int &ret = dp[x][y][w][h];
	ret = 0x3f3f3f3f;
	for (int i = 1; i < w; i++) {
		if (getArea(x, y, i, h) > 0 && getArea(x+i, y, w-i, h) > 0)
			ret = min(ret, dfs(x, y, i, h) + dfs(x+i, y, w-i, h) + h);
	}
	for (int i = 1; i < h; i++) {
		if (getArea(x, y, w, i) > 0 && getArea(x, y+i, w, h-i) > 0)
			ret = min(ret, dfs(x, y, w, i) + dfs(x, y+i, w, h-i) + w);
	}
	return ret;
}
int main() {
	while (scanf("%d %d %d", &N, &M, &K) == 3) {
		memset(g, 0, sizeof(g));
		memset(sum, 0, sizeof(sum));
		int x, y;
		for (int i = 0; i < K; i++) {
			scanf("%d %d", &x, &y);
			g[x][y]++;
		}
		for (int i = 1; i <= N; i++) {
			int x = 0;
			for (int j = 1; j <= M; j++) {
				x += g[i][j];
				sum[i][j] = sum[i-1][j] + x;
			}
		}
		testcase++;
		printf("Case %d: %d\n", testcase, dfs(1, 1, N, M));
	}
	return 0;
}
Read More +
解題區►解題區 - 其他題目

建造二元搜尋樹 O(n log n)

Problem

參照 Zerojudge d526: Binary Search Tree (BST) 按照插入的順序，建造一棵二元搜尋樹，原則上很簡單，但是很容易遇到極端的偏斜情況，如果插入順序很接近已經排序過的順序，則複雜度最慘為 O(n^2)。

Sample Input

1
2
3
4
11
368 115 121 88 741 762 801 34 41 511 60
6
5 2 10 4 9 15

Sample Output

1
2
368 115 88 34 41 60 121 741 511 762 801
5 2 4 10 9 15

Solution

核心

先稍微認識一下笛卡爾樹 (一種二元樹)，每個節點為 <key, value>，只看 key 時，笛卡爾樹是一棵二元搜尋樹，而看 value 時，它是一個最大堆 (或者是最小堆)。

在建造前，先撇清一點，笛卡爾樹的深度可能到達 n，與一般平衡樹不同。

笛卡爾樹如何建造 ? 假使已經對於 key 值由小到大排序 (升排序)，那麼將點依序插入笛卡爾樹，能保證的是－由於要符合二元搜尋樹，新加入的點一定是這棵樹某個節點的右節點。知道這一點後，再往前考慮前一次插 入的點(它原本也符合再某節點的右節點)，往這個節點往上爬，直到符合最大堆(性質 node.v > new_insert.v)，這時將這個節點的右子樹移到新加入節點的左子樹 (此時符合二元搜尋樹的性質，也保有原本堆的性質)。就這麼持續入點下去。

這麼發現，往上爬的次數不超過節點個數，因為每個節點只會從右子樹換到左子樹。均攤下 O(n) (每個節點只會從右子樹推到左子樹一次，因此最多 n 次)

我們接著將 “按照順序插入的 BST” 轉換成建造笛卡爾樹，key 值依舊為輸入的元素大小，而 value 則訂為輸入順序，根據 key 值為一個二元搜尋樹，根據 value 建造一個最小堆，那麼仔細思考可以得到與原本相同的二元搜尋樹。

建造笛卡爾樹只需要花 O(n) 時間，但建造前必須根據 key 排序 O(n log n)，所以複雜度為 O(n log n)。

在這樣的方式建造有一個缺點，並不知道途中插入的情況，只會在最後得到一樣的二元搜尋樹。假使要得到途中插入的情況，考慮離線處理，將所有操作儲存起來，而二元樹的節點位置並不會更動的情況下，事先建造一個靜態樹，隨後使用一個懶標記存在與否即可。

補充

  • 如何利用這個笛卡爾樹解決最簡單的 RMQ 問題？
    對於 <key, value> = <i, A[i]> 所建造的笛卡爾樹，可以利用 LCA 的 tarjan 算法(離線作法) 在 O(n) 時間內完成。RMQ 假使查找 [l, r] 的最小值，又因為我們根據 value 建造最小堆，則根據 tarjan 的搜索順序，拜訪右子樹時(對於區間的 r 來說)，左子樹將會跟其 LCA 合併，而 LCA 的 index 肯定比左子樹來得大 (大於等於 l)，又根據最小堆保證是大於等於 l 且小於等於 r 的最小值。
  • 只有笛卡爾樹可以做到建造二元搜尋樹嗎？
    其實並不然，還可以藉由一個額外的平衡樹來完成，效率一樣在 O (n log n)，但是親自撰寫平衡樹本身就本末倒置，如果藉由 STL 提供的平衡樹，代碼量會比笛卡爾樹好寫多。具體而言使用 lower_bound 查找當前插入的元素位在哪兩個元素之間，一定符合在右子樹或者是左子樹。
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
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct Node {
    int key, value;
    int lson, rson, parent;
};
Node D[65536];
void insertCartesianTree(int index, Node D[]) {
    int p = index - 1;
    while(D[p].value > D[index].value)
        p = D[p].parent;
    D[index].lson = D[p].rson;
    D[p].rson = index;
    D[index].parent = p;
}
void dfsPrint(int node) {
    if(node == 0)    return;
    printf("%d ", D[node].key);
    dfsPrint(D[node].lson);
    dfsPrint(D[node].rson);
}
int main() {
    int N, x;
    pair<int, int> A[65536];
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 1; i <= N; i++) {
            scanf("%d", &x);
			A[i] = make_pair(x, i);
        }
        sort(A+1, A+1+N);
        D[0].value = -1;
        D[0].lson = D[0].rson = D[0].parent = 0;
        for(int i = 1; i <= N; i++) {
            D[i].lson = D[i].rson = D[i].parent = 0;
            D[i].value = A[i].second, D[i].key = A[i].first;
        }
        for(int i = 1; i <= N; i++) {
            insertCartesianTree(i, D);
        }
        dfsPrint(D[0].rson);
        puts("");
    }
    return 0;
}
Read More +
學校課程►通識課程

[通識] 文明的進程 Week 3

上週因為上課在想題目，花了一大段時間在挑戰不可能的任務，最後宣告無法在指定要求下的時間內完成。

首先，講到十五世紀到文藝復興這段時間，歐洲開始興起的禮儀運動，儘管當時的跟現代禮儀差距是巨大的，那時人們認為的禮貌到了現代說不定還會被當作詬病。

禮貌運動從何來？為什麼突然會有禮貌之分？要求別人也要有禮貌，為了看起來合適、舒服？什麼是 羞恥 、 嬌貴 ？對於沒有在自然界存有的情感，人類為什麼卻擁有？

這些都源自於 階級 的出現，為了凸顯同種之間的高低之分，階級是很重要的，以人類而言，同種之間差別不太能從外表體現，就以行為舉止來作為第一印象。為什麼一開始不說外表呢？在物質還沒有這麼豐裕之前，其實貴族和平民之間差別並不大，所以追溯歷史，一開始比較注重行為舉止，往後才在物質豐饒的社會中，開始利用光鮮亮麗的裝飾品來凸顯階層。

階級仇視，每當越強調階級之差時，人民對於仇視的怨念增強，不外乎看看我們的 PTT 鄉民們，好吧，也許不是，那島民呢？

從刀槍物質上的強大區分階級，隨後已經變成了無形的距離之差反應階級，看著那騎士精神的消散，就能明白人們不再以武力來講自己有多偉大、崇高。

「我比你高貴，但不是單純的外在，而是你那難以進化的心靈。」

現代如何區分過去？我們開始追求極簡化的結構、嚴謹的環境以及情感上所呈現的一種寧靜安穩的姿態，講著講著，有點類似難以動搖的心靈，受任何波折都不容易易怒。說來笑話，這有點 面癱 了，都要變成非生物的巨石，也許擺脫生物本能變成大自然的一部分，才是真正的高貴吧！

為什麼宗教會興盛？從現代人的眼光來看，有普及教育的出現，信不信教沒有特別的意義，但為什麼還有人信？就是看著原先那些信教的人們，看起來比較崇高、端莊，加入宗教就能與它們站在相同的地位，向宗教最高的神悔過自己的罪孽，不斷地心靈規訓，就能煥然一新？

加入咱們宗教，就能升一級哦！你就會有所不同！

把持不住的孩子們都去了，人活著就耐不住寂寞、離群，「照著人多的地方走，肯定不會有問題的！」某方面的確是這樣，這沒有什麼對錯，「我思故我在」你曾是否講過做點不同的？還是一本死嗑？

禮儀書是什麼？告訴你「 如何去做 」出這種書的人自己不去做嗎？又是哪種人出了這種書？社會階層流動時，人們有機會往上爬，才會去夢、才有動力，禮儀書正是隨著洪流而出，學習與分享，只有下階層的人們才懂得那些事。

那上面的人要怎麼穩固自己的勢力呢？把原本區分階級的方式變得更加複雜，倒不如說奇特、古怪，努力地推層出新，就是為了要防止自我的存在貶值。

聽著老師說的這些，看來我要去悔過。

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

UVa 12424 - Answering Queries on a Tree

Problem

給一棵樹

  1. 調整某一個節點上的顏色
  2. 詢問兩個點路徑上，哪一個顏色數量最多，輸出數量即可。

Sample Input

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

Sample Output

1
2
3
4
2
3
1
1

Solution

由於顏色不大於 10，可以安妥建造 10 棵線段樹，利用樹鏈剖分的概念，重邊將會取子樹最大的那一邊，其他都是輕邊，隨後保證每一個點往上爬升，最多經過 log n 個輕邊。

因此時間複雜度調整 O(log n) 詢問 O(log^2 n)。

對於樹鏈剖分找 LCA 操作，針對兩個 (x, y) 所在的 node 而言，查看哪個 node 位置高低，調整到同高進行操作，保證爬的次數最多 log n，對於每一個 node 中建造一個線段樹，因此各自 query 也要 log 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
#include <stdio.h> 
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXN 131072
int color[MAXN];
int hNext[MAXN], iNode[MAXN], aPos[MAXN];
int used[MAXN], nodesize = 0;
struct Node {
	int p, pPos, dep;
	vector<int> A;
	vector<int> seg[10];
	void init() {
		A.clear();
		p = -1, dep = 0;
	}
} nodes[262144];
struct Tree {
	vector<int> g[MAXN];
	int root;	
	void init(int n) {
		for (int i = 0; i < n; i++)
			g[i].clear();
		root = 0;
	}
	void addEdge(int x, int y) {
		g[x].push_back(y);
		g[y].push_back(x);
	}
} tree;
int getSTsize(int n) {
	int ret = 1;
	for (ret = 1; ret < n; ret <<= 1);
	return ret<<1;
}
int prepare(int u, int p) {
	int sz = 1, mx = -1, hedge = -1;
	int v, t;
	for (int i = 0; i < tree.g[u].size(); i++) {
		v = tree.g[u][i], t;
		if (v == p)	continue;
		sz += (t = prepare(v, u));
		if (mx < t)
			mx = t, hedge = v;
	}
	hNext[u] = hedge;
	return sz;
}
void buildST(Node &nd, int k, int l, int r) {
	if (l > r)	return ;
	if (l == r) {
		nd.seg[color[nd.A[l]]][k] = 1;
		return;
	}
	int mid = (l + r)/2;
	buildST(nd, k<<1, l, mid);
	buildST(nd, k<<1|1, mid+1, r);
	for (int i = 0; i < 10; i++)
		nd.seg[i][k] = nd.seg[i][k<<1] + nd.seg[i][k<<1|1];
}
void build(int u, int p) {	
	if (used[u] == 0) {
		Node &nd = nodes[++nodesize];
		nd.init();
		for (int i = u; i != -1; i = hNext[i]) {
			used[i] = 1;
			iNode[i] = nodesize, aPos[i] = nd.A.size();
			nd.A.push_back(i);
		}
		for (int i = 0; i < 10; i++)
			nd.seg[i].clear(), nd.seg[i].resize(getSTsize(nd.A.size()), 0);
		buildST(nd, 1, 0, nd.A.size() - 1);
		if (p != -1) {
			nd.p = iNode[p], nd.pPos = aPos[p];
			nd.dep = nodes[nd.p].dep + 1;
		}
	}
	int v;
	for (int i = 0; i < tree.g[u].size(); i++) {
		v = tree.g[u][i];
		if (v == p)	continue;
		build(v, u);
	}
}
int colorsum[10];
void queryST(Node &nd, int k, int l, int r, int x, int y) {
	if (x <= l && r <= y) {
		for (int i = 0; i < 10; i++)
			colorsum[i] += nd.seg[i][k];
		return ;
	}
	int mid = (l + r)/2;
	if (x <= mid)
		queryST(nd, k<<1, l, mid, x, y);
	if (mid < y)
		queryST(nd, k<<1|1, mid+1, r, x, y);
	
}
void search(int u, int v) {
	memset(colorsum, 0, sizeof(colorsum));
	int x = iNode[u], y = iNode[v];
	u = aPos[u], v = aPos[v];
	while (x != y) {
		if (nodes[x].dep < nodes[y].dep)
			swap(x, y), swap(u, v);
		assert(u <= nodes[x].A.size());
		queryST(nodes[x], 1, 0, nodes[x].A.size() - 1, 0, u);
		u = nodes[x].pPos, x = nodes[x].p;
	}
	if (u > v)	swap(u, v);
	queryST(nodes[x], 1, 0, nodes[x].A.size() - 1, u, v);
	int ret = 0;
//	for (int i = 0; i < 10; i++)
//		printf("%d ", colorsum[i]);
//	puts("");
	for (int i = 0; i < 10; i++)
		ret = max(ret, colorsum[i]);
	printf("%d\n", ret);
}
void modifyST(Node &nd, int k, int l, int r, int x, int v) {
	if (l == r) {
		for (int i = 0; i < 10; i++)
			nd.seg[i][k] = 0;
		nd.seg[v][k]++;
		return ;
	}
	int mid = (l + r)/2;
	if (x <= mid)
		modifyST(nd, k<<1, l, mid, x, v);
	else
		modifyST(nd, k<<1|1, mid+1, r, x, v);
	for (int i = 0; i < 10; i++)
		nd.seg[i][k] = nd.seg[i][k<<1] + nd.seg[i][k<<1|1];
}
void modify(int u, int color) {
	int x = iNode[u];
	modifyST(nodes[x], 1, 0, nodes[x].A.size() - 1, aPos[u], color);
}
int main() {
//	freopen("in.txt","r+t",stdin);
//    freopen("out2.txt","w+t",stdout);
	int testcase;
	int n, q, x, y;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &q);
		for (int i = 0; i < n; i++)
			scanf("%d", &color[i]), color[i]--;
		tree.init(n);
		
		for (int i = 1; i < n; i++) {
			scanf("%d %d", &x, &y);
			x--, y--;
			tree.addEdge(x, y);
		}
		
		prepare(tree.root = 0, -1);
		memset(used, 0, sizeof(used));
		nodesize = 0;
		build(tree.root = 0, -1);
		
//		for (int i = 0; i < n; i++)
//			printf("[%d] %d\n", i, hNext[i]);
		int cmd, u, v;
		for (int i = 0; i < q; i++) {
			scanf("%d %d %d", &cmd, &u, &v);
			if (cmd == 0) {
				u--, v--;
				modify(u, v);
			} else {
				u--, v--;
				search(u, v);
			}
		}
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12783 - Weak Links

Problem

是否存在 weak link，使得兩個 component 會因為 weak link 斷掉而無法連通。

Sample Input

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

Sample Output

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

Solution

找橋 bridge！利用 back edge 的深度進行判斷。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int visited[1024], depth[1024];
vector< pair<int, int> > bridge;
int findBridge(int u, int p, int dep) {
	visited[u] = 1, depth[u] = dep;
	int back = 0x3f3f3f3f;
	for(int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if(v == p)	continue;
		if(!visited[v]) {
			int b = findBridge(v, u, dep+1);
			if(b > dep)
				bridge.push_back(make_pair(u, v));
			back = min(back, b);
		} else {
			back = min(back, depth[v]);
		}
	}
	return back;
}
int main() {
	int n, m, q, x, y;
	while(scanf("%d %d", &n, &m) == 2 && n+m) {
		for(int i = 0; i < n; i++)
			g[i].clear();
		for(int i = 0; i < m; i++) {
			scanf("%d %d", &x, &y);
			g[x].push_back(y);
			g[y].push_back(x);
		}
		
		bridge.clear();
		memset(visited, 0, sizeof(visited));
		for(int i = 0; i < n; i++) {
			if(!visited[i]) {
				findBridge(i, -1, 0);
			}
		}
		for (int i = 0; i < bridge.size(); i++)
			if (bridge[i].first > bridge[i].second)
				swap(bridge[i].first, bridge[i].second);
		sort(bridge.begin(), bridge.end());
		printf("%d", bridge.size());
		for (int i = 0; i < bridge.size(); i++)
			printf(" %d %d", bridge[i].first, bridge[i].second);
		puts("");
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 12784 - Don't Care

Problem

問是否計算順序會影響結果，給一個有向圖，請問是否每一個操作都會 reduce 到同一個項目。

Sample Input

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

Sample Output

1
2
3
4
1
1
0
0

Solution

如果裡面有環肯定是不行的，因此需要偵測環是否存在。

在這之後，必須檢查是否會 reduce 到同一個項目，因此我們將每個 node reduce 的結果保存，之後取聯集，如果發現 reduce 項目超過一個則直接回傳失敗。

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
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
vector<int> g[1024];
set<int> A[1024];
int used[1024];
int instk[1024];
int dfs(int u) {
	used[u] = 1, instk[u] = 1;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (instk[v])
			return 1;
		if (!used[v]) {
			if(dfs(v))
				return 1;
			A[u].insert(A[v].begin(), A[v].end());
			if (A[u].size() > 1)
				return 1;
		}
	}
	if (g[u].size() == 0)
		A[u].insert(u);
	instk[u] = 0;
	return A[u].size() > 1;
}
int main() {
	int n, m, x, y;
	while (scanf("%d %d", &n, &m) == 2 && n) {
		for (int i = 0; i < n; i++)
			g[i].clear(), used[i] = 0, A[i].clear(), instk[i] = 0;
		int indeg[1024] = {};
		for (int i = 0; i < m; i++) {
			scanf("%d %d", &x, &y);
			g[x].push_back(y);
			indeg[y]++;
		}
		
		int err = 0;
		for (int i = 0; i < n && !err; i++) {
			if (used[i] == 0 && indeg[i] == 0)
				err |= dfs(i);
		}
		for (int i = 0; i < n; i++) // cycle
			if (used[i] == 0)
				err = 1;
		printf("%d\n", !err);
	}
	return 0;
}
/*
3 2
0 1
1 2
2 2
0 1
0 1
2 2
0 1
1 0
3 2
0 1
0 2
0 0
*/
Read More +
解題區►解題區 - Zerojudge

b317. 紅圓茵可的野望

內容 ：

紅圓茵可最近隱居在板擦山研究魔法師的夢想，傳說中的魔法－「召喚蘿莉」。
只要成功練就這個魔法，茵可就可以召喚出一堆蘿莉，然後跟一堆蘿莉一起……嘿嘿嘿…..
目前茵可已經研究出N種可能可以成功魔法陣，接下來就是要測試這些魔法陣能不能成功召喚蘿莉，因為數量實在太多了，所以他決定先測試其中K種。為了測試魔法陣，茵可需要先開一個異次元空間，並且在裡面做測試(因為召喚蘿莉是個極大的魔法，發動時可能會造成空間扭曲，不小心毀掉可茵城就不好了。)。魔法陣都是圓形的，半徑為r，發動一個魔法陣需要以魔法陣為底高度為h的圓柱體空間。而茵可只能開出長方體的異次元空間，一個異次元空間有其長、寬、高，而魔法陣只能放置在該空間的地板上(長 x 寬那一面)，所以要發動一個半徑為r，高度為h的魔法陣，茵可需要開一個長2r寬2r高h的異次元空間(體積2r x 2r x h)。現在茵可想要開一個異次元空間，而這個空間至少要能發動K個魔法陣(不必同時發動)，這個空間的體積至少是多少。

輸入說明 ：

第一行有兩個正整數 N,K(K<=N)
接下來N行每行有兩個正整數r,h代表一個魔法陣的半徑及發動需要高度(r,h<=100)

測資

  1. N<=100
  2. N<=100
  3. N<=100
  4. N<=100000
  5. N<=100000

輸出說明 ：

輸出要發動其中K個魔法陣所需最小的異次元空間的體積是多少

範例輸入 ：

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

範例輸出 ：

1
16

提示 ：

範測所需體積為 224=16

可發動第1、2、5個魔法陣

Solution

這一題有兩種做法，直接窮舉 O(100 * 100) 的針對 [r, h] 找到 [0, r] x [0, h] 的數量是否大於 K，那麼可以在線性時間內完成。

而下面的做法，算是多此一步，原本想說能不能用 O(n log n) 時間內完成，但是會缺少部分調整資訊，也就是單純排序，以掃描線的基準會漏到資訊。

如果這一題的 r, h 很大的話，窮舉還是會耗費 O(n^2 log 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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
int BIT[256];
int query(int x) {
	int ret = 0;
	for (; x; x -= x&(-x))
		ret += BIT[x];
	return ret;
}
void modify(int x, int L) {
	for (; x <= L; x += x&(-x))
		BIT[x]++;
}
int main() {
	int N, K, r, h, w;
	while (scanf("%d %d", &N, &K) == 2) {
		vector<pair<int, int> > D;
		for (int i = 0; i < N; i++) {
			scanf("%d %d", &r, &h);
			assert(r <= 100 && h <= 100 && r > 0 && h > 0);
			D.push_back(make_pair(r * 2, h));
		}
		int ret = 0x3f3f3f3f;
		sort(D.begin(), D.end());
		memset(BIT, 0, sizeof(BIT));
		for (int i = 0; i < N; i++) {
			modify(D[i].second, 255);
			for (int j = D[i].second; j <= 100; j++) {
				int q = query(j);
				w = D[i].first, h = j;
				if (q >= K)
					ret = min(ret, w*w*h);
			}
		}
		if (K == 0)	ret = 0;
		printf("%d\n", ret);
	}
	return 0;
}
Read More +