NOIP考前沖刺

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

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

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

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

BK

BKK

BJKK

JJJDD

GJGDDC

GGGCCCI

EEEHHIIA

ELHHHIAAF

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

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

。。

。。。

。。。。

。。。。。

。。。。。C

。。。CCC。

EEEHH。。。

E。HHH。。。。

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

BK

BKK

BJKK

JJJDD

GJGDDC

GGGCCCI

EEEHHIIA

ELHHHIAAF

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

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

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

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

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