Noip考前沖刺-搜索枚舉2

NOIP考前沖刺

--枚舉、搜索武森MAZE現(xiàn)在有一個(gè)6×6的迷宮。每個(gè)格子可能是空地或者是洞穴。每個(gè)格子的四周有可能是墻，如果一個(gè)格子的左邊有墻，那么它不能從這個(gè)格子往左面的格子走。迷宮中有且只有一個(gè)起點(diǎn)〔圓點(diǎn)〕和重點(diǎn)〔星型〕，起點(diǎn)和重點(diǎn)有可能是屬于同一個(gè)格子。現(xiàn)在可以往上〔U〕、下〔D〕、左〔L〕和右(R)四個(gè)方向走。先要求用最短的步數(shù)從起點(diǎn)走到終點(diǎn)〔當(dāng)走洞穴是，那么算失敗〕。解法BFS狀態(tài)表示DIST[X,Y]狀態(tài)轉(zhuǎn)移DIST[X,Y]=MIN{DIST[X+DIRX[I],Y+DIRY[I]]}+1轉(zhuǎn)移條件：轉(zhuǎn)到格子是否在范圍內(nèi)轉(zhuǎn)移格子是否有墻轉(zhuǎn)移格子是否似乎洞穴DOUBLE

MAZE現(xiàn)在有兩個(gè)6×6的迷宮每個(gè)格子可能是空地或者是洞穴。每個(gè)格子的四周有可能是墻，如果一個(gè)格子的左邊有墻，那么它不能從這個(gè)格子往左面的格子走。迷宮中有且只有一個(gè)起點(diǎn)〔圓點(diǎn)〕和重點(diǎn)〔星型〕，起點(diǎn)和重點(diǎn)有可能是屬于同一個(gè)格子?，F(xiàn)在可以往上〔U〕、下〔D〕、左〔L〕和右(R)四個(gè)方向走?，F(xiàn)在同時(shí)控制兩個(gè)格子的走法〔一個(gè)命令兩個(gè)迷宮同時(shí)走〕，如果有個(gè)一個(gè)迷宮走到了洞穴，那么失敗。如果有一個(gè)格子的要走的方向有墻，那么待在原位置的不動(dòng)。先要求用最短的步數(shù)〔步數(shù)相同要求字典序最小〕從起點(diǎn)走到終點(diǎn)〔當(dāng)走洞穴是，那么算失敗〕。解法BFS？解法BFS狀態(tài)表示DIST[X1,Y1,X2,Y2]狀態(tài)表示DIST[X1Y1,X2Y2]哪個(gè)比較好？解法BFS狀態(tài)表示DIST[X1Y1,X2Y2]狀態(tài)轉(zhuǎn)移DIST[X1Y1,X2Y2]

=MIN{DIST[X1Y1+WAYX[I],X2Y2+WAYY[I]]}+1DIST[X1Y1+WAYX[I],X2Y2+WAYY[I]]表示

能到達(dá)[X1Y1,X2Y2]的格子轉(zhuǎn)移條件：轉(zhuǎn)到格子是否在范圍內(nèi)轉(zhuǎn)移格子是否有墻轉(zhuǎn)移格子是否似乎洞穴注意那些有一個(gè)格子的路上有墻，留在原地的格解法求出了最短距離。怎么求得字典序最小的方案？方法1每次按字典序有小到大的走路方式〔D,L,R,U〕枚舉走路的格子，判斷DIST’是否等于當(dāng)前格子的DIST-1.方法特點(diǎn)優(yōu)點(diǎn)：容易想到，簡(jiǎn)單易寫不容犯錯(cuò).缺點(diǎn)：算法復(fù)雜度高，方法2根據(jù)上面的方法，我們易知枚舉是否要走路的格子，如果是，那么DIST’是否等于當(dāng)前格子的DIST-1.那個(gè)能否從終點(diǎn)到起點(diǎn)進(jìn)行BFS,直接計(jì)算出路徑最短并且字典序最小的方案？算法實(shí)現(xiàn)本卷須知：在倒向BFS的時(shí)候，我們要注意的是現(xiàn)在的BFS是對(duì)原本實(shí)踐的回放，和原本的BFS方式不同。對(duì)于一個(gè)左邊有墻格子，如果他在原本的BFS的過程當(dāng)中是向左走的，那么我們現(xiàn)在就要向右走，這點(diǎn)毋庸置疑！但是，他有可能是向左走的時(shí)候，發(fā)現(xiàn)左邊有墻而停留在原味的結(jié)果，所以對(duì)于這種情況，我們要考慮兩種不同的情況，當(dāng)然如果兩個(gè)迷宮同時(shí)出像這種情況，那么要考慮2×2=4種情況。方法特點(diǎn)優(yōu)點(diǎn)：便于根據(jù)題目要求，得到最短且字典序最小的解。時(shí)間復(fù)雜度低缺點(diǎn)：細(xì)節(jié)考慮較多編程復(fù)雜度高不易實(shí)現(xiàn)考點(diǎn)選手的正向思維和逆向思維思維的嚴(yán)謹(jǐn)性智慧珠游戲智慧珠游戲拼盤由一個(gè)三角形盤件和12個(gè)形態(tài)各異的零件組成。12個(gè)零件按珠子數(shù)分3大類第1大類：有三個(gè)珠子符號(hào)為A第2大類：有四個(gè)珠子符號(hào)為B符號(hào)為C符號(hào)為D第3大類：有五個(gè)珠子符號(hào)為E 符號(hào)為I符號(hào)為F 符號(hào)為J符號(hào)為G 符號(hào)為K符號(hào)為H 符號(hào)為L(zhǎng)舉例說明字符化B

BK

BKK

BJKK

JJJDD

GJGDDC

GGGCCCI

EEEHHIIA

ELHHHIAAF

ELLLLIFFFF條件&要求對(duì)于由珠子構(gòu)成的零件，可以放到盤件的任一位置，條件是能有地方放，且尺寸適宜，所有的零件都允許旋轉(zhuǎn)(0o、90o、180o、270o)和翻轉(zhuǎn)(水平、豎直)。

現(xiàn)給出一個(gè)盤件的初始布局，求一種可行的智慧珠擺放方案，使所有的零件都能放進(jìn)盤件中。樣例輸入文件一共有10行，第i行有i個(gè)字符。如果第i行的第j個(gè)字符是字母”A”至”L”中的一個(gè)，那么表示第i行第j列的格子上已經(jīng)放了零件，零件的編號(hào)為對(duì)應(yīng)的字母。如果第i行的第j個(gè)字符是”.”，那么表示第i行第j列的格子上沒有放零件。輸入保證預(yù)放的零件已擺放在盤件中。。

。。

。。。

。。。。

。。。。。

。。。。。C

。。。CCC。

EEEHH。。。

E。HHH。。。。

E。。。。。。。。。輸出樣例如果能找到解，輸出10行，為放完全部12個(gè)零件后的布局。其中，第i行應(yīng)包含i個(gè)字符，第i行的第j個(gè)字符表示第i行第j列的格子上放的是哪個(gè)零件。如果無(wú)解，輸出單獨(dú)的一個(gè)字符串”Nosolution”(不要引號(hào)，請(qǐng)注意大小寫)。所有的數(shù)據(jù)保證最多只有一組解。B

BK

BKK

BJKK

JJJDD

GJGDDC

GGGCCCI

EEEHHIIA

ELHHHIAAF

ELLLLIFFFF解法BFSorDFS解法BFS不好記錄狀態(tài)，解最多為一個(gè)，不存在深度較淺的解DFSNOSOLUTION輸入數(shù)據(jù)中“.”的個(gè)數(shù)與實(shí)際需要填的形狀的柱子總數(shù)不符。。。預(yù)處理對(duì)于每個(gè)珠子，將其的構(gòu)造形式量化，便于搜索時(shí)使用方法1最簡(jiǎn)單的思路從第一行的第一個(gè)位置開始搜索，嘗試將當(dāng)前情況下的沒有放過的珠子，放在個(gè)這個(gè)位置上〔這個(gè)位置為珠子的某一個(gè)角而不是其中任意一個(gè)點(diǎn)〕依次搜索每一個(gè)沒有放東西的位置，直至最終沒有格子沒有放下并且所有的珠子都已經(jīng)放完了如果滿足要求，那么輸出解如果不滿足要求，那么屬于Nosolution方法特點(diǎn)優(yōu)點(diǎn)：思路簡(jiǎn)單，清晰代碼易寫缺點(diǎn)：根本沒有優(yōu)化的可能性時(shí)間復(fù)雜度較高方法2通過觀察題目中的不同珠子我們發(fā)現(xiàn)，對(duì)有有些珠子，如：G,J,K等珠子，由于形狀比較特殊，所以可能與其有連接的珠子的形式比較單一，可以預(yù)處理出來，在搜索的時(shí)候，可以從這里入手。觀察輸入文件為一個(gè)三角形，那么對(duì)于斜邊上的位置，會(huì)造成有一些格子不能被放置，這一點(diǎn)也可以預(yù)先處理出來，可以有效地進(jìn)行優(yōu)化算法特點(diǎn)優(yōu)點(diǎn)：改變搜索的順序，可以有效的減少搜索的次數(shù)對(duì)于一些特殊的情況，事先預(yù)處理出來，可以有效的減枝時(shí)間復(fù)雜度較方法1有一定的優(yōu)勢(shì)缺點(diǎn)：算法要預(yù)處理的內(nèi)容有些復(fù)雜編程復(fù)雜度較高BFSORDFS探險(xiǎn)隊(duì)得到了一張古老藏寶的地圖，圖中包含n神秘的地點(diǎn)，并且知道這些神秘的地點(diǎn)之間是有一些隧道連接的，并且探險(xiǎn)隊(duì)知道藏寶圖中包含了m條隧道，〔m<n〕，經(jīng)過探險(xiǎn)的觀察這個(gè)藏寶圖中不包含什么回路〔即任意兩點(diǎn)之間最多存在一條路徑使其相連〕，藏寶圖中當(dāng)中可能包含很多區(qū)域，任意兩個(gè)區(qū)域是不相通的，現(xiàn)在藏寶圖和探險(xiǎn)隊(duì)走過藏寶圖中的某些神秘的地點(diǎn)，又知道探險(xiǎn)隊(duì)只能采取深度優(yōu)先搜索或者寬度優(yōu)先搜索的方式來對(duì)藏寶地點(diǎn)進(jìn)行探險(xiǎn)，請(qǐng)問探險(xiǎn)隊(duì)可能使用哪種方式進(jìn)行探險(xiǎn)的？輸入數(shù)據(jù)第一行兩個(gè)數(shù)字n、m和k表示藏寶圖中有多少個(gè)神秘地點(diǎn)由1到n表示這個(gè)n個(gè)神秘地點(diǎn)和藏寶圖中的道路和探險(xiǎn)隊(duì)已經(jīng)探過的神秘地點(diǎn)數(shù)目。接下來的m行每行兩個(gè)數(shù)ai,bi表示神秘地點(diǎn)ai和神秘地點(diǎn)bi有道路相連。在接下來的k行每行一個(gè)數(shù)字表示那些神秘地點(diǎn)被探過。輸出數(shù)據(jù)輸出有種情況DFS 表示是深度優(yōu)先搜索的BFS 表示是寬度優(yōu)先搜索的BOTH 表示兩種情況都有可能NEITHER 表示兩種情況都不可能題目模型抽象給定一個(gè)無(wú)向圖，并且其中一些點(diǎn)被遍歷，現(xiàn)在詢問你這些點(diǎn)是怎么遍歷的？思路首先對(duì)于圖進(jìn)行遍歷。由于不同的聯(lián)通分支之間互不影響所以進(jìn)行處理。判斷是哪種方法？思路什么情況下無(wú)解？

如果有兩個(gè)或兩個(gè)以上聯(lián)通分支沒有被完全遍歷到對(duì)于這種情況是不不可能存在某一種算法，能便利成那個(gè)樣子的。

所以Nosolution思路那么這道題目，就簡(jiǎn)化成了對(duì)以某一聯(lián)通分支進(jìn)行檢查，判斷其遍歷方式。思路BFS: 一直對(duì)于某一聯(lián)通分支〔題目中已經(jīng)給出圖中沒有環(huán)〕，所以這是一棵樹，如果我們確定了這棵樹的樹根，那么就很好判斷這棵樹是否是用BFS遍歷得了。 怎么求得這棵樹的樹根呢？思路不妨枚舉樹根易知寬度優(yōu)先搜索的最深深度與最淺深度相差為一那么對(duì)于圖中的各個(gè)不同的遍歷路徑，我們都可以計(jì)算深度，從而判斷，是否為BFS思路DFS: 白板聰明的火車司機(jī)一輛有n個(gè)門的火車駛進(jìn)了一座長(zhǎng)len的火車站，火車的n個(gè)門在火車上的位置分別為di(1≤i≤n，且d1=0，di≤len)?；疖囌居衜個(gè)乘客，第i個(gè)乘客位于火車站的pi(pi≤len)位置，一個(gè)乘客會(huì)選擇離他最近的門上車?；疖嚨拿總€(gè)門都必須停在火車站內(nèi)，為了讓所有乘客上車時(shí)走的距離和最長(zhǎng)，火車司機(jī)應(yīng)該讓火車的第一個(gè)門停在火車站的什么位置，最長(zhǎng)距離和又是多少。輸入樣例第一行一個(gè)數(shù)len第二行一個(gè)數(shù)m第三行m個(gè)遞增的非負(fù)整數(shù)p1，p2，……pm第四行一個(gè)數(shù)n第五行n-1個(gè)遞增的正整數(shù)d2，d3，……dn45012344123輸出數(shù)據(jù)一行兩個(gè)數(shù)分別表示最優(yōu)位置和最長(zhǎng)距離和，答案保存3位小數(shù)0.5002.500思路枚舉枚舉什么？車停靠的位置？？？思路最簡(jiǎn)單的方法是以0.001為步長(zhǎng)枚舉時(shí)間復(fù)雜度為O(1000l(n+m))優(yōu)化策略用反證法容易證明最優(yōu)情況下至少有一個(gè)人位于兩個(gè)門的中點(diǎn)，以此為根據(jù)可將步長(zhǎng)調(diào)整為0.5再枚舉復(fù)雜度為O(l(n+m))誤差曲線小紅是個(gè)聰明的女孩，最近沉迷于機(jī)器學(xué)習(xí)。她非常喜歡的方法稱為線性判別分析，其中有許多有趣的性質(zhì)。為了檢驗(yàn)該算法的效率，她收集很多的數(shù)據(jù)集。更重要的是，每個(gè)數(shù)據(jù)分為兩局部：訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)。她得到的訓(xùn)練數(shù)據(jù)模型的參數(shù)和測(cè)試的測(cè)試數(shù)據(jù)模型。令她驚訝的是，她發(fā)現(xiàn)每個(gè)數(shù)據(jù)集的測(cè)試誤差曲線只是一個(gè)拋物曲線。一個(gè)拋物曲線對(duì)應(yīng)一個(gè)二次函數(shù)。在數(shù)學(xué)中，二次函數(shù)的形式是多項(xiàng)式函數(shù)f(x)=ax^2+bx+c.如果只有一個(gè)測(cè)試誤差曲線的最小誤差值很容易計(jì)算。然而，有幾個(gè)數(shù)據(jù)集，這意味著小紅將獲得許多拋物曲線。小紅希望得到，使所有數(shù)據(jù)集上的最正確性能優(yōu)化的參數(shù)。所以她應(yīng)該考慮到，即所有誤差曲線，她要面對(duì)許多二次函數(shù)，并作出新的錯(cuò)誤定義，將其總誤差。現(xiàn)在，她著重于以下新的功能的最小二次其中涉及到多個(gè)職能。新的函數(shù)F〔x〕的定義如下： F(x)=max(Si(x)),i=1...n.,xis[0,1000].Si(x)isaquadricfunction現(xiàn)在小紅想要知道函數(shù)F〔x〕的最小值是多少？輸入數(shù)據(jù)輸入數(shù)據(jù)包含兩局部。第一局部是一個(gè)整數(shù)n表示有多少個(gè)測(cè)試誤差曲線第二局部由n行組成，每行有三個(gè)數(shù)字a，b，c，表示測(cè)試誤差曲線的三個(gè)參數(shù)a(0≤a≤100),b(|b|≤5000),c(|c|≤5000)。2200

2-42輸出數(shù)據(jù)輸出小紅想要的最小值0.5000思路對(duì)于這道題目，我們可以看到這個(gè)曲線有一下特殊情況：直線頂點(diǎn)這些情況要特殊處理。方法1由于我們要尋找一個(gè)點(diǎn)，使得函數(shù)F〔x〕的最小，我們最初的想法和上一道題目一樣，能不能枚舉我們選取的那個(gè)點(diǎn)，然后以此計(jì)算這個(gè)點(diǎn)上的函數(shù)F〔x〕的值。最終得到答案。算法特點(diǎn)有點(diǎn)：思路簡(jiǎn)單，通俗易懂缺點(diǎn)：算法時(shí)間復(fù)雜度很高

方法2既然枚舉選取的值不行，那么這道題是不是不是枚舉呢？枚舉答案？方法2如果枚舉答案，我們就要怎么計(jì)算這個(gè)答案，能不能在答案范圍內(nèi)找到呢？見白板有趣的樓道小明在漆黑的光棍節(jié)晚上還要悲催的去上一節(jié)政治課，他心里越想越