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