Posts Tagged ‘位运算’

POJ 1084 Square Destroyer

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

2010-04-09，阅读题目，分析题目
2010-04-11，代码实现，发现理解错题意；重新写，一次AC，282ms；下午加一可行性剪枝，16ms

解题报告：
此问题可以转化为一个图论的问题，把火柴看作另A类结点，正方形看作B类结点。如果某根火柴在某个正方形的边上，那么我们就往这相应的两个结点添加一条边。这样，问题转化为求该图中，最少用多少A类结点可以覆盖所有的B类结点。当n=5时，A类结点数为：2n(n+1)=60；B类结点数为：n(n+1)(2n+1)/6=55。
可以见得，B类结点可以直接通过一个64位整型类储存。利用位运算，可以大大加快搜索速度。做法具体如下：
(1) 若有边(i, j)（分别属于A、B类结点，下同），则Aij = 0；否则Aij = 1；
(2) 对于每个确定的i，将Aij二进制编码至Bi中；
(3) 除去数据中没有的Bi，并编码初始状态st；
(4) 对于Bi按照可覆盖点数排序（优化1）；
(5) 若i<j，且Bi和Bj效果是一致的，则删掉Bj（优化2）；
(6) 计算opt[i] = Bi & B(i+1) & B(i+2) … & Bn（可行性剪枝）。
搜索过程，按照一般的方法做即可，添加最优性剪枝：若当前值大于阶段最剪枝，则跳出；添加可行性剪枝，若取剩余所有的Bi也无法达到目标，则剪枝。

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

#include <stdio.h>
#include <stdlib.h>
 
const int maxn = 65, INF[] = {0, 1, 3, 6, 9, 12};
int es, n, m, answer;
long long edge[maxn], opt[maxn], st;
bool ev[maxn];
 
int input() {
	int k, t;
	scanf("%d%d", &es, &k);
	n = (es * es + es) << 1;
	for (int i = 1; i <= n; ++i)
		ev[i] = 1;
	for (int i = 1; i <= k; ++i) {
		scanf("%d", &t);
		ev[t] = 0;
	}
	return 0;
}
 
int build_graph() {
	long long nt = 1;
	m = es*(es+1)*(2*es+1)/6;
	for (int i = 1; i <= n; ++i)
		edge[i] = (1 << m) - 1;
	for (int l = 1; l <= es; ++l)
		for (int x0 = 1, x1 = l; x1 <= es; ++x0, ++x1)
			for (int y0 = 1, y1 = l; y1 <= es; ++y0, ++y1) {
				int w0 = (es+es+1)*(x0-1) + y0;
				int w1 = (es+es+1)*x1 + y0;
				for (int i = 1; i <= l; ++i) {
					edge[w0] -= nt;
					edge[w1] -= nt;
					++w0, ++w1;
				}
				w0 = es*x0 + (es+1)*(x0-1) + y0;
				w1 = w0 + l;
				for (int i = 1; i <= l; ++i) {
					edge[w0] -= nt;
					edge[w1] -= nt;
					w0 += es+es+1;
					w1 += es+es+1;
				}
				nt <<= 1;
			}
	int j = 0;
	st = (1 << m) - 1;
	for (int i = 1; i <= n; ++i)
		if (ev[i]) {
			edge[++j] = edge[i];
		} else {
			st &= edge[i];
		}
	n = j;
	return 0;
}
 
int count(long long x) {
	x = (x & 0x5555555555555555ll) + (x>> 1 & 0x5555555555555555ll);
	x = (x & 0x3333333333333333ll) + (x>> 2 & 0x3333333333333333ll);
	x = (x & 0x0F0F0F0F0F0F0F0Fll) + (x>> 4 & 0x0F0F0F0F0F0F0F0Fll);
	x = (x & 0x00FF00FF00FF00FFll) + (x>> 8 & 0x00FF00FF00FF00FFll);
	x = (x & 0x0000FFFF0000FFFFll) + (x>>16 & 0x0000FFFF0000FFFFll);
	x = (x & 0x00000000FFFFFFFFll) + (x>>32 & 0x00000000FFFFFFFFll);
	return x;
}
 
int dfs(int k, long long st, int sum) {
	if (!st) {
		answer = sum-1 < answer ? sum-1 : sum-1;
	} else if (k <= n && sum < answer && !(st & opt[k])) {
		if ((st & edge[k]) != st)
			dfs(k+1, st & edge[k], sum + 1);
		dfs(k+1, st, sum);
	}
	return 0;
}
 
int comp(long long *x, long long *y) {
	return count(*x) - count(*y);
}
 
int work() {
	answer = INF[es];
	qsort(&edge[1], n, sizeof(long long), (int(*) (const void*, const void*)) comp);
	for (int i = 1; i < n; ++i) {
		int k = i;
		for (int j = i + 1; j <= n; ++j)
			if ((st & edge[i]) != (st & edge[j]))
				edge[++k] = edge[j];
		n = k;
	}
	opt[n] = edge[n];
	for (int i = n - 1; i > 0; --i)
		opt[i] = opt[i+1] & edge[i];
	dfs(1, st, 1);
	return 0;
}
 
int output() {
	printf("%d\n", answer);
	return 0;
}
 
int main() {
	int testCases;
	scanf("%d", &testCases);
	while (testCases--) {
		input();
		build_graph();
		work();
		output();
	}
	return 0;
}

POJ 2286 The Rotation Game

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

2010-04-08，阅读题目
2010-04-09，分析题目，实现，一次AC

解题报告：
这题可以采用广度优先搜索解决，关键问题是如何设计状态。
假设中间8个格子的数字已经确定，那么，其余两种数字在这种情况下是等价的。那么，我们把已经确定下来的中间的数字全部置为1，其余均值为0，那么就可以压缩为一个大小范围为0 – 2^24-1的状态。同时，我们可以知道，真正的状态总数为C(8, 24) = 24! / (8! * 16!) = 735471。这样的状态总数完全是可以接受的。
只要中间的数字不能确定，BFS就变得很容易了。但是问题是现在中间的数字并不确定，那么我们只需要枚举中间的数字，分别求出最优值，然后便可求出答案。
但是这样做的效率是低下的，因为，很有可能我按照顺序1、2、3进行广搜，假定中间数字为1、2的时候每次都扩展出70万种状态，而3只需要扩展出100种状态便可到达，显然浪费了很多时间。有一个简单的解决方案，就是在状态的前面增加两位二进制数字，00、01、02分别表示这个状态中间为1、2、3，那么，问题就很好解决了。
我的程序花了58MB内存和2000ms时间。

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

#include <stdio.h>
#include <string.h>
 
const int TARGET = 0x399C0;
const int RE[] = {
	0x3AF77BA, 0x35DEEF5, 0x3FFF80F, 0x3F01FFF, 0x35DEEF5, 0x3AF77BA, 0x3F01FFF, 0x3FFF80F
};
const int RR[][7] = {
	{0,2,6,11,15,20,22},
	{1,3,8,12,17,21,23},
	{4,5,6,7,8,9,10},
	{13,14,15,16,17,18,19},
	{1,3,8,12,17,21,23},
	{0,2,6,11,15,20,22},
	{13,14,15,16,17,18,19},
	{4,5,6,7,8,9,10}
};
const int RL[][7] = {
	{22,0,2,6,11,15,20},
	{23,1,3,8,12,17,21},
	{5,6,7,8,9,10,4},
	{14,15,16,17,18,19,13},
	{3,8,12,17,21,23,1},
	{2,6,11,15,20,22,0},
	{19,13,14,15,16,17,18},
	{10,4,5,6,7,8,9}
};
 
int data[24], statu, q[735473 * 3], pre[735473 * 3], answer_int, answer_step;
short step[735473 * 3];
char o[735473 * 3], answer[1001], ans[1001];
char vis[16777216 * 3] = {0};
 
bool input() {
	scanf("%d", &data[0]);
	if (!data[0])
		return false;
	for (int i = 1; i < 24; ++i)
		scanf("%d", &data[i]);
	return true;
}
 
int operate(int k, int A) {
	int res = A & RE[k];
	for (int i = 0; i < 7; ++i)
		res |= (A >> RR[k][i] & 1) << RL[k][i];
	return res;
}
 
int work_bfs(int arr[]) {
	int head = 0, last = 3;
	for (int i = 1; i <= 3; ++i) {
		q[i] = arr[i];
		o[i] = 0;
		step[i] = 0;
		vis[arr[i]] = statu;
	}
	while (head < last) {
		int A = q[++head];
		int step0 = step[head] + 1;
		if (step0 > answer_step)
			break;
		for (int k = 0; k < 8; ++k) {
			int B = operate(k, A);
			if (vis[B] < statu) {
				if ((B & TARGET) == TARGET)
					answer_step = step0;
				q[++last] = B;
				o[last] = k;
				pre[last] = head;
				step[last] = step0;
				vis[B] = statu;
			}
		}
	}
	return last;
}
 
int work() {
	++statu;
	int arr[4] = {0};
	for (int i = 1; i <= 3; ++i) {
		for (int j = 23; j >= 0; --j)
			arr[i] = (arr[i] << 1) | (data[j] == i ? 1 : 0);
		if ((arr[i] & TARGET) == TARGET) {
			strcpy(answer, "No moves needed");
			answer_int = i;
			return 0;
		}
		arr[i] += (i - 1) * 16777216;
	}
	answer_step = 1000;
	int last = work_bfs(arr);
 
	for (int i = 0; i < 1000; ++i)
		answer[i] = 'Z';
	answer[1000] = '\0';
	for (int i = 1; i <= last; ++i) {
		if ((q[i] & TARGET) == TARGET) {
			int st = i, len = 0;
			while (st > 3) {
				ans[answer_step - ++len] = o[st] + 'A';
				st = pre[st];
			}
			ans[len] = '\0';
			if (strcmp(ans, answer) < 0) {
				strcpy(answer, ans);
				answer_int = q[i] / 16777216 + 1;
			}
		}
	}
	return 0;
}
 
int output() {
	printf("%s\n", answer);
	printf("%d\n", answer_int);
	return 0;
}
 
int main() {
	statu = 0;
	while (input()) {
		work();
		output();
	}
	return 0;
}

POJ 1112 Team Them Up!

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

2009-12-03，AC

解题报告：
这题是当时体育课的时候走来走去想到的，发现真神奇我居然能想到这么神奇的东西。
进行简单的考虑，假设有A、B、C三人，A不认识B，B不认识C，那么A必然需要认识C，否则就需要3个小组了，但是题中只有2个小组。然后，可以知道，A和C一定要在同一个分组，AC和B一定不能在同一个分组。
所以，我们把所有的人按照不认识的关系构图，进行染色，判断每一个连通块能否形成二分图。不能形成二分图的，直接判无解。可以形成二分图的，由于A类结点和B类结点必须在不同的分组，所以可以简化处理：对于第i个连通块，统计A类结点的个数Ai和B类结点的个数Bi。然后进行动态规划，直接根据Ai和Bi进行计算即可。
设状态f(i, x, y)，表示在前i个连通块中，可以组成一个小组x人、另一个小组y人。有方程：f(i, x, y) = f(i-1, x-Ai, y-Bi) or f(i-1, x-Bi, y-Ai)。由于对称性，以及y可以根据i, y计算得出，可以简化为f(i, x) = f(i-1, x-Ai) or f(i-1, x-Bi)。
最后根据染色关系等等进行统计，即可得出答案。
顺便，利用位运算进行了一点小小的优化。

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

#include <stdio.h>
#include <string.h>
 
const int pow[] = {0,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912
};
const int powW[] = {0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6
};
 
const int maxn = 103;
int n, color[maxn] = {0}, color_n, color_x, size[maxn << 1] = {0}, dpways[maxn][7] = {0}, answer_c;
bool edge[maxn][maxn] = {0}, dp[2][maxn] = {0}, answer_ok, answer[maxn];
 
int input() {
	scanf("%d", &n);
	int v;
	for (int u = 0; u < n; ++u)
		while (1) {
			scanf("%d", &v);
			if (!v)
				break;
			edge[u][v - 1] = 1;
		}
	for (int u = 0; u < n; ++u) {
		for (int v = 0; v < u; ++v)
			edge[u][v] = edge[v][u] = edge[u][v] && edge[v][u];
		edge[u][u] = 1;
	}
	return 0;
}
 
bool dye(int u) {
	int cx = color_x - color[u];
	for (int v = 0; v < n; ++v)
		if (!edge[u][v]) {
			if (color[v] == 0) {
				color[v] = cx;
				++size[cx];
				if (!dye(v))
					return false;
			} else if (color[v] != cx)
				return false;
		}
	return true;
}
 
bool work_dye() {
	color_n = 0;
	for (int i = 0; i < n; ++i)
		if (!color[i]) {
			color[i] = ++color_n;
			size[color_n] = 1;
			color_x = color_n + color_n + 1;
			if (!dye(i))
				return false;
			++color_n;
		}
	return true;
}
 
int work() {
	if (answer_ok = work_dye()) {
		dp[0][0] = true;
		int now = 0, pre = 1;
		for (int i = 1; i <= color_n; i += 2) {
			now = 1 - now;
			pre = 1 - pre;
			memset(dp[now], 0, sizeof(dp[now]));
			for (int j = n; j >= 0; --j)
				if (j - size[i] >= 0 && dp[pre][j - size[i]]) {
					dp[now][j] = true;
					memcpy(dpways[j], dpways[j - size[i]], sizeof(dpways[j]));
					dpways[j][powW[i]] |= pow[i];
				} else if (j - size[i+1] >= 0 && dp[pre][j - size[i+1]]) {
					dp[now][j] = true;
					memcpy(dpways[j], dpways[j - size[i+1]], sizeof(dpways[j]));
					dpways[j][powW[i+1]] |= pow[i+1];
				}
		}
		int arr[7];
		for (int i = n >> 1; i <= n; ++i)
			if (dp[now][i]) {
				memcpy(arr, dpways[i], sizeof(arr));
				break;
			} else if (n-i > 0 && dp[now][n-i]) {
				memcpy(arr, dpways[n-i], sizeof(arr));
				break;
			}
		answer_c = 0;
		for (int i = 0; i < n; ++i) {
			answer[i] = arr[powW[color[i]]] & pow[color[i]];
			answer_c += answer[i] ? 1 : 0;
		}
	}
	return 0;
}
 
int output() {
	if (answer_ok) {
		printf("%d", answer_c);
		for (int i = 0; i < n; ++i)
			if (answer[i])
				printf(" %d", i + 1);
		printf("\n%d", n - answer_c);
		for (int i = 0; i < n; ++i)
			if (!answer[i])
				printf(" %d", i + 1);
		printf("\n");
	} else
		printf("No solution\n");
	return 0;
}
 
int main() {
	input();
	work();
	output();
	return 0;
}

POJ 2411 Mondriaan’s Dream

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

2009-12-02，AC

解题报告：
这是一道状态压缩DP。首先对每一行设计状态，对于某个位置，有空和非空两种情况。什么情况下进行状态转移呢?
(1) (x, y)为空，(x-1, y)不为空，表示该(x, y)为一个竖着的方块的上面一格；
(2) (x, y)不为空，(x-1, y)为空，表示该(x, y)为一个竖着的方块的下面一格；
(3) (x, y)、(x-1, y)均不为空，并且一行中有一段连续的、数量为偶数的这样的格子，表示这一段连续的格子为横着的方块。
我们用0表示空，1表示非空，每行不超过11个格子，于是我们可以进行二进制编码。为了提高速度，可以预先处理某个状态A可以从哪些状态转移而来。
还有一个优化，就是h*w为奇数答案显然为0。

当然，可以打表-.-

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

#include <stdio.h>
#include <string.h>
 
const int pow[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
const int maxn = 11, maxpow = 2049;
 
int n, m;
int match[maxpow][maxpow], size[maxpow] = {0};
long long dp[2][maxpow];
 
bool check1(int x, int y) {
	int c = 0;
	for (int i = 0; i < m; ++i) {
		if (!(x & 1) && !(y & 1))
			return false;
		if (x & 1 ^ y & 1 && c & 1)
			return false;
		if (x & 1 && y & 1)
			++c;
		x >>= 1;
		y >>= 1;
	}
	if (c & 1)
		return false;
	else
		return true;
}
 
bool check2(int x) {
	int c = 0;
	while (x > 0) {
		if (x & 1)
			++c;
		else if (c & 1)
			return false;
		x >>= 1;
	}
	return !(c & 1);
}
 
int init() {
	memset(size, 0, sizeof(size));
	for (int i = 0; i < pow[m]; ++i)
		for (int j = 0; j < pow[m]; ++j)
			if (check1(i, j))
				match[i][size[i]++] = j;
	return 0;
}
 
long long work() {
	int pm = pow[m];
	memset(dp[1], 0, sizeof(dp[1]));
	for (int i = 0; i < pm; ++i)
		if (check2(i))
			dp[1][i] = 1;
	for (int i = 2; i <= n; ++i) {
		int now = i & 1;
		int pre = 1 - now;
		memset(dp[now], 0, sizeof(dp[now]));
		for (int j = 0; j < pm; ++j)
			for (int k = 0; k < size[j]; ++k)
				dp[now][j] += dp[pre][match[j][k]];
	}
	int now = n & 1;
	int pre = 1 - now, pm1 = pm - 1;
	dp[now][pm1] = 0;
	for (int k = 0; k < size[pm1]; ++k)
		dp[now][pm1] += dp[pre][match[pm1][k]];
	return dp[n & 1][pm - 1];
}
 
int main() {
	while (1) {
		scanf("%d%d", &n, &m);
		if (n == 0 || m == 0)
			break;
		if (n * m & 1) {
			printf("0\n");
		} else {
			if (n < m) {
				int t = n;
				n = m;
				m = t;
			}
			init();
			printf("%I64d\n", work());
		}
	}
	return 0;
}