问题:
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 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1298思路:
简单题，不需要任何"算法"
这里之所以记录的原因是，我用scanf进行输入，虽然AC，不过比较繁琐(scanf会因为读到空白符而结束，与题意不符)
网上看到"史上最精髓的gets"呵呵，不禁赞叹...
代码:
"scanf version"
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 }
问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1950思路:
首先想到的方法是枚举所有的可能，然后依次计算每个表达式的值，看看是否等于零
想法简单，然而碰到的问题是如何计算表达式？汗...还真不会，是不是得用堆栈的呵呵
看了网上的代码，原来还可以一边深度搜索一边计算表达式值的，技巧在于如何处理"."这个"运算符"
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 }