今日，你了嗎？AC2023/11/211第一講一招制敵之搜尋題2023/11/212 依據(jù)“信息學(xué)初學(xué)者之家”網(wǎng)站的統(tǒng)計(jì)，Ural〔俄羅斯的Ural州立大學(xué)的簡稱，那里設(shè)立了一個(gè)UralOnlineProblemSet，并且支持OnlineJudge?！车念}目類型或許呈如下的分布：

搜尋動(dòng)態(tài)規(guī)劃貪心構(gòu)造圖論 約10%約15%約5%約5%約10% 計(jì)算幾何純數(shù)學(xué)問題數(shù)據(jù)構(gòu)造其它

約5%約20%約5%約25%統(tǒng)計(jì)信息：2023/11/213搜尋題特點(diǎn)分析:題意簡潔理解算法相對固定編程有路可循競賽必備學(xué)問2023/11/214——摘自《ACM競賽之新人向?qū)?/p>

》 “算法中最根本和常用的是搜尋，主要是回溯和分支限界法的使用。這里要說的是，有些初學(xué)者在學(xué)習(xí)這些搜尋根本算法是不太留意剪枝，這是特別不行取的，由于全部搜尋的題目給你的測試用例都不會(huì)有很大的規(guī)模，你往往覺察不出程序運(yùn)行的時(shí)間問題，但是真正的測試數(shù)據(jù)肯定能過濾出那些沒有剪枝的算法。實(shí)際上參賽選手根本上都會(huì)使用常用的搜尋算法，題目的區(qū)分度往往就是建立在諸如剪枝之類的優(yōu)化上了。”引言2023/11/215什么是搜尋算法呢？ 搜尋算法是利用計(jì)算機(jī)的高性能來有目的地窮舉一個(gè)問題的局部或全部的可能狀況，從而求出問題的解的一種方法。

搜尋過程實(shí)際上是依據(jù)初始條件和擴(kuò)展規(guī)章構(gòu)造一棵解答樹并查找符合目標(biāo)狀態(tài)的節(jié)點(diǎn)的過程。

2023/11/216舉例分析從簡潔的字符串搜尋講起2023/11/217HDOJ_1238SubstringsYouaregivenanumberofcase-sensitivestringsofalphabeticcharacters,findthelargeststringX,suchthateitherX,oritsinversecanbefoundasasubstringofanyofthegivenstrings.

InputThefirstlineoftheinputfilecontainsasingleintegert(1<=t<=10),thenumberoftestcases,followedbytheinputdataforeachtestcase.Thefirstlineofeachtestcasecontainsasingleintegern(1<=n<=100),thenumberofgivenstrings,followedbynlines,eachrepresentingonestringofminimumlength1andmaximumlength100.Thereisnoextrawhitespacebeforeandafterastring.

OutputThereshouldbeonelinepertestcasecontainingthelengthofthelargeststringfound.

2023/11/218SampleInput

2

3

ABCD

BCDFF

BRCD

2

rose

orchidSampleOutput

2

2

2023/11/219題目分析：這是一道入門級別的搜尋題，根本思想比較簡潔，但是假設(shè)用最樸實(shí)的算法，可能會(huì)超時(shí)如何降低算法的簡單度呢？下面的算法如何：先將字符串按長度從短到長排序，枚舉最短的字符串的子串，推斷是否都是別的字符串的子串，求出最大長度即可。2023/11/2110說明： 此題除了可以練習(xí)根本搜尋算法，也是練習(xí)字符串處理的好題目，題中用到的相關(guān)學(xué)問點(diǎn)有：求反串求子串字符串查找求字符串長度猛烈推舉?。?023/11/2111再來一道數(shù)值型搜尋題2023/11/2112HDOJ_1239

CallingExtraterrestrialIntelligenceAgainProblemDescriptionAmessagefromhumanstoextraterrestrialintelligencewassentthroughtheAreciboradiotelescopeinPuertoRicoontheafternoonofSaturdayNovember16,1974.Themessageconsistedof1679bitsandwasmeanttobetranslatedtoarectangularpicturewith23*73pixels.Sinceboth23and73areprimenumbers,23*73istheuniquepossiblesizeofthetranslatedrectangularpictureeachedgeofwhichislongerthan1pixel.Ofcourse,therewasnoguaranteethatthereceiverswouldtrytotranslatethemessagetoarectangularpicture.Eveniftheywould,theymightputthepixelsintotherectangleincorrectly.ThesendersoftheArecibomessagewereoptimistic.

Weareplanningasimilarproject.Yourtaskintheprojectistofindthemostsuitablewidthandheightofthetranslatedrectangularpicture.Theterm“mostsuitable“isdefinedasfollows.Anintegermgreaterthan4isgiven.Apositivefractiona/blessthanorequalto1isalsogiven.Theareaofthepictureshouldnotbegreaterthanm.Bothofthewidthandtheheightofthetranslatedpictureshouldbeprimenumbers.Theratioofthewidthtotheheightshouldnotbelessthana/bnorgreaterthan1.Youshouldmaximizetheareaofthepictureundertheseconstraints.

Inotherwords,youwillreceiveanintegermandafractiona/b.Itholdsthatm>4and0<a/b<1.Youshouldfindthepairofprimenumbersp,qsuchthatpq<=manda/b<=p/q<=1,andfurthermore,theproductpqtakesthemaximumvalueamongsuchpairsoftwoprimenumbers.Youshouldreportpandqasthe“mostsuitable“widthandheightofthetranslatedpicture.

2023/11/2113InputTheinputisasequenceofatmost2023tripletsofpositiveintegers,delimitedbyaspacecharacterinbetween.Eachlinecontainsasingletriplet.Thesequenceisfollowedbyatripletofzeros,000,whichindicatedtheendoftheinputandshouldnotbetreatedasdatatobeprocessed.

Theintegersofeachinputtripletaretheintegerm,thenumeratora,andthedenominatorbdescribedabove,inthisorder.Youmayassume4<m<=100000and1<=a<=b<=1000.

OutputTheoutputisasequenceofpairsofpositiveintegers.Thei-thoutputpaircorrespondstothei-thinputtriplet.Theintegersofeachoutputpairarethewidthpandtheheightqdescribedabove,inthisorder.

Eachoutputlinecontainsasinglepair.Aspacecharacterisputbetweentheintegersasadelimiter.Noothercharactersshouldappearintheoutput.

2023/11/2114SampleInput

512

99999999999

1680516

197011

2023411

000SampleOutput

22

313313

2373

4343

3753

2023/11/2115獵取有用信息a.給定整數(shù)m,a,b(4<m<=100000and 1<=a<=b<=1000)b.需要找到兩個(gè)數(shù)(不妨設(shè)為p,q)滿足以下條件：p,q均為質(zhì)數(shù)；p*q<=m;a/b<=p/q<=1;c.輸出全部滿足以上條件的p,q中乘積最大的一對p,q(最大的p和最小的q,應(yīng)當(dāng)是相鄰的兩個(gè)質(zhì)數(shù))2023/11/2116算法分析1.典型的搜尋從全部可能的p,q中查找滿足條件的一對2.p,q的要求p,q均為質(zhì)數(shù),且p<=q<=100000;3.按上述思想流程應(yīng)為a.從1—100000中搜出質(zhì)數(shù)b.兩層循環(huán)，試遍全部的組合(p,q可能相等〕c.每種組合去推斷是否符合條件，如是，將p*q與當(dāng)前最大值比較，推斷，保存2023/11/2117面臨的問題：超時(shí)！從1—100000的質(zhì)數(shù)運(yùn)算約為1e+8,而這只是預(yù)備工作。因此，如不加以分析簡化此題無法在規(guī)定時(shí)間內(nèi)出解2023/11/2118深入分析考慮大于10000的某個(gè)質(zhì)數(shù)，不妨設(shè)為Q，另一個(gè)質(zhì)數(shù)為P，則：假設(shè)P<10，P/Q<0.001假設(shè)P>10，P*Q>100000而考慮到a,b的取值范圍(1<=a<=b<=1000)可知min(a/b)=0.001同時(shí)，要求：p*q<=m<=10000所以無論如何質(zhì)數(shù)都不能超過10000?！彩聦?shí)上，不會(huì)超過9091〕然而，這是最小的范圍嗎？p,q的范圍其實(shí)可在2—50000(why?)2023/11/2119搜尋時(shí)的技巧：搜尋挨次很重要。應(yīng)當(dāng)從大往小搜 〔num:質(zhì)數(shù)的個(gè)數(shù)〕 for(i=num-1;i>=0;i--) for(j=i;j<=num-1;j++)……

留意剪枝：If(a[j]>m||a[j]*a[i]>m||((double)a[i]/a[j])<s) ……2023/11/2120真正的搜尋題迷宮搜尋2023/11/2121預(yù)備學(xué)問——樹的遍歷樹的遍歷主要有如下四種方法：1.先根/序遍歷2.中根/序遍歷3.后根/序遍歷4.層次遍歷分別有什么特點(diǎn)呢？2023/11/2122〔1〕先根遍歷對樹的訪問次序是:1.先訪問根結(jié)點(diǎn)2.再訪問左子樹3.最終訪問右子樹4.對于左右子樹的訪問也要滿足以上規(guī)章例如如下：2023/11/2123以上二叉樹的先根遍歷序列是：？？21357461、2、4、5、3、6、72023/11/2124〔2〕中根遍歷對樹的訪問次序是:1.先訪問左子樹2.再訪問根結(jié)點(diǎn)3.最終訪問右子樹4.對于左右子樹的訪問也要滿足以上規(guī)章例如如下：2023/11/2125以上二叉樹的中根遍歷序列是：？？21357464、2、5、1、6、3、72023/11/2126〔3〕后根遍歷對樹的訪問次序是:1.先訪問左子樹2.再訪問右子樹3.最終訪問根結(jié)點(diǎn)4.對于左右子樹的訪問也要滿足以上規(guī)章例如如下：2023/11/2127以上二叉樹的后根遍歷序列是：？？21357464、5、2、6、7、3、12023/11/2128〔4〕層次遍歷對樹的訪問次序是:1.先訪問根結(jié)點(diǎn)2.再訪問根結(jié)點(diǎn)的子節(jié)點(diǎn)〔即其次層節(jié)點(diǎn)〕3.再訪問第三層節(jié)點(diǎn)4.……例如如下：2023/11/2129以上二叉樹的層次遍歷序列是：？？21357461、2、3、4、5、6、72023/11/2130幾個(gè)根本概念：初始狀態(tài)：略目標(biāo)狀態(tài)：略狀態(tài)空間：由于求解問題的過程中分枝有很多〔主要是求解過程中求解條件的不確定性、不完備性造成的〕，使得求解的路徑很多，這就構(gòu)成了一個(gè)圖，我們說這個(gè)圖就是狀態(tài)空間。狀態(tài)空間搜尋：就是將問題求解過程表現(xiàn)為從初始狀態(tài)到目標(biāo)狀態(tài)查找這個(gè)路徑的過程。通俗點(diǎn)說，就是在解一個(gè)問題時(shí)，找到一條解題的過程，可以從求解的開頭到問題的結(jié)果。2023/11/2131初始狀態(tài)：目標(biāo)狀態(tài)：2831647512384765例九宮重排問題2023/11/213228316475283147652831647583214765283147652318476528316475283147652318476523184765283714652023/11/2133231847651238476512384765123784652023/11/2134三、廣度優(yōu)先搜尋 根本思想：從初始狀態(tài)S開頭，利用規(guī)章，生成全部可能的狀態(tài)。構(gòu)成樹的下一層節(jié)點(diǎn)，檢查是否消失目標(biāo)狀態(tài)G，假設(shè)未消失，就對該層全部狀態(tài)節(jié)點(diǎn)，分別挨次利用規(guī)章。生成再下一層的全部狀態(tài)節(jié)點(diǎn)，對這一層的全部狀態(tài)節(jié)點(diǎn)檢查是否消失G，假設(shè)未消失，連續(xù)按上面思想生成再下一層的全部狀態(tài)節(jié)點(diǎn)，這樣一層一層往下開放。直到消失目標(biāo)狀態(tài)為止。2023/11/2135BFS算法： 〔1〕把起始節(jié)點(diǎn)S線放到OPEN表中〔2〕假設(shè)OPEN是空表，則失敗退出，否則連續(xù)。〔3〕在OPEN表中取最前面的節(jié)點(diǎn)node移到CLOSED表中。〔4〕擴(kuò)展node節(jié)點(diǎn)。假設(shè)沒有后繼〔即葉節(jié)點(diǎn)〕，則轉(zhuǎn)向〔2〕循環(huán)?！?〕把node的全部后繼節(jié)點(diǎn)放在OPEN表的末端。各后繼結(jié)點(diǎn)指針指向node節(jié)點(diǎn)?！?〕假設(shè)后繼節(jié)點(diǎn)中某一個(gè)是目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解，成功退出。否則轉(zhuǎn)向〔2〕循環(huán)。2023/11/2136搜尋過程如下：OPLWVUTRQABCDGEFS廣度優(yōu)先搜尋示意圖2023/11/2137例1、示意圖節(jié)點(diǎn)的搜尋SL，O，PQ，R，TU，V，WA，B，C

SLOPQR廣度優(yōu)先搜尋過程中的OPEN表和CLOSED表OPENCLOSED2023/11/2138四、深度優(yōu)先搜尋 根本思想：從初始狀態(tài)S開頭，利用規(guī)章生成搜尋樹下一層任一個(gè)結(jié)點(diǎn)，檢查是否消失目標(biāo)狀態(tài)G，假設(shè)未消失，以此狀態(tài)利用規(guī)章生成再下一層任一個(gè)結(jié)點(diǎn)，再檢查是否為目標(biāo)節(jié)點(diǎn)G，假設(shè)未消失，連續(xù)以上操作過程，始終進(jìn)展到葉節(jié)點(diǎn)〔即不能再生成新狀態(tài)節(jié)點(diǎn)〕，當(dāng)它仍不是目標(biāo)狀態(tài)G時(shí)，回溯到上一層結(jié)果，取另一可能擴(kuò)展搜尋的分支。生成新狀態(tài)節(jié)點(diǎn)。假設(shè)仍不是目標(biāo)狀態(tài)，就按該分支始終擴(kuò)展到葉節(jié)點(diǎn)，假設(shè)仍不是目標(biāo)，承受一樣的回溯方法回退到上層節(jié)點(diǎn)，擴(kuò)展可能的分支生成新狀態(tài)，…，始終進(jìn)展下去，直到找到目標(biāo)狀態(tài)G為止。2023/11/2139搜尋過程如下：HALIFBCDEJGKS深度優(yōu)先搜尋示意圖2023/11/2140DFS算法 〔1〕把起始節(jié)點(diǎn)S線放到OPEN表中。〔2〕假設(shè)OPEN是空表，則失敗退出，否則連續(xù)。〔3〕從OPEN表中取最前面的節(jié)點(diǎn)node移到CLOSED表中?！?〕假設(shè)node節(jié)點(diǎn)是葉結(jié)點(diǎn)〔假設(shè)沒有后繼節(jié)點(diǎn)〕，則轉(zhuǎn)向〔2〕?！?〕擴(kuò)展node的后繼節(jié)點(diǎn)，產(chǎn)生全部后繼節(jié)點(diǎn)，并把他們放在OPEN表的前面。各后繼結(jié)點(diǎn)指針指向node節(jié)點(diǎn)。〔6〕假設(shè)后繼節(jié)點(diǎn)中某一個(gè)是目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解，成功退出。否則轉(zhuǎn)向〔2〕循環(huán)。2023/11/2141例、節(jié)點(diǎn)搜尋示意圖SA，H，R，F(xiàn)，C，DE

SABCDEOPENCLOSED2023/11/2142小結(jié)： 廣度和深度優(yōu)先搜尋有一個(gè)很大的缺陷,就是他們都是在一個(gè)給定的狀態(tài)空間中窮舉。這在狀態(tài)空間不大的狀況下是很適宜的算法，可是當(dāng)狀態(tài)空間特別大，且不猜測的狀況下就不行取了。他的效率實(shí)在太低，甚至不行完成。

所以，在這里再次強(qiáng)調(diào)“剪枝”！2023/11/2143HDOJ_1010TempteroftheBoneProblemDescriptionThedoggiefoundaboneinanancientmaze,whichfascinatedhimalot.However,whenhepickeditup,themazebegantoshake,andthedoggiecouldfeelthegroundsinking.Herealizedthatthebonewasatrap,andhetrieddesperatelytogetoutofthismaze.

ThemazewasarectanglewithsizesNbyM.Therewasadoorinthemaze.Atthebeginning,thedoorwasclosedanditwouldopenattheT-thsecondforashortperiodoftime(lessthan1second).ThereforethedoggiehadtoarriveatthedooronexactlytheT-thsecond.Ineverysecond,hecouldmoveoneblocktooneoftheupper,lower,leftandrightneighboringblocks.Onceheenteredablock,thegroundofthisblockwouldstarttosinkanddisappearinthenextsecond.Hecouldnotstayatoneblockformorethanonesecond,norcouldhemoveintoavisitedblock.Canthepoordoggiesurvive?Pleasehelphim.

2023/11/2144InputTheinputconsistsofmultipletestcases.ThefirstlineofeachtestcasecontainsthreeintegersN,M,andT(1<N,M<7;0<T<50),whichdenotethesizesofthemazeandthetimeatwhichthedoorwillopen,respectively.ThenextNlinesgivethemazelayout,witheachlinecontainingMcharacters.Acharacterisoneofthefollowing:

”X”:ablockofwall,whichthedoggiecannotenter;

”S”:thestartpointofthedoggie;

”D”:theD