我們經(jīng)常使用的數(shù)的進(jìn)制為“常數(shù)進(jìn)制”，即始終逢p進(jìn)1。例如，p進(jìn)制數(shù)K可表示為
K = a0*p^0 + a1*p^1 + a2*p^2 + ... + an*p^n （其中0 <= ai <= p-1），
它可以表示任何一個自然數(shù)。
對于這種常數(shù)進(jìn)制表示法，以及各種進(jìn)制之間的轉(zhuǎn)換大家應(yīng)該是很熟悉的了，但大家可能很少聽說變進(jìn)制數(shù)。這里我要介紹一種特殊的變進(jìn)制數(shù)，它能夠被用來實現(xiàn)全排列的Hash函數(shù)，并且該Hash函數(shù)能夠?qū)崿F(xiàn)完美的防碰撞和空間利用（不會發(fā)生碰撞，且所有空間被完全使用，不多不少）。這種全排列Hash函數(shù)也被稱為全排列數(shù)化技術(shù)。下面，我們就來看看這種變進(jìn)制數(shù)。
我們考查這樣一種變進(jìn)制數(shù)：第1位逢2進(jìn)1，第2位逢3進(jìn)1，……，第n位逢n+1進(jìn)1。它的表示形式為
K = a1*1! + a2*2! + a3*3! + ... + an*n! （其中0 <= ai <= i），
也可以擴(kuò)展為如下形式（因為按定義a0始終為0），以與p進(jìn)制表示相對應(yīng)：
K = a0*0! + a1*1! + a2*2! + a3*3! + ... + an*n! （其中0 <= ai <= i）。
（后面的變進(jìn)制數(shù)均指這種變進(jìn)制數(shù)，且采用前一種表示法）
先讓我們來考查一下該變進(jìn)制數(shù)的進(jìn)位是否正確。假設(shè)變進(jìn)制數(shù)K的第i位ai為i+1，需要進(jìn)位，而ai*i!=(i+1)*i!=1*(i+1)!，即正確的向高位進(jìn)1。這說明該變進(jìn)制數(shù)能夠正確進(jìn)位，從而是一種合法的計數(shù)方式。
接下來我們考查n位變進(jìn)制數(shù)K的性質(zhì)：
（1）當(dāng)所有位ai均為i時，此時K有最大值
MAX[K] = 1*1! + 2*2! + 3*3! + ... + n*n!
= 1! + 1*1! + 2*2! + 3*3! + ... + n*n! - 1
= (1+1)*1! + 2*2! + 3*3! + ... + n*n! - 1
= 2! + 2*2! + 3*3! + ... + n*n! - 1
= ...
= (n+1)!-1
因此，n位K進(jìn)制數(shù)的最大值為(n+1)!-1。
（2）當(dāng)所有位ai均為0時，此時K有最小值0。
因此，n位變進(jìn)制數(shù)能夠表示0到(n+1)!-1的范圍內(nèi)的所有自然數(shù)，共(n+1)!個。
在一些狀態(tài)空間搜索算法中，我們需要快速判斷某個狀態(tài)是否已經(jīng)出現(xiàn)，此時常常使用Hash函數(shù)來實現(xiàn)。其中，有一類特殊的狀態(tài)空間，它們是由全排列產(chǎn)生的，比如N數(shù)碼問題。對于n個元素的全排列，共產(chǎn)生n!個不同的排列或狀態(tài)。下面將討論如何使用這里的變進(jìn)制數(shù)來實現(xiàn)一個針對全排列的Hash函數(shù)。
從數(shù)的角度來看，全排列和變進(jìn)制數(shù)都用到了階乘。如果我們能夠用0到n!-1這n!個連續(xù)的變進(jìn)制數(shù)來表示n個元素的所有排列，那么就能夠把全排列完全地數(shù)化，建立起全排列和自然數(shù)之間一一對應(yīng)的關(guān)系，也就實現(xiàn)了一個完美的Hash函數(shù)。那么，我們的想法能否實現(xiàn)呢？答案是肯定的，下面將進(jìn)行討論。
假設(shè)我們有b0,b1,b2,b3,...,bn共n+1個不同的元素，并假設(shè)各元素之間有一種次序關(guān)系 b0<b1<b2<...<bn。對它們進(jìn)行全排列，共產(chǎn)生(n+1)!種不同的排列。對于產(chǎn)生的任一排列 c0,c1,c2,..,cn，其中第i個元素ci（1 <= i <= n）與它前面的i個元素構(gòu)成的逆序?qū)Φ膫€數(shù)為di（0 <= di <= i），那么我們得到一個逆序數(shù)序列d1,d2,...,dn（0 <= di <= i）。這不就是前面的n位變進(jìn)制數(shù)的各個位么？于是，我們用n位變進(jìn)制數(shù)M來表示該排列：
M = d1*1! + d2*2! + ... + dn*n!
因此，每個排列都可以按這種方式表示成一個n位變進(jìn)制數(shù)。下面，我們來考查n位變進(jìn)制數(shù)能否與n+1個元素的全排列建立起一一對應(yīng)的關(guān)系。
由于n位變進(jìn)制數(shù)能表示(n+1)!個不同的數(shù)，而n+1個元素的全排列剛好有(n+1)!個不同的排列，且每一個排列都已經(jīng)能表示成一個n位變進(jìn)制數(shù)。如果我們能夠證明任意兩個不同的排列產(chǎn)生兩個不同的變進(jìn)制數(shù)，那么我們就可以得出結(jié)論：
★ 定理1 n+1個元素的全排列的每一個排列對應(yīng)著一個不同的n位變進(jìn)制數(shù)。
對于全排列的任意兩個不同的排列p0,p1,p2,...,pn（排列P）和q0,q1,q2,...,qn（排列Q），從后往前查找第一個不相同的元素，分別記為pi和qi（0 < i <= n）。
（1）如果qi > pi，那么,
如果在排列Q中qi之前的元素x與qi構(gòu)成逆序?qū)Γ从衳 > qi，則在排列P中pi之前也有相同元素x > pi（因為x > qi且qi > pi），即在排列P中pi之前的元素x也與pi構(gòu)成逆序?qū)Γ詐i的逆序數(shù)大于等于qi的逆序數(shù)。又qi與pi在排列P中構(gòu)成pi的逆序?qū)Γ詐i的逆序數(shù)大于qi的逆序數(shù)。
（2）同理，如果pi > qi，那么qi的逆序數(shù)大于pi的逆序數(shù)。
因此，由（1）和（2）知，排列P和排列Q對應(yīng)的變進(jìn)制數(shù)至少有第i位不相同，即全排列的任意兩個不同的排列具有不同的變進(jìn)制數(shù)。至此，定理1得證。
計算n個元素的一個排列的變進(jìn)制數(shù)的算法大致如下（時間復(fù)雜度為O(n^2)）：
template <typename T>
size_t PermutationToNumber(const T permutation[], int n)
{
// n不能太大，否則會溢出（如果size_t為32位，則n <= 12）
size_t result = 0;
for (int j = 1; j < n; ++j) {
int count = 0;
for (int k = 0; k < j; ++k) {
if (permutation[k] > permutation[j])
++count;
}
// factorials[j]保存著j!
result += count * factorials[j];
}
return result;
}
說明：
（1）由于n!是一個很大的數(shù)，因此一般只能用于較小的n。
（2）有了計算排列的變進(jìn)制數(shù)的算法，我們就可以使用一個大小為n!的數(shù)組來保存每一個排列的狀態(tài)，使用排列的變進(jìn)制數(shù)作為數(shù)組下標(biāo)，從而實現(xiàn)狀態(tài)的快速檢索。如果只是標(biāo)記狀態(tài)是否出現(xiàn)，則可以用一位來標(biāo)記狀態(tài)。
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1775思路:
簡單題，可以打表，可以DFS，還可以動規(guī)
代碼(dfs):
1 /* Note: 10! = 3628800 */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 10
6 int facs[MAX_LEN];
7 int mark, n;
8
9 void
10 init()
11 {
12 int i, f = 1;
13 facs[0] = 1;
14 for(i=1; i<MAX_LEN; i++) {
15 facs[i] = f*i;
16 f = facs[i];
17 }
18 }
19
20 void
21 dfs(int depth, int sum)
22 {
23 if(sum == n) {
24 mark = 1;
25 return;
26 }
27 if(depth>=MAX_LEN || mark)
28 return;
29 dfs(depth+1, sum+facs[depth]);
30 dfs(depth+1, sum);
31 }
32
33 int
34 main(int argc, char **argv)
35 {
36 init();
37 while(scanf("%d", &n)!=EOF && n>=0) {
38 mark = 0;
39 if(n > 0)
40 dfs(0, 0);
41 printf("%s\n", mark?"YES":"NO");
42 }
43 }
代碼(table, from
http://blog.chinaunix.net/u3/105033/showart_2199237.html):
1 #include<iostream>
2 using namespace std;
3 bool b[1000001];
4 int sum=0;
5 int a[10]={1,1,2,6,24,120,720,5040,40320,362880};
6 void calculate(int n)
7 {
8 if(n>=10)
9 return ;
10 sum+=a[n];
11 b[sum]=true;
12 calculate(n+1);
13 sum-=a[n];
14 calculate(n+1);
15 }
16 int main()
17 {
18 memset(b,0,sizeof(b[0]));
19 calculate(0);
20 b[0]=false;
21 int n;
22 cin>>n;
23 while( n>=0)
24 {
25 if(b[n])
26 cout<<"YES"<<endl;
27 else
28 cout<<"NO"<<endl;
29 cin>>n;
30 }
31 return 0;
32 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2248思路:
第一個想法是BFS，不過習(xí)慣性地看discuss，發(fā)現(xiàn)大家用的都是DFS，于是還是用DFS+減枝
這道題目的關(guān)鍵減枝是: num[depth+1] = num[depth]+num[i], 0<=i<=depth，另外就是從大到小的搜索順序
另一種解法是迭代加深搜索，第一次使用，貌似就是用DFS實現(xiàn)BFS，不過空間需求與時間需求是兩者的折衷，其模板類似于:
1 for(deep=1; 1; deep++)
2
3 {
4
5 dfs(0);
6
7 If(find = true)
8
9 break;
10
11 }
代碼1:
1 #define MAX_LEN 101
2 #define INF 0x7FFFFFFF
3 int num[MAX_LEN];
4 int ans[MAX_LEN];
5 int n, min;
6
7 int
8 dfs(int depth)
9 {
10 int i, j;
11 if(depth+1 >= min)
12 return;
13 if(num[depth] == n) {
14 min = depth+1;
15 memcpy(ans, num, min*sizeof(int));
16 return;
17 }
18 for(i=depth; i>=0; i--)
19 if(num[i]+num[depth]<=n) {
20 num[depth+1] = num[i] + num[depth];
21 dfs(depth+1);
22 }
23 }
24
25 int
26 main(int argc, char **argv)
27 {
28 int i;
29 while(scanf("%d", &n)!=EOF && n!=0) {
30 min = INF;
31 num[0] = 1;
32 dfs(0);
33 for(i=0; i<min; i++)
34 printf("%d ", ans[i]);
35 printf("\n");
36 }
37 return 0;
38 }
代碼2:
1 #define MAX_LEN 101
2 int num[MAX_LEN];
3 int n, find, dplimit;
4
5 void
6 dfs(int depth)
7 {
8 int i, j;
9 if(depth >= dplimit)
10 return;
11 if(num[depth] == n) {
12 if(!find) {
13 for(j=0; j<=depth; j++)
14 printf("%d ", num[j]);
15 printf("\n");
16 find = 1;
17 }
18 return;
19 }
20 for(i=depth; i>=0; i--)
21 if(num[i]+num[depth]<=n) {
22 num[depth+1] = num[i] + num[depth];
23 dfs(depth+1);
24 }
25 }
26
27 int
28 main(int argc, char **argv)
29 {
30 while(scanf("%d", &n)!=EOF && n!=0) {
31 find = 0;
32 num[0] = 1;
33 for(dplimit=1; 1; dplimit++) {
34 dfs(0);
35 if(find)
36 break;
37 }
38 }
39 }
摘要: 問題:http://acm.pku.edu.cn/JudgeOnline/problem?id=1475思路:很復(fù)雜的一題，從discuss知道可以采用嵌套的BFS來做，不過始終不知道如何下手通過這題，發(fā)現(xiàn)自己對于復(fù)雜問題的coding能力比較弱，不能很好的理清其中的邏輯關(guān)系，需要多多鍛煉這題的關(guān)鍵是抓住box的每一次擴(kuò)展，都對應(yīng)地存在一個person的起始位置，兩者需要同時記錄參考:http:/...
閱讀全文
才儲©分析：您的性格類型傾向是“ ISFJ ”(內(nèi)向 實感 情感 判斷)
沉靜，友善，有責(zé)任感和謹(jǐn)慎。能堅定不移地承擔(dān)責(zé)任。做事貫徹始終、不辭勞苦和準(zhǔn)確無誤。忠誠，替人著想，細(xì)心；往往記著他所重視的人的種種微小事情，關(guān)心別人的感受。努力創(chuàng)造一個有秩序、和諧的工作和家居 環(huán)境。 ISFJ型的人忠誠、有奉獻(xiàn)精神和同情心，理解別人的感受。他們意志清醒而有責(zé)任心，樂于為人所需。 ISFJ型的人十分務(wù)實，他們喜歡平和謙遜的人。他們喜歡利用大量的事實情況，對于細(xì)節(jié)則有很強(qiáng)的記力。他們耐心地 對待任務(wù)的整個階段，喜歡事情能夠清晰明確。 ISFJ型的人具有強(qiáng)烈的職業(yè)道德，所以他們?nèi)绻雷约旱男袨檎嬲杏脮r，會對需要完成之事承擔(dān)責(zé)任。他們準(zhǔn)確系統(tǒng)地完成任務(wù)。他們具有傳統(tǒng)的價值觀，十分保守。他 們利用符合實際的判斷標(biāo)準(zhǔn)做決定，通過出色的注重實際的態(tài)度增加了穩(wěn)定性。 ISFJ型的人平和謙虛、勤奮嚴(yán)肅。他們溫和、圓通，支持朋友和同伴。他們樂于協(xié)助別人，喜歡實際可行地幫助他人。他們利用個人熱情與人 交往，在困難中與他人和睦相處。ISFJ型的人不喜歡表達(dá)個人情感，但實際上對于大多數(shù)的情況和事件都具有強(qiáng)烈的個人反應(yīng)。他們關(guān)心、保護(hù)朋友，愿意為朋友獻(xiàn)身，他們有為他人服務(wù)的意識，愿意完成他們的責(zé)任和義務(wù)。 您適合的領(lǐng)域有：領(lǐng)域特征不明顯，較相關(guān)的如：醫(yī)護(hù)領(lǐng)域、消費類商業(yè)、服務(wù)業(yè)領(lǐng)域 您適合的職業(yè)有：（該類型可能存在的盲點見完整分析報告） · 內(nèi)科醫(yī)生
· 營養(yǎng)師
· 圖書/檔案管理員
· 室內(nèi)裝潢設(shè)計師
· 顧客服務(wù)代表
· 記賬員
· 特殊教育教師
· 酒店管理
· 人事管理人員
· 電腦操作員
· 信貸顧問
· 零售業(yè)主
· 房地產(chǎn)代理或經(jīng)紀(jì)人
· 藝術(shù)人員
· 商品規(guī)劃師
· 語言病理學(xué)者
· 審計師
· 會計
· 財務(wù)經(jīng)理
· 辦公室行政管理
· 后勤和供應(yīng)管理
· 中層經(jīng)理
· 公務(wù)（法律、稅務(wù)）執(zhí)行人員
· 銀行信貸員
· 成本估價師
· 保險精算師
· 稅務(wù)經(jīng)紀(jì)人
· 稅務(wù)檢查員
· 機(jī)械、電氣工程師
· 計算機(jī)程序員
· 數(shù)據(jù)庫管理員
· 地質(zhì)
· 氣象學(xué)家
· 法律研究者
· 律師
· 外科醫(yī)生
· 藥劑師
· 實驗室技術(shù)人員
· 牙科醫(yī)生
· 醫(yī)學(xué)研究員
from: http://www.apesk.com/mbti/dati.asp |
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3411思路:
做過幾道類似的題，DFS
不過，這一道有點特殊，每條邊以及每個點的訪問次數(shù)并非只有一次，為了能夠預(yù)付款，需要重復(fù)訪問某個點或者邊
這樣出現(xiàn)的一個問題就是搜索何時結(jié)束？這里參考了網(wǎng)上的代碼: 重復(fù)訪問的原因是為了能夠預(yù)先到達(dá)某個城市，而城市的總個數(shù)為N，也就是說，每個點的重復(fù)訪問次數(shù)不需要超過N
另外，由于每兩個點之間可能存在多條路徑，因此不能使用鄰接矩陣，而需要鄰接表
代碼
1 int N, m;
2 int min;
3 int mark[MAX_LEN];
4 struct Node {
5 int dest;
6 int adv;
7 int p, r;
8 struct Node *next;
9 };
10 struct Node *roads[MAX_LEN];
11 struct Node save[MAX_LEN];
12
13 void
14 init()
15 {
16 int i, a, b, c, p, r, cnt = 0;
17 min = INF;
18 memset(mark, 0, sizeof(mark));
19 memset(roads, 0, sizeof(roads));
20 for(i=0; i<m; i++) {
21 scanf("%d %d %d %d %d", &a, &b, &c, &p, &r);
22 save[cnt].dest = b;
23 save[cnt].adv = c;
24 save[cnt].p = p;
25 save[cnt].r = r;
26 save[cnt].next = roads[a];
27 roads[a] = save+cnt;
28 ++cnt;
29 }
30 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1190思路:
DFS+減枝，好題
代碼:
1 /*
2 * N = R[1]^2*H[1] + R[2]^2*H[2] + 
+ R[M]^2*H[M]
3 * S = R[1]^2 + 2R[1]*H[1] + 2R[2]*H[2] + + 2R[M]H[M]
4 */
5 #include<stdio.h>
6 #include<stdlib.h>
7 #include<string.h>
8 #include<math.h>
9 #define MAX_LEVEL 21
10 #define INF 0x7FFFFFFF
11 /* from top level to the i[th] level, the minimum total volumn and area */
12 int min_volumn[MAX_LEVEL], min_area[MAX_LEVEL];
13 int n, m;
14 int rt;
15
16 void
17 init()
18 {
19 int i;
20 rt = INF;
21 min_volumn[0] = min_area[0] = 0;
22 for(i=1; i<MAX_LEVEL; i++) {
23 min_volumn[i] = min_volumn[i-1] + i*i*i;
24 min_area[i] = min_area[i-1] + 2*i*i;
25 }
26 }
27
28 /* from bottom(m[th] level) to the top */
29 void
30 dfs(int level, int last_r, int last_h, int cur_volumn, int cur_area)
31 {
32 int r, h, tmp, v, a;
33 if(cur_volumn+min_volumn[level]>n || cur_area+min_area[level]>=rt)
34 return;
35 /* ADD this pruning according the volumn&area formula */
36 if(2*(n-cur_volumn)/last_r+cur_area >= rt)
37 return;
38 if(level==0) {
39 if(cur_volumn == n)
40 rt = cur_area<rt ? cur_area : rt;
41 return;
42 }
43 /* the minimal r in [level] would be level */
44 for(r=last_r-1; r>=level; r--) {
45 tmp = (int)((n-cur_volumn-min_volumn[level-1])/(double)(r*r));
46 tmp = tmp>(last_h-1) ? (last_h-1) : tmp;
47 for(h=tmp; h>=level; h--) {
48 v = r*r*h;
49 a = 2*r*h;
50 if(level == m)
51 a += (r*r);
52 dfs(level-1, r, h, cur_volumn+v, cur_area+a);
53 }
54 }
55 }
56
57 int
58 main(int argc, char **argv)
59 {
60 int max_m_r, max_m_h;
61 while(scanf("%d %d", &n, &m) != EOF) {
62 init();
63 max_m_r = (int)(sqrt((n-min_volumn[m-1])/(double)m)) + 1;
64 max_m_h = (int)((n-min_volumn[m-1])/(double)(m*m)) + 1;
65 dfs(m, max_m_r, max_m_h, 0, 0);
66 if(rt == INF)
67 printf("0\n");
68 else
69 printf("%d\n", rt);
70 }
71 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1724思路:
有點與PKU 3256類似的題
第一個想法就是深搜
第一遍代碼(WA):
對于discuss里的測試數(shù)據(jù)該代碼是沒有問題的，可結(jié)果還是WA...
1 #define MAX_CITIES 101
2 #define INF 100000
3 int road[MAX_CITIES][MAX_CITIES];
4 int length[MAX_CITIES][MAX_CITIES];
5 int toll[MAX_CITIES][MAX_CITIES];
6 int visited[MAX_CITIES];
7 int k, n, r;
8 int min_len;
9
10 void
11 dfs(int city, int cur_len, int cur_toll)
12 {
14 int i;
15 visited[city] = 1;
16 if(cur_len>=min_len || cur_toll>k) {
17 visited[city] = 0;
18 return;
19 }
20 if(city == n) {
21 min_len = cur_len;
22 visited[city] = 0;
23 return;
24 }
25 for(i=1; i<=n; i++) {
26 if(road[city][i] && !visited[i])
27 dfs(i, cur_len+length[city][i], cur_toll+toll[city][i]);
28 }
29 visited[city] = 0;
30 }
繼續(xù)翻查discuss里，發(fā)現(xiàn)有人說兩點之間可能有多條路徑...
然后看到其他人代碼是使用鏈表來保存所有的路徑，所以修改后的AC代碼如下:
1 #define MAX_CITIES 101
2 #define INF 100000
3 struct Node {
4 int dest;
5 int len;
6 int toll;
7 struct Node *next;
8 };
9 struct Node roads[MAX_CITIES];
10 struct Node backup[MAX_CITIES*MAX_CITIES];
11 int visited[MAX_CITIES];
12 int k, n, r;
13 int min_len;
14
15 void
16 dfs(int c, int cur_len, int cur_toll)
17 {
18 int i;
19 struct Node *node;
20 if(cur_len>=min_len || cur_toll>k)
21 return;
22 if(c == n) {
23 min_len = cur_len;
24 return;
25 }
26 for(node=roads[c].next; node!=NULL; node=node->next) {
27 if(!visited[node->dest]) {
28 visited[node->dest] = 1;
29 dfs(node->dest, cur_len+node->len, cur_toll+node->toll);
30 visited[node->dest] = 0;
31 }
32 }
33 }
34
35 int
36 main(int argc, char **argv)
37 {
38 int i, s, d, l, t, cnt=0;
39 memset(visited, 0, sizeof(visited));
40 scanf("%d", &k);
41 scanf("%d", &n);
42 scanf("%d", &r);
43 for(i=1; i<=n; i++)
44 roads[i].next = NULL;
45 for(i=0; i<r; i++) {
46 scanf("%d %d %d %d", &s, &d, &l, &t);
47 backup[cnt].dest = d;
48 backup[cnt].len = l;
49 backup[cnt].toll = t;
50 backup[cnt].next = roads[s].next;
51 roads[s].next = backup+cnt;
52 ++cnt;
53 }
54 min_len = INF;
55 visited[1] = 1;
56 dfs(1, 0, 0);
57 if(min_len == INF)
58 printf("-1\n");
59 else
60 printf("%d\n", min_len);
61 }
問題:
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 (這個應(yīng)該是SYSU的哈哈，里面有西西里)
思路:
這個題是真不會做，即使是看別人代碼都看了快兩天，艾...
首先要解決的問題是如何求大數(shù)的模(這里大數(shù)用字符串表示)？
我們知道對于取模運算有: (a+b)%k = ((a%k)+(b%k))%k
(ab)%k = ((a%k)(b%k))%k
對于0-9的每個數(shù)，可以將其在個、十、百、千...位時模k的結(jié)果保存到一張表中: mod_arr
這樣，修改這個大數(shù)的任何一位而模k的新結(jié)果可以在O(1)時間內(nèi)取得
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數(shù)組始終不理解，結(jié)果TLE
更加容易理解的方案是BFS，每次擴(kuò)展改變一位數(shù)字
使用BFS的問題是如何判重？參考第二篇文章(繁瑣的C++語法，沒認(rèn)真看呵呵)，使用余數(shù)判重，其實還不是太理解
代碼:
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 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2676思路:
深度搜索
純粹按照題意進(jìn)行搜索，1532MS...額...就快TLE了呵呵
據(jù)discussion說，倒過來搜索時間會相當(dāng)快
代碼:
1 #define MAX_LEN 10
2 char table[MAX_LEN][MAX_LEN];
3 int flag;
4
5 int
6 is_available(int x, int y, char ch)
7 {
8 int j, k, small_x, small_y;
9 for(j=0; j<9; j++) /* row */
10 if(table[x][j]==ch)
11 return 0;
12 for(k=0; k<9; k++) /* column */
13 if(table[k][y]==ch)
14 return 0;
15 small_x = x/3;
16 small_y = y/3;
17 for(j=small_x*3; j<(small_x+1)*3; j++)
18 for(k=small_y*3; k<(small_y+1)*3; k++)
19 if(table[j][k]==ch)
20 return 0;
21 return 1;
22 }
23
24 void
25 dfs(int x, int y)
26 {
27 int i, j, nx, ny;
28 if(flag)
29 return;
30 if(x==9){
31 if(!flag) {
32 for(j=0; j<9; j++)
33 printf("%s\n", table[j]);
34 flag = 1;
35 }
36 return;
37 }
38 if(y==8) {
39 nx = x+1;
40 ny = 0;
41 } else {
42 nx = x;
43 ny = y+1;
44 }
45 if(table[x][y] == '0') {
46 for(i=1; i<=9; i++) {
47 if(is_available(x, y, i+'0')) {
48 table[x][y] = i+'0';
49 dfs(nx, ny);
50 table[x][y] = '0';
51 }
52 }
53 } else
54 dfs(nx, ny);
55 }
更好的解題代碼見:
http://blog.csdn.net/logic_nut/archive/2009/08/09/4428996.aspx