問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1416思路:
深度優先搜索，找出所有可能的劃分，并適當減枝
這里搜索的對象是什么？
我的第一個想法受到了前幾天完成PKU 1950的啟發，對于從高到低的每一位，有兩種可能:
a. 作為解的一部分，加入總和
b. 不加入總和，而是作為向下繼續搜索時的高位
dfs(depth, cur_sum, pre)
depth: 搜索深度
cur_sum: 當前總和
pre: 保留位
經過一段時間的調試，一次AC了
存在的問題是: 對于每一種可能的解都會重復記錄兩次，例如:
輸入 376 144139
輸出 283 144 139
dfs(6, 283, 0)與dfs(6, 144, 139)都可以得到該解
之后，查看了網上的代碼，原來不用想的這么復雜
對于第k位，我們搜索從其開始的所有可能，然后遞歸，例如:
對于將被“粉碎"的12346，對于第一位'1'，可能的劃分有1, 12, 123, 1234, 12346
代碼(方法一):
1 #define MAX_LEN 7
2 int target, num;
3 int digits_count, digits[MAX_LEN];
4 int sum_count, sum, parts_count, parts[MAX_LEN];
5 int ans_count, ans[MAX_LEN];
6
7 void
8 init()
9 {
10 int i, temp, rem;
11 memset(digits, -1, sizeof(digits));
12 memset(parts, -1, sizeof(parts));
13 digits_count = sum_count = parts_count = 0;
14 sum = -1;
15 rem = num;
16 do {
17 digits[digits_count++] = rem % 10;
18 rem /= 10;
19 } while(rem!=0);
20 for(i=0; i<digits_count/2; i++) {
21 temp = digits[i];
22 digits[i] = digits[digits_count-i-1];
23 digits[digits_count-i-1] = temp;
24 }
25 }
26
27 void
28 dfs(depth, cur_sum, pre)
29 {
30 if(cur_sum+pre>target) /* pruning */
31 return;
32 //printf("dfs(%d, %d, %d)\n", depth, cur_sum, pre);
33 if(depth == digits_count) {
34 if(pre != 0) {
35 parts[parts_count++] = pre;
36 cur_sum += pre;
37 }
38 if(cur_sum == sum)
39 ++sum_count;
40 if(cur_sum > sum) {
41 sum = cur_sum;
42 sum_count = 1;
43 ans_count = parts_count;
44 memcpy(ans, parts, sizeof(int)*ans_count);
45 }
46 if(pre != 0)
47 parts[parts_count--] = -1;
48 return;
49 }
50 /* branch 1 */
51 parts[parts_count++] = digits[depth] + pre * 10;
52 dfs(depth+1, cur_sum+parts[parts_count-1], 0);
53 parts[parts_count--] = -1;
54 /* branch 2 */
55 dfs(depth+1, cur_sum, pre*10+digits[depth]);
56 }
代碼(方法二):
1 #define MAX_LEN 7
2 int target, len;
3 char num[MAX_LEN];
4 int sum_count, sum, parts_count, parts[MAX_LEN];
5 int ans_count, ans[MAX_LEN];
6
7 void
8 dfs(int depth, int cur_sum)
9 {
10 int i, value = 0;
11 if(cur_sum > target) /* pruning */
12 return;
13 if(depth == len) {
14 if(cur_sum == sum)
15 ++sum_count;
16 if(cur_sum > sum) {
17 sum = cur_sum;
18 sum_count = 1;
19 ans_count = parts_count;
20 memcpy(ans, parts, sizeof(int)*ans_count);
21 }
22 return;
23 }
24 for(i=depth; i<len; i++) {
25 value *= 10;
26 value += (num[i]-'0');
27 parts[parts_count++] = value;
28 dfs(i+1, cur_sum+value);
29 parts[parts_count--] = -1;
30 }
31 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1129思路:
好題，典型的圖著色問題
首先，對于鄰接關系，可以用二維數組來表示
具有鄰接關系的節點不能使用同一種顏色，求所需顏色的最小值
深度優先搜索，當目前使用顏色個數已經超過當前最優解時進行減枝
代碼:
1 #define MAX_NUM 29
2 #define INF 100000
3 int graph[MAX_NUM][MAX_NUM];
4 int color[MAX_NUM];
5 int num, ans;
6
7 void
8 init()
9 {
10 int i, j, len;
11 char conn[MAX_NUM];
12 memset(graph, 0, sizeof(graph));
13 memset(color, -1, sizeof(color));
14 ans = INF;
15 for(i=0; i<num; i++) {
16 scanf("%s", conn);
17 len = strlen(conn);
18 for(j=2; j<len; j++)
19 graph[i][conn[j]-'A'] = 1;
20 }
21 }
22
23 int
24 is_valid(int depth, int cindex)
25 {
26 int i;
27 for(i=0; i<depth; i++)
28 if(graph[depth][i] && color[i]==cindex)
29 return 0;
30 return 1;
31 }
32
33 void
34 dfs(int depth, int used_colors)
35 {
36 int i;
37 if(used_colors >= ans) /* pruning */
38 return;
39 if(depth == num) {
40 ans = used_colors<ans ? used_colors : ans;
41 return;
42 }
43 for(i=1; i<=used_colors; i++) {
44 if(is_valid(depth, i)) {
45 color[depth] = i;
46 dfs(depth+1, used_colors);
47 color[depth] = -1;
48 }
49 }
50 color[depth] = used_colors+1;
51 dfs(depth+1, used_colors+1);
52 color[depth] = -1;
53 }
問題:
1 #define ENDALL "ENDOFINPUT"
2 #define ENDEACH "END"
3 #define MAX_LEN 250
4 const char cipher[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
5 const char plain[] = "VWXYZABCDEFGHIJKLMNOPQRSTU";
6 char msg[MAX_LEN];
7
8 void
9 translate(char *msg)
10 {
11 int i, len=strlen(msg);
12 for(i=0; i<len; i++)
13 if(msg[i]>='A' && msg[i]<='Z')
14 msg[i] = plain[msg[i]-'A'];
15 printf("%s ", msg);
16 }
17
18 int
19 main(int argc, char **argv)
20 {
21 char temp[15];
22 while(scanf("%s", temp)!=EOF) {
23 if(strcmp(temp, ENDALL)==0)
24 break;
25 while(scanf("%s", msg) && strcmp(msg, ENDEACH)!=0)
26 translate(msg);
27 printf("\n");
28 }
29 return 0;
30 }
"gets version"
1 #define ENDALL "ENDOFINPUT"
2 #define MAX_LEN 250
3 const char cipher[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
4 const char plain[] = "VWXYZABCDEFGHIJKLMNOPQRSTU";
5 char msg[MAX_LEN];
6
7 void
8 translate(char *msg)
9 {
10 int i, len=strlen(msg);
11 for(i=0; i<len; i++)
12 if(msg[i]>='A' && msg[i]<='Z')
13 msg[i] = plain[msg[i]-'A'];
14 printf("%s\n", msg);
15 }
16
17 int
18 main(int argc, char **argv)
19 {
20 char temp[15];
21 while(gets(temp)!=EOF) {
22 if(strcmp(temp, ENDALL)==0)
23 break;
24 gets(msg);
25 translate(msg);
26 gets(temp);
27 }
28 return 0;
29 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1426思路:
典型的BFS，每次擴展都在末尾加上0或者1，例如從1開始，1->10、1->11，10->100，10->101...
根據這點，就可以寫出AC的代碼，不過這樣所需內存會比較高昂，因為保存的每個狀態都是long long，并且狀態數目非常多
參考網上代碼，發現這里可以應用鴿巢原理
對于m取模，其結果只有0, 1, ..., m-1這幾種可能，因此很可能出現重復
另外，如果擴展前remainder是k, 那么擴展之后的remainder可以通過((k*10)+0/1)%num計算得到
如何記錄結果也是比較tricky的，這里在每個狀態中只保留一位以及指向擴展前狀態的指針，輸出的時候只要遞歸即可
代碼:
1 struct EACH {
2 int remainder;
3 int digit;
4 struct EACH *pre;
5 }queue[QUEUE_MAX];
6 int hash[REMAINDER_MAX];
7 int head, tail;
8 int num;
9
10 void
11 output(struct EACH *end)
12 {
13 if(end==NULL)
14 return;
15 output(end->pre);
16 printf("%d", end->digit);
17 }
18
19 void
20 bfs()
21 {
22 int cur_rem, next_rem;
23 queue[tail].remainder = 1%num;
24 queue[tail].digit = 1;
25 queue[tail].pre = NULL;
26 hash[queue[tail].remainder] = 1;
27 while(head <= tail) {
28 ++head;
29 cur_rem = queue[head].remainder;
30 if(cur_rem == 0) {
31 output(queue+head);
32 printf("\n");
33 return;
34 }
35 next_rem = (cur_rem*10+0)%num;
36 if(!hash[next_rem]) {
37 ++tail;
38 queue[tail].remainder = next_rem;
39 queue[tail].digit = 0;
40 queue[tail].pre = queue+head;
41 hash[next_rem] = 1;
42 }
43 next_rem = (cur_rem*10+1)%num;
44 if(!hash[next_rem]) {
45 ++tail;
46 queue[tail].remainder = next_rem;
47 queue[tail].digit = 1;
48 queue[tail].pre = queue+head;
49 hash[next_rem] = 1;
50 }
51 }
52 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1321思路:
深度優先搜索
有點類似于八皇后問題，不過要注意這里k<=n，也就是說: 某些行是可以不放置棋子的
不過，該題還可以利用位運算進行優化...
代碼:
1 char chessboard[MAX_LEN][MAX_LEN];
2 int record[MAX_LEN];
3 int n, k;
4 int total;
5
6 int
7 is_valid(int i, int depth)
8 {
9 int j;
10 for(j=0; j<depth; j++)
11 if(record[j] == i)
12 return 0;
13 return 1;
14 }
15
16 void
17 dfs(int depth, int cur)
18 {
19 int i, j;
20 if(depth == n) {
21 if(cur == k)
22 ++total;
23 return;
24 }
25 if(cur+(n-depth) < k) /* pruning */
26 return;
27 for(i=0; i<n; i++) {
28 if(chessboard[depth][i]=='#' && is_valid(i, depth)) {
29 record[depth] = i;
30 dfs(depth+1, cur+1);
31 record[depth] = -1;
32 }
33 }
34 dfs(depth+1, cur);
35 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1629思路:
這題如果想通了，就是一水題呵呵，不亞于PKU 1000的'A+B Problem'
該題要求輸出在填滿words之后grid中剩余的字符，并且告訴我們一定存在解
最簡單的辦法就是對A-Z的字符進行計數，然后輸出
現在，我們將題目的要求改變一下，找出所有可能的填滿方案（更具挑戰性）
這可以通過DFS來解決，代碼如下:
通過調用solve(0)即可獲得所有的方案
這里，set(x, y, index, ct)是找出對于words[index]的所有可能填充
1 void
2 set(int x, int y, int index, int ct)
3 {
4 int i, tx, ty;
5 visited[x][y] = index+1;
6 if(ct+1 == words_len[index]) {
7 solve(index+1);
8 visited[x][y] = 0;
9 return;
10 }
11 for(i=0; i<4; i++) {
12 tx = x + dx[i];
13 ty = y + dy[i];
14 if(is_valid(tx, ty) && !visited[tx][ty] && grid[tx][ty]==words[index][ct+1])
15 set(tx, ty, index, ct+1);
16 }
17 visited[x][y] = 0;
18 }
19
20 void
21 solve(int index)
22 {
23 int i, j;
24 if(index == p) {
25 for(i=0; i<n; i++) {
26 for(j=0; j<m; j++) {
27 printf("%d\t", visited[i][j]);
28 }
29 printf("\n");
30 }
31 return;
32 }
33 char c = words[index][0];
34 for(i=0; i<n; i++) {
35 for(j=0; j<m; j++) {
36 if(grid[i][j]==c && !visited[i][j])
37 set(i, j, index, 0);
38 }
39 }
40 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3278思路:
簡單的BFS，一次AC
使用一個數組visited[MAX_NUM]來判重
代碼:
1 #define ADD(temp, cur) ++tail; \
2 queue[tail].num = temp; \
3 queue[tail].moves = cur+1; \
4 visited[temp] = 1;
5
6 int
7 bfs()
8 {
9 int cur_num, cur_moves, temp;
10 queue[tail].num = n;
11 queue[tail].moves = 0;
12 visited[queue[tail].num] = 1;
13 while(head <= tail) {
14 ++head;
15 cur_num = queue[head].num;
16 cur_moves = queue[head].moves;
17 if(cur_num == k)
18 return cur_moves;
19 temp = cur_num - 1;
20 if(temp>=0 && temp<MAX_NUM && !visited[temp]) {
21 ADD(temp, cur_moves);
22 }
23 temp = cur_num + 1;
24 if(temp>=0 && temp<MAX_NUM && !visited[temp]) {
25 ADD(temp, cur_moves);
26 }
27 temp = cur_num<<1;
28 if(temp>=0 && temp<MAX_NUM && !visited[temp]) {
29 ADD(temp, cur_moves);
30 }
31 }
32 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3256思路:
該題是一道簡單的DFS，結果卻歷經了很多次RE，甚至還TLE，艾...
首先，對于paths可以用二維數組paths[MAX_N][MAX_N]來表示，雖然是很自然的事情，不過還是體現了選擇合適的數據結構對于解題的幫助
然后，對于每個起點(pasture in which each cow is grazing from beginning)依次深度優先搜索，并計數
所有的搜索結束之后，清點計數，若某個pasture的計數等于cows的個數，那么就是符合條件的pasture
需要注意的一點是如何避免路徑中的環路，這里使用一維數組visited來標記經過的pastures
代碼:
1 void
2 init()
3 {
4 int i, j, p;
5 memset(paths, 0, sizeof(paths));
6 memset(starts, 0, sizeof(starts));
7 memset(counts, 0, sizeof(counts));
8 scanf("%d %d %d", &k, &n, &m);
9 for(i=1; i<=k; i++)
10 scanf("%d", starts+i);
11 for(i=1; i<=m; i++) {
12 scanf("%d %d", &j, &p);
13 paths[j][p] = 1;
14 }
15 }
16
17 void
18 solve(int index)
19 {
20 int i;
21 visited[index] = 1;
22 ++counts[index];
23 for(i=1; i<=n; i++)
24 if(paths[index][i] && !visited[i]) {
25 solve(i);
26 }
27 }
28
29 void
30 output()
31 {
32 int i, total=0;
33 for(i=1; i<=n; i++)
34 if(counts[i] == k)
35 ++total;
36 printf("%d\n", total);
37 }
問題:
depth: 搜索深度，即運算符的個數
cur: 目前表達式的值
pre: 前一個運算數
代碼:
1 #define MAX_N 16
2 #define MAX_SOLVE 20
3 int total;
4 int n;
5 const int arr[] = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
6 const char op[] = {'+', '-', '.'};
7 char oparr[MAX_N];
1 void
2 solve(int depth, int cur, int pre)
3 {
4 if(depth+1 == n) {
5 cur += pre;
6 if(cur == 0) {
7 ++total;
8 if(total <= MAX_SOLVE)
9 output();
10 }
11 return;
12 }
13 oparr[depth] = op[0];
14 solve(depth+1, cur+pre, arr[depth]);
15 oparr[depth] = op[1];
16 solve(depth+1, cur+pre, -arr[depth]);
17 oparr[depth] = op[2];
18 if(arr[depth]>=10)
19 pre = pre*100 + pre/abs(pre)*arr[depth];
20 else
21 pre = pre*10 + pre/abs(pre)*arr[depth];
22 solve(depth+1, cur, pre);
23 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1691思路:
首先要解決的問題是如何合理地表示整個Board?
這題還是在青島洲際無聊的時候用手機看到的，當時想到用一顆樹的父子節點來表示各個矩形之間的上下關系
其實，這是一個有向圖，而表示的方法則可以很簡單地使用二維數組(因為矩形的個數比較少)進行標記即可
另一個巧妙之處是記錄每個節點的入度，當入度為零時表示可以Painting
在用有向圖進行表示之后，剩下的就是搜索了(太菜，參考人家的)
代碼:
1 int
2 solve(int last_color, int count)
3 {
4 int i, j, rt;
5 int ans = 1000000;
6 for(i=0; i<n; i++) {
7 if(!visited[i] && degree[i]==0) {
8 visited[i] = 1;
9 if(recs[i].color != last_color)
10 ++count;
11 for(j=0; j<n; j++)
12 if(graph[i][j])
13 --degree[j];
14 rt = solve(recs[i].color, count);
15 ans = rt<ans ? rt : ans;
16 visited[i] = 0;
17 if(recs[i].color != last_color)
18 --count;
19 for(j=0; j<n; j++)
20 if(graph[i][j])
21 ++degree[j];
22 }
23 }
24 if(ans == 1000000)
25 ans = count;
26 return ans;
27 }
1 void
2 build_graph()
3 {
4 int i, j;
5 for(i=0; i<n; i++)
6 for(j=0; j<n; j++)
7 if(i!=j && is_immdt_above(recs+i, recs+j)) {
8 graph[i][j] = 1;
9 ++degree[j];
10 }
11 }
1 /* if rec1 is immediate above rec2, return 1 */
2 int
3 is_immdt_above(struct Rec *rec1, struct Rec *rec2)
4 {
5 if(rec1->lwrgt_x==rec2->uplft_x && !(rec1->lwrgt_y<=rec2->uplft_y || rec1->uplft_y>=rec2->lwrgt_y))
6 return 1;
7 return 0;
8 }