摘要: 问题:http://acm.pku.edu.cn/JudgeOnline/problem?id=1198思路:宽度优先搜索tips:1. 如何表示整个chessboard？ 最简单的方法是用二维数组，不过如果发现该chessboard是8X8的话，很自然地会想到是否可以用一个整数来表示 答案是肯定的，long long类型，不过可能unsigned ...
阅读全文
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1753思路:
首先，观察题意，可以发现对于每个piece，最多只有两种可能性: 翻转一次或者不翻转，翻转多次是没有意义的
另外，由于整个rectangular大小是4X4，因此可以使用位运算来提高性能
对于位运算，需要知道的是如何反转任意的某一位:
巧妙的异或运算 1^x = ~x 0^x = x
1. 深度优先搜索
1 #define SIZE 4
2 #define BIT_MAX 16
3 const int END_BLACK = 0;
4 const int END_WHITE = (1<<(BIT_MAX))-1;
5 int min;
6
7 int
8 flip(int init_state, int bit_num)
9 {
10 int x, y;
11 x = bit_num / SIZE;
12 y = bit_num % SIZE;
13 init_state ^= (1<<bit_num);
14 if(x == 0)
15 init_state ^= (1<<(bit_num+SIZE));
16 else if(x == 3)
17 init_state ^= (1<<(bit_num-SIZE));
18 else {
19 init_state ^= (1<<(bit_num+SIZE));
20 init_state ^= (1<<(bit_num-SIZE));
21 }
22 if(y==0)
23 init_state ^= (1<<(bit_num+1));
24 else if(y==3)
25 init_state ^= (1<<(bit_num-1));
26 else {
27 init_state ^= (1<<(bit_num+1));
28 init_state ^= (1<<(bit_num-1));
29 }
30 return init_state;
31 }
32
33 void
34 dfs(long state, int depth, int count)
35 {
36 if(state==END_BLACK || state==END_WHITE) {
37 min = count < min ? count : min;
38 return;
39 }
40 if(depth >= BIT_MAX || count >= min)
41 return;
42 dfs(state, depth+1, count);
43 dfs(flip(state, depth), depth+1, count+1);
44 }
2. 宽度优先搜索
1 #define SIZE 4
2 #define BIT_MAX 16
3 const int END_BLACK = 0;
4 const int END_WHITE = (1<<(BIT_MAX))-1;
5 /* up, down, left, right */
6 const int dx[] = {-1, 1, 0, 0};
7 const int dy[] = {0, 0, -1, 1};
8 const int idx_diff[] = {-SIZE, SIZE, -1, 1};
9 struct State {
10 long state;
11 int count; /* minimum number of rounds needed to reach 'state' */
12 };
13 struct State queue[1<<BIT_MAX];
14 int visited[1<<BIT_MAX];
15 int head, tail;
16 long state; /* the low 16 bits represents the current state */
17
18 int
19 is_valid(int x, int y)
20 {
21 return (x>=0 && x<SIZE && y>=0 && y<SIZE);
22 }
23
24 /*
25 * tricky of bit-operation
26 * 1 ^ x = ~x
27 * 0 ^ x = x
28 */
29 long
30 flip(long state, int x, int y)
31 {
32 int i, index = x*SIZE + y;
33 state ^= (1<<index);
34 for(i=0; i<4; i++) {
35 if(is_valid(x+dx[i], y+dy[i]))
36 state ^= (1<<(index+idx_diff[i]));
37 }
38 return state;
39 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1166思路:
首先，观察题意，可以看出对于每一种Move，最多只需执行4次
一共存在9种不同的Move，因此可以尝试枚举出所有的可能，这样的复杂度是: 4^9
1 #define CLK_NUM 9
2 #define MV_NUM 9
3 #define DIAL_NUM 4
4 int clocks[CLK_NUM];
5 int moves[MV_NUM][CLK_NUM] = {
6 {1, 1, 0, 1, 1, 0, 0, 0, 0}, /* move: 1 */
7 {1, 1, 1, 0, 0, 0, 0, 0, 0}, /* move: 2 */
8 {0, 1, 1, 0, 1, 1, 0, 0, 0}, /* move: 3 */
9 {1, 0, 0, 1, 0, 0, 1, 0, 0}, /* move: 4 */
10 {0, 1, 0, 1, 1, 1, 0, 1, 0}, /* move: 5 */
11 {0, 0, 1, 0, 0, 1, 0, 0, 1}, /* move: 6 */
12 {0, 0, 0, 1, 1, 0, 1, 1, 0}, /* move: 7 */
13 {0, 0, 0, 0, 0, 0, 1, 1, 1}, /* move: 8 */
14 {0, 0, 0, 0, 1, 1, 0, 1, 1} /* move: 9 */
15 };
16 int mv_cur[MV_NUM*4]; /* 4 times a circle for each move */
17 int mv_cur_num;
18 int flag;
19
20 int
21 is_ok()
22 {
23 int i;
24 for(i=0; i<CLK_NUM; i++)
25 if(clocks[i] % DIAL_NUM != 0)
26 return 0;
27 return 1;
28 }
29
30 void
31 dfs(int depth)
32 {
33 if(depth > MV_NUM || flag)
34 return;
35 int i, j, k;
36 if(is_ok()) {
37 flag = 1;
38 for(i=0; i<mv_cur_num; i++)
39 printf("%d ", mv_cur[i]+1);
40 printf("\n");
41 return;
42 }
43 for(j=0; j<4; j++) { /* each move test 4 times */
44 for(k=0; k<j; k++) {
45 for(i=0; i<CLK_NUM; i++)
46 clocks[i] += moves[depth][i];
47 mv_cur[mv_cur_num] = depth;
48 mv_cur_num += 1;
49 }
50 dfs(depth+1);
51 for(k=0; k<j; k++) {
52 for(i=0; i<CLK_NUM; i++)
53 clocks[i] -= moves[depth][i];
54 mv_cur_num -= 1;
55 }
56 }
57 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1915思路:
典型的宽度优先搜索
貌似求解最优问题的这种题目用宽度优先搜索比较合适，如果更改为深度优先搜索，那么必须求出所有的解才能得到最优解(通过递归调用树可以清晰的明白这点)
1 int
2 bfs()
3 {
4 int i, tx, ty, ttx, tty, cur;
5 ++tail;
6 queue[tail].x = start_x;
7 queue[tail].y = start_y;
8 vstd_min[start_x][start_y] = 0;
9 while(head < tail) {
10 ++head;
11 tx = queue[head].x;
12 ty = queue[head].y;
13 cur = vstd_min[tx][ty];
14 if(tx==end_x && ty==end_y)
15 return cur;
16 for(i=0; i<8; i++) {
17 ttx = tx + dxy[i][0];
18 tty = ty + dxy[i][1];
19 if(is_valid(ttx, tty) && vstd_min[ttx][tty]==0) {
20 ++tail;
21 queue[tail].x = ttx;
22 queue[tail].y = tty;
23 vstd_min[ttx][tty] = cur+1;
24 }
25 }
26 }
27 return 32767;
28 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1101思路:
宽度优先搜索
要点: 每次扩展的时候，在各个方向(上下左右)，不是简单地只扩展一格，而是“直线延伸”式的扩展
另外，由于允许路径超出board范围，所以在上下左右各多放置一栏空白
由于使用C来写，所以队列就简单地用数组模拟，一般情况下还是可行的，不过有时可能比较浪费空间，又有时可能会分配数组大小不够而出现RE
队列的每个Element是一个State结构，其中包含了点坐标及到达该点的最小segments
其实，虽然AC了，还是一直有个疑问，在找到目的点的时候，我们得到一个segments个数，而且就直接将其作为问题的解，那会不会在另外一个方向存在另一条路径到达这个目的点，而且其segments个数更小，只是该条路径在队列中尚未被访问到？这也是当初我将vstd_drt数组设置成某点是否被访问过及其被访问的方向的初衷
1 #define SIZE_MAX 77 /* 75+2 */
2 #define UP 1
3 #define DOWN 2
4 #define LEFT 4
5 #define RIGHT 8
6 char board[SIZE_MAX][SIZE_MAX];
7 int vstd_drt[SIZE_MAX][SIZE_MAX];
8 int width, height;
9 int start_x, start_y, end_x, end_y;
10 struct State {
11 int x;
12 int y;
13 int min;
14 };
15 struct State queue[SIZE_MAX*SIZE_MAX];
16 int head, tail;
17 const int dx[] = {-1, 1, 0, 0};
18 const int dy[] = {0, 0, -1, 1};
19
20 int
21 is_valid(int x, int y)
22 {
23 return (x>=0 && x<=height+1 && y>=0 && y<=width+1);
24 }
25
26 #define ADD(i, j, min, drt) ++tail; \
27 queue[tail].x = i; \
28 queue[tail].y = j; \
29 queue[tail].min = min; \
30 vstd_drt[i][j] = drt;
31
32 void
33 push_queue(int x, int y, int drt, int min)
34 {
35 int i, j;
36 switch(drt) {
37 case UP:
38 j = y;
39 for(i=x; i>=0; i--) {
40 if(board[i][j]=='X')
41 break;
42 if(!vstd_drt[i][j]) {
43 ADD(i, j, min, drt);
44 }
45 }
46 break;
47 case DOWN:
48 j = y;
49 for(i=x; i<=height+1; i++) {
50 if(board[i][j]=='X')
51 break;
52 if(!vstd_drt[i][j]) {
53 ADD(i, j, min, drt);
54 }
55 }
56 break;
57 case LEFT:
58 i = x;
59 for(j=y; j>=0; j--) {
60 if(board[i][j]=='X')
61 break;
62 if(!vstd_drt[i][j]) {
63 ADD(i, j, min, drt);
64 }
65 }
66 break;
67 case RIGHT:
68 i = x;
69 for(j=y; j<=width+1; j++) {
70 if(board[i][j]=='X')
71 break;
72 if(!vstd_drt[i][j]) {
73 ADD(i, j, min, drt);
74 }
75 }
76 break;
77 }
78 }
79
80 int
81 bfs()
82 {
83 int i, j, cur_x, cur_y, cur_min, nx, ny;
84 for(i=0; i<4; i++) {
85 nx = start_x + dx[i];
86 ny = start_y + dy[i];
87 if(is_valid(nx, ny) && board[nx][ny]==' ' && !vstd_drt[nx][ny])
88 push_queue(nx, ny, 1<<i, 1);
89 }
90 while(head<tail) {
91 ++head;
92 cur_x = queue[head].x;
93 cur_y = queue[head].y;
94 cur_min = queue[head].min;
95 if(cur_x==end_x && cur_y==end_y)
96 return cur_min;
97 for(i=0; i<4; i++) {
98 nx = cur_x + dx[i];
99 ny = cur_y + dy[i];
100 if(is_valid(nx, ny) && board[nx][ny]==' ' && !vstd_drt[nx][ny])
101 push_queue(nx, ny, 1<<i, cur_min+1);
102 }
103 }
104 return -1;
105 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1164思路:
其实这题经过分析之后就是一道深度优先搜索题，1次AC...o(∩_∩)o...哈哈
涉及到如何解析一个整数来确定方向的问题，我的解决办法如下:
1 #define WEST 1
2 #define NORTH 2
3 #define EAST 4
4 #define SOUTH 8
5 #define CAN_GO(sum, dir) (((15-(sum))&dir) != 0)
6 int dir[] = {WEST, NORTH, EAST, SOUTH};
7 int dx[] = {0, -1, 0, 1};
8 int dy[] = {-1, 0, 1, 0};
具体代码(与PKU 1562类似):
1 void
2 solve()
3 {
4 int i, j, temp;
5 for(i=0; i<row; i++)
6 for(j=0; j<col; j++)
7 if(!visited[i][j]) {
8 total += 1;
9 temp = dfs(i, j);
10 largest = temp > largest ? temp : largest;
11 }
12 }
13
14 int
15 dfs(int i, int j)
16 {
17 int k, sum, rooms = 1;
18 visited[i][j] = 1;
19 sum = castle[i][j];
20 for(k=0; k<4; k++) {
21 if(CAN_GO(sum, dir[k]) && is_valid(i+dx[k], j+dy[k]) && !visited[i+dx[k]][j+dy[k]]) {
22 rooms += dfs(i+dx[k], j+dy[k]); /* 注意这里如何求解room个数 */
23 }
24 }
25 return rooms;
26 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1562思路:
简单的深度优先搜索，类似求连通域
1 void
2 dfs(int x, int y)
3 {
4 int i, sx, sy;
5 visited[x][y] = 1;
6 for(i=0; i<8; i++) {
7 sx = x+dx[i];
8 sy = y+dy[i];
9 if(within(sx, sy) && !visited[sx][sy] && map[sx][sy]=='@')
10 dfs(sx, sy);
11 }
12 }
13
14 void
15 solve()
16 {
17 int i, j;
18 for(i=0; i<m; i++)
19 for(j=0; j<n; j++)
20 if(map[i][j] == '@' && !visited[i][j]) {
21 dfs(i, j);
22 count+=1;
23 }
24 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3253思路:
哈夫曼树（详见CLRS）
这题设计的很巧妙
理解的关键是: 将切割木板的过程反过来观察，也就是将所有最终的短木板进行拼接的过程，这其实就是哈夫曼树的构造过程
CLRS上关于哈夫曼树的构造是以优先级队列为基础的
由于倾向于用C来写，所以并没有使用C++的STL（当然，这要简单的多）
别忘了: 目的并不是要简单，而是要锻炼自己的算法及数据结构基础
以最小堆为基础的优先级队列实现:
1 #define PARENT(i) ((i-1)>>1)
2 #define LEFT_CLD(i) ((i<<1)+1)
3 #define RIGHT_CLD(i) ((i+1)<<1)
4 #define SWAP(a, b) a=a+b; b=a-b; a=a-b /* tricky */
5 int heap_size;
6
7 void
8 min_heapify(long long *heap, int i)
9 {
10 int min = i;
11 int left = LEFT_CLD(i);
12 int right = RIGHT_CLD(i);
13 if(left<heap_size && heap[min]>heap[left])
14 min = left;
15 if(right<heap_size && heap[min]>heap[right])
16 min = right;
17 if(min != i) {
18 SWAP(heap[i], heap[min]);
19 min_heapify(heap, min);
20 }
21 }
22
23 void
24 build_min_heap(long long *heap, int length)
25 {
26 int i;
27 heap_size = length;
28 for(i=(heap_size>>1)-1; i>=0; i--)
29 min_heapify(heap, i);
30 }
31
32 long long
33 extract_min(long long *heap)
34 {
35 if(heap_size < 1) {
36 fprintf(stderr, "heap underflow\n");
37 exit(1);
38 }
39 long long rt = heap[0];
40 SWAP(heap[0], heap[heap_size-1]);
41 --heap_size;
42 min_heapify(heap, 0);
43 return rt;
44 }
45
46 void
47 decrease_key(long long *heap, int i, long long new_key)
48 {
49 int c, p;
50 if(heap[i] < new_key) {
51 fprintf(stderr, "new key is larger than current key\n");
52 exit(1);
53 }
54 heap[i] = new_key;
55 c = i;
56 p = PARENT(i);
57 while(c>0 && heap[p]>heap[c]) {
58 SWAP(heap[c], heap[p]);
59 c = p;
60 p = PARENT(c);
61 }
62 }
63
64 void
65 insert(long long *heap, long long value)
66 {
67 ++heap_size;
68 heap[heap_size-1] = MAX_INT;
69 decrease_key(heap, heap_size-1, value);
70 }
哈夫曼树的构造(这里是简化版，根据题意只需要计算cost即可):
1 long long
2 huffman_tree_way(long long *heap, int length)
3 {
4 int i;
5 long long fst, snd, sum, rt=0;
6 build_min_heap(heap, length);
7 for(i=0; i<length-1; i++) {
8 fst = extract_min(heap);
9 snd = extract_min(heap);
10 sum = fst + snd;
11 rt += sum;
12 insert(heap, sum);
13 }
14 return rt;
15 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2388思路:
1. 排序
这题直接用快排就能AC，很水...
2. 求解第i个顺序统计量(详见CLRS)
利用快速排序过程中的思路，期望时间复杂度是O(n)
ps: partition函数的执行过程是比较有意思的呵呵
1 int
2 partition(long *arr, int begin, int end)
3 {
4 int i, j;
5 i = begin;
6 long pivot = arr[begin];
7 for(j=begin+1; j<=end; j++)
8 if(arr[j] <= pivot)
9 swap(arr, ++i, j);
10 swap(arr, i, begin);
11 return i;
12 }
13
14 long
15 find_ith_os(long *arr, int begin, int end, int ith)
16 {
17 if(begin == end)
18 return arr[begin];
19 int p = partition(arr, begin, end);
20 int k = p-begin+1;
21 if(k == ith)
22 return arr[p];
23 else if(ith < k)
24 return find_ith_os(arr, begin, p-1, ith);
25 else
26 return find_ith_os(arr, p+1, end, ith-k);
27 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1007http://acm.pku.edu.cn/JudgeOnline/problem?id=2299思路:
求逆序对的个数
这两题的基本问题是一致的，给定一个数组(包括字符串)，求出逆序对的个数
1. 最简单的方法
两层循环，复杂度O(n^2)
1 int
2 inversion_cal(char *str)
3 {
4 int i, j, count = 0;
5 int len = strlen(str);
6 for(i=0; i<len; i++)
7 for(j=i+1; j<len; j++)
8 if(str[i] > str[j])
9 ++count;
10 return count;
11 }
2.
归并排序＆分治思想其实，只要将归并排序稍加修改，就是一个求解逆序对个数问题的O(nlgn)方法
要理解的是这其中涉及的分治思想(三步骤):
a. 分解为子问题
b. 求解子问题
c. 合并子问题的解来得到原问题的解
具体对应到求逆序对个数的问题:
a. 将原数组分解为前后两个子数组
b. 求解子数组的逆序对个数
c. 合并前后子数组，同时计算逆序对个数(这个是指逆序对的第一个数在前子数组中，而第二个数在后子数组中)
1 long long
2 merge_count(long *arr, long *temp, long begin, long end)
3 {
4 if(begin >= end)
5 return 0;
6 long i, j, k, mid = (begin+end)/2;
7 long long rt = 0;
8 rt += merge_count(arr, temp, begin, mid);
9 rt += merge_count(arr, temp, mid+1, end);
10 i = k = begin;
11 j = mid+1;
12 while(i<=mid && j<=end) {
13 if(arr[i] <= arr[j])
14 temp[k++] = arr[i++];
15 else {
16 temp[k++] = arr[j++];
17 rt += (mid-i+1);
18 }
19 }
20 for( ; i<=mid; i++)
21 temp[k++] = arr[i];
22 for( ; j<=end; j++) {
23 temp[k++] = arr[j];
24 rt += (mid-i+1);
25 }
26 /* copy */
27 for(k=begin; k<=end; k++)
28 arr[k] = temp[k];
29 return rt;
30 }
3. 特例方法
针对PKU 1007该题的特殊性: 字符串中只包含A, G, T, C四个字母，还有一种更加简单的O(n)方法
1 int
2 inversion_cal2(char *str)
3 {
4 int i, temp[4], count = 0;
5 int len = strlen(str);
6 memset(temp, 0, sizeof(temp));
7 for(i=len-1; i>=0; i--) {
8 switch(str[i]) {
9 case 'A':
10 ++temp[0];
11 break;
12 case 'C':
13 ++temp[1];
14 count += temp[0];
15 break;
16 case 'G':
17 ++temp[2];
18 count += (temp[0]+temp[1]);
19 break;
20 case 'T':
21 ++temp[3];
22 count += (temp[0]+temp[1]+temp[2]);
23 break;
24 }
25 }
26 return count;
27 }