明解題報(bào)告acm習(xí)題集

1、Radar Installation1360Ame the coasting is an infinite straight line. Land is in one side ofcoasting, seahe other. Each small island is a polocatinghesea side. And any radar installation, locating on the coasting, can onlycover d distance, so an island installation, if the distance bethe sea can be c

2、overed by a radius n them is at most d.We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given theitionof each islandhe sea, and given the distance of the coverage of theradar installation, your task is to write a program

3、to find the number of radar installations to cover all the islands. Noteminimalttheitionofanislandisrepresentedbyitsx-ycoordinates.InputThe inp containsonsists ofseveral test cases. Theline of eachcasetwoegers n (1 n 1000) and d, where n is the number of islandshe sea and d is the distance of covera

4、ge of the radar installation.This is followed by n liach containinoegers representing thecoordinate of theition of each island. Then a blline follows to separate the cases.The input is terminated by a line containing pair of zeros.OutputFor each test case output one line consisting of the test case

5、numberfollowed by the minimal numberof radarinstallations case.needed.-1installation meansnosolutionfortSle Input3122-3 121102200Sle OutputCase 1: 2Case 2: 1貪心這道題挺費(fèi)腦筋的。把問題簡(jiǎn)化，就是在一個(gè)坐標(biāo)系里面，用圓心在 x 軸上，半徑為d 的圓，去覆蓋給出的 x 軸上或 x 軸上方的 n 個(gè)目標(biāo)點(diǎn)，求所需最少的圓數(shù)。稱半徑為 d 的圓為標(biāo)準(zhǔn)圓。這個(gè)問題看上去無從下手，但經(jīng)過一番觀察，發(fā)現(xiàn)，以這 n 個(gè)點(diǎn)為圓心作標(biāo)準(zhǔn)圓，將在x 軸上截得

6、n 條弦(包括一個(gè)點(diǎn)的情況)。每一條弦就代表了一個(gè)范圍，以弦上的點(diǎn)為圓心作標(biāo)準(zhǔn)圓都可以覆蓋弦所對(duì)應(yīng)的圓心，也就是目標(biāo)點(diǎn)。對(duì)于 x 軸上的某一點(diǎn)，它在多少條弦上，就表示以這點(diǎn)為圓心作標(biāo)準(zhǔn)圓可以覆蓋多少個(gè)目標(biāo)點(diǎn)。那么，可以將這些弦分成幾個(gè)集合，要求每個(gè)集合中的弦的交集不為空。這樣，對(duì)于每一個(gè)集合，只要在集合中的弦的交集上任取一點(diǎn)作標(biāo)準(zhǔn)圓，就可以完這個(gè)集合中的弦所對(duì)應(yīng)的目標(biāo)點(diǎn)。那么，所能劃分出的集合的最少數(shù)目即為題目所要求的。問題得到轉(zhuǎn)化。那么應(yīng)該如何劃分呢？通過與會(huì)議安排問題的類比，思考得出下面結(jié)論：按弦的右端點(diǎn)排序后，排在最前的沒有加入集合的弦的右端點(diǎn)，必然是所在集合的弦的交集的右端點(diǎn)，因?yàn)檫@個(gè)

7、集合中沒有一條弦的右端點(diǎn)會(huì)排在這條弦的右端點(diǎn)的左邊。對(duì)于每一個(gè)，都希望盡可能利用它，使它覆蓋盡可能多的目標(biāo)點(diǎn)。也就是說，每一個(gè)集合中都要加入盡可能多的弦。于是，設(shè)計(jì)出了一個(gè)貪心算法：將所有的弦按右端點(diǎn)遞增排序。選擇排在最前的沒有加入集合的弦，加入集合并做為基。然后往后遍歷所有的弦，如果弦的左端點(diǎn)在基的右端點(diǎn)的左邊，則當(dāng)前交集與其求交后結(jié)果必不為空，將其加入當(dāng)前集合。一輪選擇結(jié)束后，如果還有弦沒有被加入集合，則重復(fù)上面的步驟，統(tǒng)計(jì)出集合的數(shù)目即可。注意到每次開一個(gè)新的集合，都要遍歷后面所有的弦，是一個(gè)不小的開銷。那么，這么做有必要嗎？是否定的。每次遍歷，只需要遍歷到一條不滿足要求的弦，即可停止遍

8、歷，開始下一輪的選擇。假設(shè)在這條弦后存在一條弦，左端點(diǎn)在當(dāng)前集合的基的右端點(diǎn)的左邊，雖然沒有加入當(dāng)前集合，但在后面的集合中，可知這條弦的左端點(diǎn)在后面的集合的基的左端點(diǎn)的左邊，右端點(diǎn)的右邊，這條弦包含了后面的集合的基，可以加入后面的集合而不會(huì)影響集合的總數(shù)。這樣，算法就得到了簡(jiǎn)化，效率也大大提高。String Distance and Transform Pros1459String Distance is a non-negativeegert measures the distancebetn two strings. Here we give the definition. A trans

9、form list is alist of string, where each string, except for the last one, can be changed to the string followed by adding a character, deleting a character or replacing a character. The length of a transform list is the count ofstrings minus 1 (t is the count of operations to transform these twostri

10、ngs). The distance betn two strings is the length of a transformlist from one string to the other with the minimal length. You are to write a program to calculate the distance betn two strings and give the corresponding transform list.InputInponsists a sequence of string pairs, each string pair cons

11、ists twolines, each string occupies one line. The length of each string will beno moren 80.OutputFor each string pair, you should give aneger to indicate the distancebetn them at theline, and give a sequence ofd to transform d count, thenstring 1 to string 2.Eachd must bed is a line lead bythed. AIn

12、sert Delete Replace,value,valuewhereis theition of the string andshould d,be betn 1 andthe current length of the string (in Insertcan be 1 greatern the length), and value is a character. Actually manydlistscan satisfy therequest,butonlyoneofthemisrequired.Sle Inputabcac bcd aaaaabaaaaSle Output31234

13、1234Delete 1 Replace 3,dDelete4Insert Insert Insert Insert1,a2,a3,b7,a字符串編輯距離問題，動(dòng)態(tài)規(guī)劃這類字符串的題目做過很多的，基本上都是用動(dòng)態(tài)規(guī)劃去解決。因此考慮這個(gè)題是否也能夠用動(dòng)態(tài)規(guī)劃解決。觀察到題目的三種變換之間并沒有相互制約的關(guān)系，最優(yōu)變換序列的子序列必然是最優(yōu)的，若不是最優(yōu)的，將更優(yōu)的換上，則此變換序列比原最優(yōu)變換序列更優(yōu)，矛盾。因此，考慮使用動(dòng)態(tài)規(guī)劃。設(shè)所給的兩個(gè)字符串為 A1.m和 B1.n，定義 fi,j為 A1.i和 B1.j的編輯距離。先考慮單一字符 a，b 間的編輯距離 t ：0當(dāng) a = bt(a,b

14、) = 1當(dāng) a b考慮從字符串 A1.i到字符串 B1.j的變換?？煞譃橐韵聨追N情況：(1)將字符 Ai改為字符 Bj：需要 t(Ai,Bj) 次操作。(2)刪除字符 Ai：需要 1 次操作。(3)字符 Bj：需要 1 次操作。因此，可以得到 fi,j的轉(zhuǎn)移方程：fi-1,j-1= min fi-1,j +fi,j-1 + t(Ai,Bj) 11fi,j再考慮邊界情況：fi,0 = i, i = 0 . m，f0,j = j, j = 0 . n由于題目還要態(tài)轉(zhuǎn)移方程，構(gòu)造出解答，所以考慮保留所有的狀態(tài)值。否則，由上面的狀可以看出要計(jì)算 fi,j，只依賴于當(dāng)前行和前一行兩行的數(shù)據(jù)，我們可以通

15、過引入輔助變量，將空間的需求減至一維。這道題還有一個(gè)麻煩的事情：構(gòu)造出編輯序列?；氐角懊娴那闆r，采取從后往前倒向編輯的思路，并讓每一步的操作與狀態(tài)的轉(zhuǎn)移對(duì)應(yīng)：構(gòu)造 fi,j時(shí)：(1)當(dāng) i = 0 且 j = 0 時(shí)，構(gòu)造結(jié)束。(2)當(dāng) i 0 且 ( j = 0 或 fi,j = fi-1,j + 1) 時(shí)，表示要在刪去第 i 個(gè)字符，即 Delete i。然后構(gòu)造 fi-1,j。(3)當(dāng) j 0 且 ( i = 0 或 fi,j = fi,j-1 + 1) 時(shí)，表示要在第 i+1 個(gè)字符前字符 Bj，即 Insert i+1,Bj。然后構(gòu)造 fi,j-1。(4)當(dāng) Ai = Bj 且 (f

16、i,j = fi-1,j-1) 時(shí)，表示不需要修改。然后構(gòu)造 fi-1,j-1。(5)當(dāng) Ai Bj 且 (fi,j = fi-1,j-1 + 1) 時(shí)，表示要將 Ai替換成 Bj，即 Replace i,Bj。然后構(gòu)造 fi-1,j-1。這樣構(gòu)造還是相當(dāng)簡(jiǎn)單方便的，由于是倒向編輯，所以不用擔(dān)心 Delete 和 Insert的位置變化問題，只需要循環(huán)就可以構(gòu)造出了。不過這個(gè)程序費(fèi)時(shí) 0.07s，令人不爽。再嘗試正向編輯。關(guān)鍵問題就是位置變化，通過引入一個(gè)輔助變量p位置的變化量，這樣通過p 就可以修正位置了。初始時(shí) p = 0。構(gòu)造 fi,j時(shí)：(1)當(dāng) i = 0 且 j = 0 時(shí)，構(gòu)造結(jié)

17、束。(2)當(dāng) i 0 且 (j = 0 或 fi,j = fi-1,j + 1) 時(shí)，構(gòu)造 fi-1,j，然后刪去第 i+p 個(gè)字符，即 Delete i+p。同時(shí) p 減去 1，表示后面的字符的位置都要往左邊偏移一個(gè)位置。(3)當(dāng) j 0 且 (i = 0 或 fi,j = fi,j-1 + 1) 時(shí)，構(gòu)造 fi,j-1，然后在第i+1 個(gè)字符前字符 Bj，即 Insert i+p+1,Bj。同時(shí) p 加上 1，表示后面的字符的位置都要往右邊偏移一個(gè)位置。(4)當(dāng) Ai = Bj 且 (fi,j = fi-1,j-1) 時(shí)，構(gòu)造 fi-1,j-1，然后不需要修改。(5)當(dāng) Ai Bj 且 (

18、fi,j = fi-1,j-1 + 1) 時(shí)，構(gòu)造 fi-1,j-1，然后將Ai替換成 Bj，即 Replace i+p,Bj。正向編輯的程序僅費(fèi)時(shí) 0.03s，！第一！讓人驚異：遞歸的比循環(huán)的還節(jié)省時(shí)間？Dp1479In a room with n rows and mcolumns, Dp and her child is separated bysome laser beams and obstacles. Dp has to manage to make through thelaser beams to rescue her child. She can pour some wate

19、r on herself andwalk through a cell with laser beams, and arriveell without laserbeams, when her body is dry again. Dp can walk in eight directions.Dp can only pour water in a cell without laser beams, so she is notable to walk over two continuous cells with laser beams. Laser beam stops at obstacle

20、 or other laser generator.Its your turn tol the minimum number of times Dp has to pour wateronto herself in order to reach the cell of her child.InputThere are multiple caseshe input, separated with bllines. Pleasepros toof file.Theline of each case containsegers n and m (1 = n, m Sj, you are to cal

21、culate the minimal total difficulty to provet the given sements are equivalent.InputThe inpontains several cases. Each case begins wineger n (2= n Sj. The itheger of the ith row is always 0 as its obvioustSi concludes Si. All the n * negers are bet Input is terminated by EOF.n 0 and 100, inclusively

22、.OutputFor each test case, output a line with the minimal difficulty for case.tSle Input40592 3 40 7 810 0 1213 14 15 0Sle Output34圖論這是一道很不錯(cuò)的圖論題。題目要求求出證明幾個(gè)命題相互等價(jià)的最小代價(jià)，并給出了圖 G，Gi,j表示證明 Si = Sj 所需要的代價(jià)。經(jīng)過抽象，可以得出，題目就是要求圖 G 的一個(gè)回路，要求所有的點(diǎn)都至少在上面出現(xiàn)一次，且回路的總長度最短。注意，與回路的不同在于允許某些點(diǎn)出現(xiàn)多次。只需要用 Floyd對(duì)原圖求所有點(diǎn)對(duì)間的最短路徑，構(gòu)造

23、出新圖 G（G中兩兩點(diǎn)之間都是最短路徑），然后求 G的最短回路，得到的就是原圖中所求的最短回路。證明如下：假設(shè) C 是一個(gè)滿足要求的原圖中的最短回路，C 上包含了圖 G 的所有點(diǎn)，但某些點(diǎn)可能出現(xiàn)多次。設(shè) C 上的點(diǎn)為 v1, v2, ., vk，設(shè)集合 S 初始為空。首先，令當(dāng)前點(diǎn)為 v1，顯然 v1 不在 S 中，把 v1 加入 S。然后繼續(xù)看 C 中后面的點(diǎn)，直到找到一個(gè)不在 S 中的點(diǎn) u。如果 v1 和 u 之間不是 v1 到 u 的最短路徑，則可以把這一段用最短路徑換上，得到更 短的回路 C，顯然與假設(shè)不符，所以 v1 和 u 之間一定是 v1 到 u 的最短路徑。然后把 u 加入

24、 S，繼續(xù)找下一個(gè)不在 S 中的點(diǎn) u，顯然 u 到 u之間也是最短路徑。繼續(xù)重復(fù)下去，直到把 C 上所有的點(diǎn)找完。這些點(diǎn)依次被加入集合 S，這個(gè)加入順序就了一個(gè)新圖G（G中兩兩點(diǎn)之間都是最短路徑）上的回路。可見，圖 G 的滿足條件的最短回路一定是 G的某一條回路?；芈?。所以 G的最短回路就是 G 中的最短需要注意，在 Floyd 中要下具體路徑。在最后用枚舉全排列的方法枚舉圈，計(jì)算圈長時(shí)，不能重復(fù)計(jì)算某些已經(jīng)計(jì)算過的邊，因此要利用到先前體路徑進(jìn)行排查。我就是這個(gè)原因，在最后一個(gè)數(shù)據(jù)上 WA 掉了。下的具另外，在枚舉圈時(shí)，由于這個(gè)圈從哪個(gè)點(diǎn)開始都是一樣的，所以可以固定點(diǎn) 1 為開始點(diǎn)，這樣可以

25、減少不必要的枚舉。還有我在計(jì)算圈長時(shí)用了遞歸，如果不用，速度應(yīng)該會(huì)更快的。Count the Colors1610Paing some colored segments on a line, some previously pa may be covered by some the subsequent ones.ed segmentsYour task is counting the segments of different colors you can seeast.InputTheline of each data set contains exactly oneeger n, 1 =

26、 n= 8000, equal to the number of colored segments.Each of the following n lines consists of exactly 3 nonnegativeegersseparated by single spa:x1 x2 cx1 and x2 indicate the left endpoand right endpoof the segment,c indicates the color of the segment.All the numbers arehe range 0, 8000, and theyare al

27、legers.Input may contain several data set, pros toof file.OutputEach line of the output should contain a color indext can be seen fromthe top, following the count of the segments ofthiscolor,theyshouldbepred according to the color index.Ifsomecolorcant be seen, you shouldntprit.Prabllineaftereveryda

28、taset.SleInput50043401012121123232011001Sle Output123111110121線段樹這是一道很經(jīng)典的題目。像這類有先后次序的疊加，然后進(jìn)行統(tǒng)計(jì)，一般都可以采用離散化 + 線段樹的方法來做。離散化主要是可以減少規(guī)模，而且方便進(jìn)行相關(guān)的計(jì)算，如計(jì)算長度、面積等。線段樹則可以方便地將各線段的統(tǒng)計(jì)結(jié)合起來，充分利用已知信息，降低統(tǒng)計(jì)的時(shí)間復(fù)雜度。這道題要求的是最后所能看到的各種顏色的線段數(shù)。由于只需要求一個(gè)統(tǒng)計(jì)數(shù)，所以離散化可以省去不做。線段樹中的每個(gè)結(jié)點(diǎn)中用變量 color下此區(qū)間的顏況，color = 0.8000 表示此區(qū)間是單一的顏色 color，

29、color = 8001 表示此區(qū)間為底色，color = -1 表示此區(qū)間的顏色不唯一。算法不難，統(tǒng)計(jì)算法則要費(fèi)點(diǎn)腦筋，需要依靠區(qū)間兩端的顏色來加以判斷。如果區(qū)間a,b為單一顏色 c，則返回此區(qū)間最左 邊和最右邊的顏色為c，同時(shí)將顏色為c 的線段數(shù)加 1。否則，令m = (a + b) DIV 2，統(tǒng)計(jì)左邊區(qū)間a,m，和右邊區(qū)間m,b，然后進(jìn)行判斷，如果左邊區(qū)間的右端點(diǎn)顏色 和右邊區(qū)間的左端點(diǎn)顏色相同，則左邊和右邊是同一條線段，前面重復(fù)累計(jì)了一次，則將此顏色的線段數(shù)減 1。然而，據(jù)說這道題最快的方法是最原始的染色！Place the Robots1654Robert is a famous

30、engineer. One day he was given a task by his background of the task was the following:s. TheGiven a map consisting of square blocks. There were three kinds of blocks:Wall, Grass, and Empty. Hiss wanted to place as many robots assiblehe map. Each robot held a laser weapon which could shoot to fourdir

31、ections (north, east, south, west) simultaneously. A robod to stayat the block where it was initially placed all the time and to keep firing all the time. The laser beams certainly could pass the grid of Grass, but could not pass the grid of Wall. A robot could only be placed in an Empty block. Sure

32、ly the s would not want to see one robot hurting another. In other words, two robots must not be placed in one line (horizontallyor vertically) unless there is a Wall betn them.Nowt you are such a smart programmer and one of Roberts best friends, He is asking you to help him solving this problem.t i

33、s, given thedescription of a map, compute theum number of robotst can beplacedhe map.InputThe cases.line contains aneger T (= 11) which is the number of testFor each test case, theline contains twoegers m and n (1= m,n RX#oX*o顯然，放置一個(gè) Robot 后，上下左右四個(gè)方向在遇到#之前的所有格子均成為了。每放一個(gè) Robot，影響到的是行上兩個(gè)#之間的格子，和列上兩個(gè)#之

34、間的格子。這就給了一個(gè)啟示：將棋盤“線段化”。一段無法再向左右擴(kuò)展的連續(xù)非墻格子稱為行線段，將一段無法再向上下擴(kuò)展的連續(xù)非墻格子稱為列線段。數(shù)字，列線段標(biāo)字母，有：把棋盤分別按行線段、列線段標(biāo)出序號(hào)，行線段標(biāo)棋盤o*#oo#o*o行線段11112#列線段 abdf a#ac#gaceg- 33#45555-如果在某個(gè)格子k 放置一個(gè) Robot，那么 k 必然是某條行線段 i 和某條列線段j 的交點(diǎn)。顯然，任意一條行線段和列線段最多只能存在一個(gè)交點(diǎn)，交點(diǎn)處就是放置 Robot處。這又啟發(fā)問題轉(zhuǎn)化為匹配問題。設(shè)有二分圖 G，X 集合為行線段集合，Y 集合為列線段集合。若在棋盤(i,j)上可以放置

35、一個(gè) Robot，(i,j)屬于行線段 a 和列線段 b，則在二分圖中連一條邊(a,b)。二分圖中的每一條邊，就對(duì)應(yīng)一個(gè) Robot 的放置，因此只要求出二分圖 G 的最大匹配即可。問題涉及到圖 G 的問題，由 ZJU 1002 的限界，可以知道，行線段（或列線段）最多的情況是如下所示：o#o# #o#o o#o#o#o因此，可以知道，圖中至多有 50 * 50 / 2 = 1250 條行線段（或線段）。顯然，用鄰接矩陣來。，時(shí)間和空間上都不能接受，因此，選用鄰接表做為結(jié)構(gòu)若問題規(guī)模再大一些，還可以采取別的優(yōu)化方法：找出棋盤中的連通塊，每次只處理通塊。這樣可以減少問題的規(guī)模。Lagranges

36、 Four-Square Theorem1738The factt anyitiveeger has a represenion as the sum of atmost fouritive squares (i.e. squares ofitiveegers) is knownas Lagranges Four-Square Theorem. Thepublished proof of thetheorem was given by Joseph-Louis Lagrange in 1770. Your mishoweveris not show suchto explahe origina

37、l proof nor to discover a new proof but tot the theorem holds for some specific numbers by counting how many sible represenions there are.For agivenitiveeger n, you should report the number of allrepresenions of n as the sum of at most fouritive squares. The orderof addition does not matter, e.g. yo

38、u should consider 42 + 32 and 32+ 42 are the same represenion.For ex represen report 3 separale, lets check the case of 25. Thiseger has just three ions 12+22+22+42, 32 + 42, and 52. Thus you shouldhis case. Be careful not to count 42 + 32 and 32 + 42y.InputThe inputitive zero. Theis comed of at mos

39、t 255 lines, each containing a singleeger lessn 215, followed by a line containing a single last line is not a part of the input data.OutputThe output should be comed of lines, each containing a singleeger.No other characters should appearhe output.The outputeger corresponding to the inputeger n is

40、the number ofall represenionsofnasthesumofatmostfouritivesquares.Sle Input1252003211200070Sle Output13487738經(jīng)典動(dòng)態(tài)規(guī)劃，有限背包問題這也算是一道很經(jīng)典的動(dòng)態(tài)規(guī)劃題。題目要求的是將一個(gè)數(shù)拆分成最多四個(gè)平方數(shù)的和的方法數(shù)，而且要注意 32 + 42 和 42 + 32 只能算一種?？梢园堰@個(gè)問題轉(zhuǎn)化為背包問題：背包容量為要拆分的數(shù)，物品為小于這個(gè)數(shù)的平方數(shù)。但這個(gè)背包問題和以往的不太相同，它限制了最多能取的物品的個(gè)數(shù)。稱其為有限背包問題。這個(gè)問題仍然可以用動(dòng)態(tài)規(guī)劃的方法來解決，只要增加維數(shù)

41、，細(xì)化狀態(tài)即可。設(shè) muli = i * i，totalm,n,k表示m 個(gè)平方數(shù)的范圍內(nèi)，把 n 拆分成 k 個(gè)平方數(shù)之和的方法數(shù)，m = 1.Sqrt(32768)，n = 0.32768, k = 0.4。平方數(shù)看成是物品，以物品(即 m)為階段進(jìn)行計(jì)算，每次增加一個(gè)物品 muli。對(duì)于每個(gè)數(shù) n，若 n = muli，則原來已經(jīng)有 totalm-1,n,k種拆成 k 個(gè)平方數(shù)之和的 方法，現(xiàn)在增加了一個(gè)物品 muli，則多出了 totalm-1,n-muli,k-1種方法，total m,n,k = totalm-1,n,k + totalm-1,n-muli,k-1。初始條件為 to

42、talm,0,0 = 1，m = 1.Sqrt(32768)，其它為 0。從上面的式子中，注意到 totalm,.,.只與 totalm-1,.,.有關(guān)，這樣可以省去 m 維，直接在 totaln,k上進(jìn)行累加計(jì)算即可。最后，totaln,1 + totaln,2 + totaln,3 + totaln,4即為 n 拆分成最多 k 個(gè)平方數(shù)之和的方法數(shù)。這道題與 ZJU 1163 有非常相像的地方，需要注意到值的傳遞問題，切記！Square1909Given a set of sticks of various lengths, is itsible to johem end-to-end t

43、o form a square?InputTheline of inpontains N, the number of test cases. Each testcase begins wineger 4 = M = 20, the number of sticks. Megersfollow; each gives the length of a stick - aneger betn 1 and 10,000.OutputFor each case, output a line containing yesifisissibletoformasquare; otherwise output

44、 no.Sle Input34581 1 110 201 7 2130 40 506 4 4 3 5Sle Outputyes no yes搜索，無解判斷 + 排序優(yōu)化 + 有序化枚舉 + 可行性剪枝這道題是要求判斷是否能將所給的 M 條木棍拼接成一個(gè)正方形。由于邊長最大可達(dá) 10000，用動(dòng)態(tài)規(guī)劃顯然不切實(shí)際，所以考慮使用搜索。在搜索之前，應(yīng)先判斷問題是否一定無解，以避免不必要的搜索。先計(jì)算出 M 條總長 sum，如果 sum 不是 4 的倍數(shù)，顯然這 M 條木棍不可能組成正方形。再計(jì)算出正方形每一邊的長度 max = sum / 4，如果 M 條木棍中有長度大于 max 的，則這 M 條木

45、棍也不可能組成正方形。對(duì)于這兩種情況，可以馬上輸出no。設(shè) squarei = max 表示正方形第 i 條邊剩余的長度。對(duì)于這個(gè)問題，搜索的方式有很多種：(1)以數(shù)為階段進(jìn)行搜索，每次考慮將一條木棍放在一條邊上。(2)以正方形的邊為階段進(jìn)行搜索，每次考慮往某一條邊上放木棍。顯然，第二種搜索方式可以更好的利用可行性剪枝及早回溯，比第一種搜索方式高效得多。因此，的搜索算法就定下來了：每次對(duì)一條邊進(jìn)行搜索，從沒有用過的木棍中選一條放在上面，如果 squarei = 0 則搜索下一條邊，否則繼續(xù)搜索當(dāng)前邊。一但所有邊都可以成功安排，輸出yes，否則最后輸出no。還可以進(jìn)行一些優(yōu)化：(1)上先安排長度

46、大的木棍可以更快的找到解或是回溯，因此搜索前就將木棍按長度從大到小排序。事實(shí)證明這一優(yōu)化是相當(dāng)有效的，先安排小的程序耗時(shí) 0.11s，先安排大的程序僅耗時(shí) 0.05s。(2)在搜索過還應(yīng)該避免一些重復(fù)的枚舉，即對(duì)某一條邊進(jìn)行搜索時(shí)，保持枚舉變量單調(diào)遞增。除了這樣，搜索各條邊時(shí)，還可以保持起點(diǎn)的枚舉變量單調(diào)遞增。通過這樣的有序化，可以減少不必要的搜索，提高出解的速度。(3)對(duì)于第一條邊，可以直接將一根木棍指定上去：因?yàn)檫@條邊若不包含這條木棍，由于枚舉變量的有序化，這根木棍以后就不可能再被使用了，與題意不符，所以這根木棍一定在這條邊上。通過這樣的指定，就減少了搜索量（主要是對(duì)于無解的情況）。這個(gè)優(yōu)

47、化使程序的時(shí)間從 0.05s 減少到了 0.02s，相當(dāng)厲害！(4)除了第一條邊可以直接將一根木棍指定上去，稍加思考后還會(huì)發(fā)現(xiàn)，在對(duì)每一條邊進(jìn)行搜索時(shí)，都可以將第一根未使用的木棍指定上去，理由同上。這個(gè)進(jìn)一步的優(yōu)化，使程序的時(shí)間從 0.02s 降到了 0.00s，完美解決問題！(5)還可以把最后一條邊的搜索去掉，因?yàn)樗淹昵叭龡l邊后，剩下的木棍必然是第四條邊上的。只要將剩下的序的時(shí)間已經(jīng)產(chǎn)生不了影響長度加起來進(jìn)行判斷即可。不過這一優(yōu)化對(duì)我程(6)這道題能不能用分類的方法剪枝呢？應(yīng)該是可以的，這樣就減少了一些重復(fù)搜索的組合。但是這道題的限制條件（正方形等）太強(qiáng)了，以至于這個(gè)剪枝發(fā)揮的作用相當(dāng)小。T

48、ravelling Fee2027Samball is going to travelhe coming vacation. Now its time to makea plan. After choosing the destination city, the next sts to determinethe travel route. As this pouy has just experienced a tragic lost of money, he really has limited amount of money to spend. He wants to findthe mos

49、t costless route. Samball has just learnedt the travel companywill carry out a discount strategy during the vacation: the most expensiveflight connectin a big news.o cities along the route will be free. This is reallyNow given the source and destination cities, and the costs of all theflights, you are to calculate the mi