NOIP普及講座2-搜索應(yīng)用舉例.pptx

搜索應(yīng)用舉例 泰州市第二中學(xué)附屬初中謝志鋒 例1 走迷宮 maze in out pas cpp 問題描述 一個迷宮由R行C列格子組成 有的格子里有障礙物 不能走 有的格子是空地 可以走 給定一個迷宮 求從左上角走到右下角最少需要走多少步 數(shù)據(jù)保證一定能走到 只能在水平方向或垂直方向走 不能斜著走 輸入格式 第一行是兩個整數(shù) 和 1 R C 40 代表迷宮的長和寬 例1 走迷宮 maze in out pas cpp 接下來是 行 每行 個字符 代表整個迷宮 空地格子用 表示 有障礙物的格子用 表示 迷宮左上角和右下角都是 輸出格式 輸出從左上角走到右下角至少要經(jīng)過多少步 即至少要經(jīng)過多少個空地格子 計算步數(shù)要包括起點和終點 例1 走迷宮 maze in out pas cpp 輸入樣例 55 輸出樣例 9 例1 走迷宮 maze in out pas cpp 狀態(tài)分析 1 初始狀態(tài)2 目標(biāo)狀態(tài)3 狀態(tài)轉(zhuǎn)移 例1 走迷宮 maze in out pas cpp 實現(xiàn) 1 深搜2 寬搜 例1 走迷宮 maze in out pas cpp 提高 雙向?qū)捤?例2 數(shù)字游戲 sudoku in out pas cpp 問題描述 這天Kendy路過KFC 看到KFC的櫥窗上貼著大幅的宣傳海報 海報上說 如果能在規(guī)定的時間內(nèi)解決他們提出的問題 就可以獲得價值100元的KFC最新款套餐 Kendy當(dāng)然不想放過這樣的機會 他發(fā)現(xiàn)題目是這樣的 給你一個N N的表格 3 N 10 在表格中事先已經(jīng)填入了一部分的數(shù)字 現(xiàn)在請你的表格中空余的格子里填入1 N范圍內(nèi)的數(shù)字 使得整個表格的每一行和每一列都不存在重復(fù)的數(shù)字 例2 數(shù)字游戲 sudoku in out pas cpp 格的每一行和每一列都不存在重復(fù)的數(shù)字 當(dāng)然 為了保證公平 所有人拿到的表格都是隨機的且標(biāo)注了時間 這樣Kendy就不可能把題目帶回去慢慢研究了 因此他想請你幫忙以便在規(guī)定時間內(nèi)能解決這個問題 保證都有解 例2 數(shù)字游戲 sudoku in out pas cpp 輸入輸出樣例 例2 數(shù)字游戲 sudoku in out pas cpp 樣例說明 本題共有兩種填法 取其中第一行數(shù)值較小的填法 例2 數(shù)字游戲 sudoku in out pas cpp 狀態(tài)分析 1 初始狀態(tài)2 目標(biāo)狀態(tài)3 狀態(tài)轉(zhuǎn)移 例2 數(shù)字游戲 sudoku in out pas cpp 實現(xiàn) 深搜 例3 砝碼 scales in out pas cpp 問題描述 已知一個天平 有N 1 N 1000 個已知質(zhì)量的砝碼 所有砝碼質(zhì)量的數(shù)值都在31位二進制內(nèi) 所稱物體在天平的某一邊 天平另一邊加砝碼 直到天平平衡 于是此時砝碼的總質(zhì)量就是物體的質(zhì)量 物體和砝碼不能放到同一邊 天平能承受的物體的質(zhì)量不是無限的 當(dāng)天平某一邊物體的質(zhì)量大于C 1 C 2 30 時 天平就會被損壞 例3 砝碼 scales in out pas cpp 砝碼按照它們質(zhì)量的大小被排成一行 并且 這一行中從第3個砝碼開始 每個砝碼的質(zhì)量至少等于前面兩個砝碼 也就是質(zhì)量比它小的砝碼中質(zhì)量最大的兩個 的質(zhì)量的和 用這些砝碼以及這架天平 能稱出的質(zhì)量最大是多少 由于天平的最大承重能力為C 他不能把所有砝碼都放到天平上 例3 砝碼 scales in out pas cpp 現(xiàn)在告訴你每個砝碼的質(zhì)量 以及天平能承受的最大質(zhì)量 你的任務(wù)是選出一些砝碼 使它們的質(zhì)量和在不壓壞天平的前提下是所有組合中最大的 輸入格式 第1行 兩個用空格隔開的正整數(shù) N和C 第2 N 1行 每一行僅包含一個正整數(shù) 即某個砝碼的質(zhì)量 保證這些砝碼的質(zhì)量是一個不下降序列 例3 砝碼 scales in out pas cpp 輸出格式 1行 一個正整數(shù) 表示用所給的砝碼能稱出的不壓壞天平的最大質(zhì)量 輸入輸出樣例 例3 砝碼 scales in out pas cpp 問題分析 1 數(shù)據(jù)規(guī)模 2 預(yù)處理3 搜索方向4 剪枝 例4 Noip2014尋找道路 road in out pas cpp 問題描述 在有向圖G中 每條邊的長度均為1 現(xiàn)給定起點和終點 請你在圖中找一條從起點到終點的路徑 該路徑滿足以下條件 1 路徑上的所有點的出邊所指向的點都直接或間接與終點連通 2 在滿足條件1的情況下使路徑最短 注意 圖G中可能存在重邊和自環(huán) 題目保證終點沒有出邊 例4 Noip2014尋找道路 road in out pas cpp 請你輸出符合條件的路徑的長度 輸入格式 第一行有兩個用一個空格隔開的整數(shù)n和m 表示圖有n個點和m條邊 接下來的m行每行2個整數(shù)x y 之間用一個空格隔開 表示有一條邊從點x指向點y 最后一行有兩個用一個空格隔開的整數(shù)s t 表示起點為s 終點為t 例4 Noip2014尋找道路 road in out pas cpp 輸出格式 輸出只有一行 包含一個整數(shù) 表示滿足題目描述的最短路徑的長度 如果這樣的路徑不存在 輸出 1 例4 Noip2014尋找道路 road in out pas cpp 數(shù)據(jù)說明 對于30 的數(shù)據(jù) 0 n 10 0 m 20 對于60 的數(shù)據(jù) 0 n 100 0 m 2000 對于100 的數(shù)據(jù) 0 n 10 000 0 m 200 000 0 x y s t n x t 例5 模板 template in out pas cpp 問題描述 在魔方風(fēng)靡全球之后不久 Rubik先生發(fā)明了它的簡化版 魔板 魔板由8個同樣大小的方塊組成 每個方塊顏色均不相同 可用數(shù)字1 8分別表示 任一時刻魔板的狀態(tài)可用方塊的顏色序列表示 從魔板的左上角開始 按順時針方向依次寫下各方塊的顏色代號 所得到的數(shù)字序列即可表示此時魔板的狀態(tài) 例如 序列 1 2 3 4 5 6 7 8 表示魔板狀態(tài)為 例5 模板 template in out pas cpp 對于魔板 可施加三種不同的操作 具體操作方法如下 A 上下兩行互換 如上圖可變換為狀態(tài)87654321B 每行同時循環(huán)右移一格 如上圖可變換為41236785C 中間4個方塊順時針旋轉(zhuǎn)一格 如上圖可變換為17245368 例5 模板 template in out pas cpp 給你魔板的初始狀態(tài)與目標(biāo)狀態(tài) 請給出由初態(tài)到目態(tài)變換數(shù)最少的變換步驟 若有多種變換方案則取字典序最小的那種 輸入格式 測試數(shù)據(jù)包括兩行 分別代表魔板的初始狀態(tài)與終止?fàn)顟B(tài) 輸出格式 輸出滿足題意的變換步驟 例5 模板 template in out pas cpp 輸入輸出樣例 例5 模板 template in out pas cpp 康托展開 1 2 3 4 n 表示1 2 3 n的排列如 1 2 3 按從小到大排列一共6個 123132213231312321 代表的數(shù)字123456也就是把10進制數(shù)與一個排列對應(yīng)起來 他們間的對應(yīng)關(guān)系可由康托展開來找到 例5 模板 template in out pas cpp 如我想知道321是 1 2 3 中第幾個小的數(shù)可以這樣考慮 第一位是3 當(dāng)?shù)谝晃坏臄?shù)小于3時 那排列數(shù)小于321如123 213 小于3的數(shù)有1 2 所以有2 2 個 再看小于第二位2的 小于2的數(shù)只有一個就是1 所以有1 1 1所以小于321的 1 2 3 排列數(shù)有2 2 1 1 5個 所以321是第6個小的數(shù) 2 2 1 1 0 0 就是康托展開 例5 模板 template in out pas cpp 再舉個例子 1324是 1 2 3 4 排列數(shù)中第幾個大的數(shù) 第一位是1小于1的數(shù)沒有 是0個0 3 第二位是3小于3的數(shù)有1和2 但1已經(jīng)在第一位了 所以只有一個數(shù)2 1 2 第三位是2小于2的數(shù)是1 但1在第一位 所以有0個數(shù)0 1 所以比1324小的排列有0 3 1 2 0 1 2個 1324是第三個小數(shù) 例5 模板 template in out pas cpp 康托逆展開 1 2 3 4 5 的全排列 并且已經(jīng)從小到大排序完畢 1 找出第96個數(shù)首先用96 1得到95用95去除4 得到3余23有3個數(shù)比它小的數(shù)是4所以第一位是4用23去除3 得到3余5 例5 模板 template in out pas cpp 有3個數(shù)比它小的數(shù)是4但4已經(jīng)在之前出現(xiàn)過了所以第二位是5 4在之前出現(xiàn)過 所以實際比5小的數(shù)是3個 用5去除2 得到2余1有2個數(shù)比它小的數(shù)是3 第三位是3用1去除1 得到1余0有1個數(shù)比它小的數(shù)是2 第二位是2最后一個數(shù)只能是1所以這個數(shù)是45321 例5 模板 template in out pas cpp 2 找出第16個數(shù)首先用16 1得到15用15去除4 得到0余15用15去除3 得到2余3用3去除2 得到1余1用1去除1 得到1余0有0個數(shù)比它小的數(shù)是1有2個數(shù)比它小的數(shù)是3但由于1已經(jīng)在之前出現(xiàn)過了