问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3373参考:
http://blog.csdn.net/logic_nut/archive/2009/10/29/4740951.aspxhttp://iaml.is-programmer.com/posts/8249.html (这个应该是SYSU的哈哈，里面有西西里)
思路:
这个题是真不会做，即使是看别人代码都看了快两天，艾...
首先要解决的问题是如何求大数的模(这里大数用字符串表示)？
我们知道对于取模运算有: (a+b)%k = ((a%k)+(b%k))%k
(ab)%k = ((a%k)(b%k))%k
对于0-9的每个数，可以将其在个、十、百、千...位时模k的结果保存到一张表中: mod_arr
这样，修改这个大数的任何一位而模k的新结果可以在O(1)时间内取得
1 char num[MAX_LEN];
2 int hash[MAX_MOD];
3 int mod_arr[MAX_LEN][10];
4 int k, len, tmp[MAX_LEN], tmp2[MAX_LEN], start_mod;
5 int head, tail;
6 struct EACH {
7 int digits[MAX_LEN];
8 int remainder;
9 int index;
10 } queue[MAX_MOD];
11
12 void
13 init()
14 {
15 int i, j;
16 len = strlen(num);
17 for(j=0; j<10; j++)
18 mod_arr[0][j] = j%k;
19 for(i=1; i<len; i++)
20 for(j=0; j<10; j++)
21 mod_arr[i][j] = (mod_arr[i-1][j]*10)%k;
22 start_mod = 0;
23 for(i=0; i<len; i++) {
24 tmp[i] = tmp2[i] = num[len-i-1]-'0';
25 start_mod += (mod_arr[i][num[len-i-1]-'0']);
26 }
27 start_mod %= k;
28 head = -1;
29 tail = 0;
30 memset(hash, 0, sizeof(hash));
31 memset(queue, 0, sizeof(queue));
32 }
第一篇参考链接里是用DFS来做的，可惜我对于其中用于记忆化搜索的remember数组始终不理解，结果TLE
更加容易理解的方案是BFS，每次扩展改变一位数字
使用BFS的问题是如何判重？参考第二篇文章(繁琐的C++语法，没认真看呵呵)，使用余数判重，其实还不是太理解
代码:
1 void
2 bfs()
3 {
4 int i, j, t, cur_rem, cur_index;
5 queue[tail].remainder = start_mod;
6 memcpy(queue[tail].digits, tmp, sizeof(int)*len);
7 queue[tail].index = len-1;
8 hash[start_mod] = 1;
9 while(head < tail) {
10 ++head;
11 cur_rem = queue[head].remainder;
12 cur_index = queue[head].index;
13 memcpy(tmp, queue[head].digits, sizeof(int)*len);
14 if(cur_rem == 0) {
15 for(i=len-1; i>=0; i--)
16 printf("%d", tmp[i]);
17 printf("\n");
18 return;
19 }
20 /* changing digits: from least (smaller than itself) */
21 for(i=cur_index; i>=0; i--) {
22 for(j=0; j<tmp2[i]; j++) {
23 if(i==len-1 && j==0)
24 continue;
25 t = cur_rem + mod_arr[i][j] - mod_arr[i][tmp2[i]] + k; /* O(1) to find the new remainder */
26 t = t % k;
27 tmp[i] = j;
28 if(!hash[t]) {
29 ++tail;
30 queue[tail].remainder = t;
31 queue[tail].index = i-1;
32 memcpy(queue[tail].digits, tmp, sizeof(int)*len);
33 hash[t] = 1;
34 }
35 }
36 tmp[i] = tmp2[i];
37 }
38 /* changing digits: to max (greater than itself) */
39 for(i=0; i<=cur_index; i++) {
40 for(j=tmp2[i]+1; j<10; j++) {
41 t = cur_rem + mod_arr[i][j] - mod_arr[i][tmp2[i]] + k;
42 t = t % k;
43 tmp[i] = j;
44 if(!hash[t]) {
45 ++tail;
46 queue[tail].remainder = t;
47 queue[tail].index = i-1;
48 memcpy(queue[tail].digits, tmp, sizeof(int)*len);
49 hash[t] = 1;
50 }
51 tmp[i] = tmp2[i];
52 }
53 }
54 }
55 }