Posts Tagged ‘算法艺术与信息学竞赛’

POJ 2942 Knights of the Round Table

Posted in PKU OJ on 四月 16th, 2010 by 纳米 – Be the first to comment

2010-04-15，阅读、分析题目，学习算法，编码实现
2010-04-16，改写部分，调试，AC

好了，如果没有看了下题解，这题我是没啥思路的。

因为之前做了POJ 3177那题，然后也知道这题是双连通分量的，就直接往边双连通分量的方向想。想了半天随手画了个图出来才发现是错的，不是边双连通分量，而是点双连通分量。详细如下：

1. 构造数据给定图的补图，这才是我们所需要的，点代表骑士，边代表两个骑士愿意坐在一起。下面所有的算法都基于此图。

2. 求出图中所有的点双连通分量。对于求图中的双连通分量，还是参考byvoid牛的：图的割点、桥与双连通分支。其中，byvoid牛写到“每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中”。在我的实现中，由于只需要知道每个双连通分量的点集，所以只记录了树枝边。

还有，请无视黑书（《算法艺术与信息学竞赛》）P287上的解释，私以为那段纯属乱来。那里完全没有分开点双连通和边双连通来讨论，定义是“没有割顶的无向图又称作2-双连通分支，亦称作块”，好了，这里勉强还没有问题。后面又写：“把每个块收缩成一个点”，经过我若干时间的思考，发现边双连通分量是可以收缩的，但是点双连通分量是不可随便收缩的，因为，一个点可以同时属于两个块（点双连通分量），那么，这个点应该收缩到哪里呢？下面那句“它的边就是桥”也是有问题的，理由同上（亏他还加着重号）。这段话如果要重写，我也不知道该怎么写了，因为要多写出很多东西来，大概这样吧：：“无向图的子图中：没有割顶的子图称作点双连通分量，亦称作块。没有桥的子图称作边双连通分量，把每个边双连通分量收缩成一个点，就得到一棵树，它的边就是桥。”这样就没什么问题了。

3. 对每个双连通分量，判断是否存在奇圈（即圈上的点数为奇数）。首先给出两个定理：(1) 若某块存在奇圈，那么该块中的所有点都处于奇圈中；(2) 若某块不可染色为二分图，则该块存在奇圈。(1)是说明该步骤的正确性的，(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

#include <stdio.h>
#include <string.h>
 
const int maxn = 1005;
int n, m, edge[maxn][maxn], et[maxn], deep[maxn], low[maxn];
int stack[maxn][2], stack_last, bcc[maxn], bcc_n, color[maxn], color_n, answer;
bool ee[maxn][maxn], vis[maxn], point[maxn];
 
bool input() {
	scanf("%d%d", &n, &m);
	memset(et, 0, sizeof(et));
	memset(ee, 0, sizeof(ee));
	for (int i = 1, u, v; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		ee[u][v] = ee[v][u] = 1;
	}
	for (int u = 1; u <= n; ++u)
		for (int v = 1; v <= n; ++v)
			if (u != v && !ee[u][v])
				edge[u][et[u]++] = v;
	return n || m;
}
 
bool fill_color(int u) {
	int new_color = (color_n << 1) + 1 - color[u];
	for (int i = 0, v = edge[u][0]; i < et[u]; v = edge[u][++i])
		if (bcc[v] == bcc_n) {
			if (color[v] < color_n) {
				color[v] = new_color;
				if (fill_color(v))
					return true;
			} else if (color[v] != new_color) {
				return true;
			}
		}
	return false;
}
 
int calc_bcc(int s, int t) {
	int last0 = stack_last++;
	++bcc_n;
	do {
		--stack_last;
		bcc[stack[stack_last][0]] = bcc[stack[stack_last][1]] = bcc_n;
	} while (stack_last > 1 && (stack[stack_last][0] != s || stack[stack_last][1] != t));
	color[s] = (color_n += 2);
	if (fill_color(s)) {
		for (int i = stack_last; i <= last0; ++i)
			point[stack[i][0]] = point[stack[i][1]] = 1;
	}
	--stack_last;
	return 0;
}
 
int dfs(int u, int father, int d) {
	int tot = 0;
	vis[u] = 1;
	deep[u] = low[u] = d;
	for (int i = 0, v = edge[u][0]; i < et[u]; v = edge[u][++i]) {
		if (!vis[v]) {
			stack[++stack_last][0] = u;
			stack[stack_last][1] = v;
			dfs(v, u, d + 1);
			++tot;
			low[u] = low[u] < low[v] ? low[u] : low[v];
			if (u == 1 || deep[u] <= low[v])
				calc_bcc(u, v);
		} else if (v != father) {
			low[u] = low[u] < deep[v] ? low[u] : deep[v];
		}
	}
	return 0;
}
 
int work() {
	memset(vis, 0, sizeof(vis));
	memset(bcc, 0, sizeof(bcc));
	memset(color, 0, sizeof(color));
	memset(point, 0, sizeof(point));
	bcc_n = color_n = stack_last = 0;
	for (int v = 1; v <= n; ++v)
		if (!vis[v])
			dfs(v, 0, 1);
	int res = 0;
	for (int v = 1; v <= n; ++v)
		res += !point[v] ? 1 : 0;
	return res;
}
 
int main() {
	while (input())
		 printf("%d\n", work());
	return 0;
}

POJ 2482 Stars in Your Window

Posted in PKU OJ on 四月 12th, 2010 by 纳米 – Be the first to comment

2010-04-12，阅读、分析题目（话说我只看完了Here comes the problem那一段-.-）
2010-04-12，实现代码，WA，AC

解题报告：
这道题挺有意思的，不过也没啥好说，因为《算法艺术和信息学竞赛》P102-104上有较为详细的解释。我补充三点：
(1) 针对这道题，由于矩形边上的点不能取，所以我们直接对w h减1；
(2) 实现的时候，不必写平衡树，写个静态的二叉树好了（其实是不是多数的题目都可以这样搞个静态的二叉查找树呢？如果是的话就方便很多了）。不过注意，排序的第一关键字是纵坐标，升序；第二关键字是亮度，降序，因为要确保取到最大值；
(3) 2^31-1+1,000,000会爆int，所以使用unsigned。

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 <stdlib.h>
 
const int maxn = 20003;
int n, tree_last;
unsigned w, h, data[maxn][4], tree[maxn][4];
 
bool input() {
	if (scanf("%d%u%u", &n, &w, &h) == EOF)
		return false;
	for (int i = 1; i <= n; ++i) {
		scanf("%u%u%u", &data[(i<<1)-1][0], &data[(i<<1)-1][1], &data[(i<<1)-1][2]);
		data[i<<1][0] = data[(i<<1)-1][0];
		data[i<<1][1] = data[(i<<1)-1][1] + h;
		data[i<<1][2] = -data[(i<<1)-1][2];
	}
	n <<= 1;
	--w, --h;
	return true;
}
 
int comp_x(unsigned x[], unsigned y[]) {
	return x[0]!=y[0] ? (x[0]<y[0]?-1:1) : (x[1]==y[1]?0:(x[1]<y[1]?-1:1));
}
 
int comp_y(unsigned x[], unsigned y[]) {
	return x[1]!=y[1] ? (x[1]<y[1]?-1:1) : (x[2]==y[2]?0:(x[2]>y[2]?-1:1));
}
 
int build_tree(int t) {
	int left = t << 1;
	int right = left + 1;
	if (left <= n)
		build_tree(left);
	data[++tree_last][3] = t;
	tree[t][0] = data[tree_last][2];
	tree[t][1] = tree[t][2] = 0;
	tree[t][3] = 0;
	if (right <= n)
		build_tree(right);
	return 0;
}
 
int max(int x, int y) {
	return x > y ? x : y;
}
 
void tree_update(int t) {
	int left = t << 1, right = (t << 1) + 1;
	left = left > n ? 0 : left;
	right = right > n ? 0 : right;
	tree[t][2] = tree[t][1] + tree[left][2] + tree[right][2];
	tree[t][3] = max(tree[left][3], tree[t][2] - tree[right][2]);
	tree[t][3] = max(tree[t][3], tree[t][2] - tree[right][2] + tree[right][3]);
	if (t > 1)
		tree_update(t >> 1);
}
 
void tree_insert(int w) {
	tree[w][1] = tree[w][0];
	tree_update(w);
}
 
void tree_delete(int w) {
	tree[w][1] = 0;
	tree_update(w);
}
 
int work() {
	qsort(data[1], n, sizeof(int) * 4, (int(*) (const void*, const void*)) comp_y);
	tree_last = 0;
	build_tree(1);
	tree[0][0] = tree[0][1] = tree[0][2] = tree[0][3] = 0;
	qsort(data[1], n, sizeof(int) * 4, (int(*) (const void*, const void*)) comp_x);
	int res = 0, line1 = 0, line2 = 0;
	while (line2 < n) {
		do {
			tree_insert(data[++line2][3]);
		} while (data[line2][0] == data[line2+1][0]);
		while (data[line2][0] - data[line1+1][0] > w) {
			tree_delete(data[++line1][3]);
		}
		res = max(res, tree[1][3]);
	}
	return res;
}
 
int main() {
	while (input())
		printf("%d\n", work());
	return 0;
}

ZOJ 2561 Order-Preserving Codes

Posted in ZJU OJ on 四月 8th, 2010 by 纳米 – Be the first to comment

20??-??-??，阅读题目
2010-04-07，从JBY处问到这题的题解，原来是他那年的集训队作业（NOI08 – IOI09国家集训队）-.-
2010-04-08，发现和我当时的想法和做法一样，好了，我还是太没信心了，为啥不继续调试下去呢-.- 参考JBY的代码，一次AC。

解题报告：
参考《算法艺术与信息学竞赛》P151-152，感觉上此题和那题是类似的，方程也是类似的，可以利用四边形不等式进行优化。
设f(i, j)为第i – j位的最小值，sum(i, j)为第i – j位的和，有：
(1) i=j: f(i, j) = sum(i, i)
(2) i<j: f(i, j) = min{f(i, k) + f(k+1, j) | i <= k < j} + sum(i, j)
这样做的时间复杂度为O(n^3)，根据四边形不等式，迅速降为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

#include <stdio.h>
 
const int maxn = 2003;
int n, data[maxn], o[maxn][maxn];
long long sum[maxn], dp[maxn][maxn];
 
bool input() {
	if (scanf("%d", &n) == EOF)
		return false;
	for (int i = 1; i <= n; ++i)
		scanf("%d", &data[i]);
	return true;
}
 
int work() {
	sum[0] = 0;
	for (int i = 1; i <= n; ++i) {
		dp[i][i] = data[i];
		o[i][i] = i;
		sum[i] = sum[i-1] + (long long) data[i];
	}
	for (int l = 2; l <= n; ++l)
		for (int i = 1, j = l; j <= n; ++i, ++j) {
			int left = i > o[i][j-1] ? i : o[i][j-1], right = j-1 < o[i+1][j] ? j-1 : o[i+1][j];
			dp[i][j] = 0xFFFFFFFFFFFFFFFll;
			for (int k = left; k <= right; ++k)
				if (dp[i][k] + dp[k+1][j] < dp[i][j]) {
					dp[i][j] = dp[i][k] + dp[k+1][j];
					o[i][j] = k;
				}
			dp[i][j] += sum[j] - sum[i-1];
		}
	return 0;
}
 
void output(int x, int l, int r) {
	if (l >= r)
		return;
	if (x <= o[l][r]) {
		printf("0");
		output(x, l, o[l][r]);
	} else {
		printf("1");
		output(x, o[l][r]+1, r);
	}
}
 
int output() {
	for (int i = 1; i <= n; ++i) {
		output(i, 1, n);
		printf("\n");
	}
	return 0;
}
 
int main() {
	while (input()) {
		work();
		output();
	}
	return 0;
}

POJ 1141 Brackets Sequence

Posted in PKU OJ on 四月 8th, 2010 by 纳米 – Be the first to comment

2010-10-31，AC

解题报告：参考《算法艺术与信息学竞赛》P113
不过要输出那个合法序列感觉十分麻烦，那些字符串处理啊~

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

#include <stdio.h>
#include <string.h>
 
const int maxn = 103;
int n, dp[maxn][maxn] = {0};
char data[maxn], dp_arr[maxn][maxn][203] = {0}, answer[203];
 
int input() {
	char ch = 0;
	while (scanf("%c", &ch) > 0)
		if (ch == '(' || ch == ')' || ch == '[' || ch == ']')
			data[++n] = ch;
	return 0;
}
 
int work() {
	for (int i = 1; i <= n; ++i) {
		dp[i][i] = 1;
		if (data[i] == '(' || data[i] == ')') {
			dp_arr[i][i][0] = '(';
			dp_arr[i][i][1] = ')';
		} else {
			dp_arr[i][i][0] = '[';
			dp_arr[i][i][1] = ']';
		}
	}
	for (int p = 1; p < n; ++p)
		for (int i = 1; i + p <= n; ++i) {
			int j = i + p;
			int min = 0x7FFFFFFF, min_k;
			if (data[i] == '(' && data[j] == ')' || data[i] == '[' && data[j] == ']') {
				min = dp[i+1][j-1];
				min_k = -1;
			}
			for (int k = i; k < j; ++k)
				if (dp[i][k] + dp[k+1][j] < min) {
					min = dp[i][k] + dp[k+1][j];
					min_k = k;
				}
			dp[i][j] = min;
			if (min_k < 0) {
				dp_arr[i][j][0] = data[i];
				memcpy(&dp_arr[i][j][1], dp_arr[i+1][j-1], strlen(dp_arr[i+1][j-1]));
				dp_arr[i][j][strlen(dp_arr[i][j])] = data[j];
			} else {
				memcpy(dp_arr[i][j], dp_arr[i][min_k], strlen(dp_arr[i][min_k]));
				memcpy(&dp_arr[i][j][strlen(dp_arr[i][min_k])], dp_arr[min_k+1][j], strlen(dp_arr[min_k+1][j]));
			}
			//printf("%d %d: %d : %s\n", i, j, dp[i][j], dp_arr[i][j]);
		}
	memcpy(answer, dp_arr[1][n], sizeof(answer));
	return 0;
}
 
int output() {
	printf("%s\n", answer);
	return 0;
}
 
int main() {
	input();
	work();
	output();
	return 0;
}