摘要: 問題: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 }