1、1本題可以直接對每一種貨物進行試探，當不滿足條件時（裝載貨物超重）即往上回溯，直到找到一種裝填方案或輸出問題無解。2用深搜，對每一個國家首都都進行一次深搜。假設當前搜索的是第i個國家的首都，這個國家的首都用字符串Si表示，先從矩陣中找到一個字符與Si1相等，以這個字符為起點，依次搜索si2,si3silength(si)。如果其中有一個環節不能再往下搜就回溯。直到搜索到整個字符串為止。3我們分析對于一個字符串abced，其中a與b，b與c，c與e之間既可以填=，又可以填，而e與d之間就只能填，為什么呢，因為a*b*c*e=d與a*b*c*d=e（*表示既可以是，又可以是）是同一種情況，我們只需

2、要考慮后一種情況就可以了。而在后一種情況中亦包含了a*b*c*de這一情況。因此，我們只需要先計算n個字符的所有排列中，逆序數分別為1,2,3,n的排列是多少，（令S表示一個排列，則S的逆序數為，我們用ai表示逆序數為i的排列的個數，則最終結果應是。4、先從一張郵票出發，在它的上、下、左、右分別聯接上一張郵票，刪去其中重復的。然后在剩下的二聯票的基礎上，在它們的上下左右再分別聯上一張郵票，刪去重復的，依此類推就可以得到問題的19個解。5、本題可以用一個數組a描述當前的狀態，當元素ai=*時,第i枚硬幣朝上，ai=o,第i枚硬幣朝下。移動規則：根據題意每次翻動-枚硬幣，相當于固定一枚硬幣，把其它

3、各枚硬幣翻個。所以每次有n種操作方案：固定第ii1.n枚硬幣，使其他硬幣翻個。搜索策略：把初始狀態（即每一枚硬幣正面朝上）作為當前狀態；（1）從當前狀態出發，運用條移動規則，產生新的狀態；（2）判斷新的狀態是否達到目標狀態（即每一枚硬幣反面朝上），如果是，轉（4）；（3）把新的狀態記錄下來，取出下一個中間狀態作為當前狀態，返回（2）；（4）輸出從初始狀態到目標狀態的路徑，結束。6可以用一個一維數組A1.9記錄每一步跳到的位置(X,Y)。馬最多有4個方向，若原來的橫坐標為i、縱坐標為j，則四個方向的移動可表示為：1：(i,j)(i+1,j+2) (i4,j7)；2：(i,j)(i+2,j+1)

4、(i3,j0,j1,j8)。搜索策略為：S1：A1：=(0,0)；S2：從A1出發，按移動規則依次選定某個方向，如果到達的是(8，4)則轉S3，否則繼續搜索下一個到達的頂點；S3：打印路徑。7因為題目要求我們輸出所有可能的登記順序，而數據的范圍也不大，不難看出它是一個搜索題目。由于方案數可能會比較大，如果要保存下所有的方案也是沒有必要的，因此我們宜采用深搜而放棄廣搜。深搜最大的缺點就是時間效率極為低下，雖然這一道題目用沒有經過任何優化的搜索就能出解，但我們還是可以對其作一些優化。一般來講，要確定某個順序第I位上的字母，我們是從“a“到“z”循環，依次查找，看哪個字母還可以再選，當可選字母的比較

5、少，且可選字母中每一個字母又可以選較多次時，每一重循環就有很多掃描是多余的。我們可以對這種情況作如下優化：在輸入完畢后，先統計出各種字母的總個數，并且將可選的字母按字典順序依次放入到一個字符串數組中（每個字母最多放一次），搜索的時候，我們將從“a”到“z”的循環改為從頭到尾掃描字符串數組，由于該字符串數組中的各字母都是可選的，所以我們每掃到一個字母，就將它插入到當前方案的序列中，并將它的可選次數減一，如果一個字母已經不能再選（可選次數為0），則暫時將它從字符串數組中刪去，等到當前過程遞歸調用完畢后再將其插入該字符串數組。這樣一來，就可以保證每一次循環掃描到的字母都是可選的，搜索中幾乎沒有了多余

6、的運算，要想再對搜索做更大的優化也不太可能了。8本題本質上是給出集合S，和定義在S上的一個等價關系集R。試求S中不同等價類的數目。我們可以把所有的矩形看做一個集合。由于劃分塊的方法是具有傳遞性和自反性的，故我們可以把它們看做一種等價關系。這樣，由于它具有傳遞性，故對于集合S中的某一個元素來說，我們應該把直接和該元素等價的元素與它標在同一個等價類中，再把與這些元素等價的元素標在同一個等價類中，以此類推，最后就可以得到該元素所在的等價類中的所有元素。我們可以對集合中的每個元素都應用該算法，就可以得出所有的等價類。該算法很容易證明是正確的，并且由于不同的等價類不會超過|S|個，而一個等價類中不同的元

7、素也不會超過|S|個，故也將在有限步后結束。更直觀的說，我們可以用圖論的方法來描述這個問題。我們可以把集合中的元素作為點，而在等價的點之間連上邊從而形成一個圖G。我們可以知道，圖中的一個連通塊實際上就相當于我們要求的一個等價類。這樣問題就變成了找連通分量。對于這個圖論的標準問題，我們可以在O(|S|2)的時間內使用圖遍歷法得出答案。在空間上，無論我們用什么方法存這個圖都需要至少O(|S|2)的空間，但這對于這道題來說太大了一些。不過考慮到圖遍歷法是不會對同一邊訪問兩次以上的，而該題中的邊還是可以計算出來的，故我們可以只用O(|S|)的空間保存各個矩形的信息，然后在訪問邊的時候動態計算出來就可以

8、了。9本題要求最少步數，顯然應采用廣度優先搜索。設A水壺內有a升水，B水壺內有b升水，則最多會有五種產生規則：（1）當a0且b0且a0時,可以從水壺A倒a升水給水缸4、當a0時,可以從水壺B倒b升水給水缸水壺B這時水壺A內有a升水；水壺B內有0升水；（5）當by時,可以從水缸倒y-b升水給這時水壺A內有a升水水壺B內有y升水。初始時，水壺A內有x升水，水壺B內有0升水。綜合數據庫：可用一個記錄類型描述一個狀態：atype=recordfather，a，b：word； end；father記錄當前節點的父親節點的編號，a、b表示當前狀態中，水壺A和水壺B里各有多少水。整個數據庫可用一個以為數組D

9、ATA1.10000 of atype;另外用一個標志數組bool，當boolI，j為真，表示水壺A為I升，水壺B為j升的狀態還沒有產生過，反之則表示已產生過。10、以四周邊界的點為初始值，每次找最低的點擴展，直到擴展所有點為止。11可以轉化成圖論中的最短路問題求解。還要求圈。12迭代加深搜。本題由于搜索層數不明，用深搜極易陷入死胡同，用廣搜空間又吃不消，這時迭代加深搜索就成了考慮的對象。確定了搜索模式之后，我們容易得到以下兩個基本思路： （ 1） 枚舉對象 分母a/b = 1/a1 + 1/a2 + + 1/an n不妨設a1 a2 an。剪枝手段 定分母的上下界設限定的搜索層數為D ，當前

10、搜到第C層，當前正要枚舉分母ak ，還需枚舉總和為x/y的分數。answerD表示當前最優解中的第D個分母，如果還沒有得到解則表示正無窮。則必然有：Max( y / x ，ak-1) + 1 ak Min ( (D-C+1) * y / x ，Maxlongint / x ，answerD-1 )枚舉的初值容易得出，但終值的確定則要用到我們一開始對分母有序性的假設了。值得注意的是，直接限界避免了搜索過程中屢次使用可行性剪枝，在一定程度上可以提高了程序的運行速度。13 枚舉切斷的邊（可以用隨機化），即時更新和重置被感染的人，加上最優性剪枝即可。 最優性剪枝： 求出剩下的人最好情況下的感染人數，加

11、上已感染的人數，如果比當前的最優解還要大，則無需繼續搜索。 本題用多次隨機化貪心的效果也不錯。14、這道題目描述非常簡單，但是它所蘊含的剪枝信息卻是較多而隱蔽的。有時候僅僅套用一些基本的剪枝模式來分析問題是理不出什么頭緒的，這就需要我們先人為的進行搜索模擬，再在模擬的過程中找到一些常識性的判斷條件。設當前待擴展節點為，它的四周未擴展節點為，已擴展節點為。剪枝一 對節點度的判斷 當前待擴展點的四周如果有度小于2或者兩個或兩個以上的度大于2的點,則無需再擴展下去。 當前待擴展點的四周如果存在度為2的點，則此點當仁不讓的成為下次擴展時應選擇的點。剪枝二 對邊界附近位置的考慮若當前待擴展點是第二行、或

12、倒數第二行、或第二列、或倒數第二列上的點，并且存在下圖所示四種情況之一；或者提前到達終點(n,1)；或者提前將路徑封死，即已擴展了點(n-1,1)和(n,2)，則可以進行可行性剪枝。 在第2行 在第n-1行 在第2列 在第n-1列剪枝三 對可行性的預見性判斷當得出下圖中的任何一個情況時都無需繼續擴展下去。 圖一 圖二三種剪枝共同使用可以使程序很快出解。15 本題是比較典型的求最優解問題，首先考慮的當然是動態規劃解題。可以得到一個狀態轉移方程：表示總體積為N的K層的最底層的半徑為i，高為j的蛋糕的最小表面積，顯然要用動態規劃解決該試題，在空間上是不可能承受的。因此采用搜索算法。這樣，上面的動態規

13、劃轉移方程也就成了搜索算法的基本框架。下面給出搜索算法的主過程：Procedure Find(N，i，j，K，S : Integer); Var X，Y : Integer; BeginIf K=0 then begin S:=S+i*i; if (S=X*X*Y then Find(N-X*X*Y，X，Y，K-1，S+i*i-X*X+2*X*Y) End;其中：N表示目前要搜索的蛋糕的剩余體積；K表示目前搜索到了蛋糕的第K層；i、j分別表示上一層的半徑和高；S表示已經搜索完畢的前面M-K層的表面積。單是這樣一個過程，算法效率是極低的，它沒有任剪枝，因此需要遍歷整個搜索樹。下面對問題進行剪枝。（1）最優化剪枝。首先可根據Min來進行剪枝，可看出：如果目前搜索到的面積SMin，則無論如何都不可能得到一個優于Min的解，因此不需要繼續向下搜索。（2）可行性剪枝。前面是根據Min來進行剪枝，下面根據N來進行剪枝。如果，也就是說體積為N的層數為K的滿足要求的蛋糕是不存在的，因為，是表示一個有K層的最小的蛋糕，即從第一層開始每一層的半徑和高都取滿足要求的最小值。這里是確定N的下界，自然也可以確定N的上界。如果當前體積大于，（i,j分別表示的K+1層蛋糕的半徑和高），也就是說體積為N、層數為K且滿足要求的蛋糕是不存在的，因為表示一個滿足最下一層蛋糕半徑小于i，