【正文】 二、廣度優(yōu)先搜索的優(yōu)化技巧 相對于深度優(yōu)先搜索的另外一類 題目 —— 給出起始和目標(biāo)狀態(tài)，以及狀態(tài)轉(zhuǎn)移的規(guī)則，要求找到一條到達目標(biāo)狀態(tài)的的路徑或者方法。 那么當(dāng)我們?nèi)我鈴囊阎臄?shù)據(jù)中取出兩個數(shù)的時候，只會出現(xiàn)兩種情況： 兩個數(shù)同屬于 Si,或者 Ti 兩數(shù)分別屬于 Ti 和 Si。也許大家會覺得這種單一的運用搜索順序來優(yōu)化程序的方法很普通，但是這種看似簡單的方法在考試中出現(xiàn)得也不少，例如 IOI2022 中的 BLOCK，只要將木塊從大到小經(jīng)過旋轉(zhuǎn)和反轉(zhuǎn)后，依次放入進行搜索，對于比賽中的數(shù)據(jù)就可以得到滿分。2022 年全國信息學(xué)冬令營講座 1 信息學(xué)競賽中搜索問題的常見優(yōu)化技巧 重慶一中 黃曉愉 【摘要】 結(jié)合例題分析歸納了信息學(xué)競賽中解決搜索問題所常用的思考方法與解題方法，從深度優(yōu)先搜索和廣度優(yōu)先搜索兩個方面探討了提高程序效率的適用技巧。 當(dāng)然，這道題還有很大的優(yōu)化余地，但是搜索順序這種思想在搜索的題目中是廣泛運用的。同樣的，在搜索的過程中最大化這些約束條件是提高程序效率的關(guān)鍵。 這樣得到的算法在最壞情況下擴展的節(jié)點為 21000(實際中遠遠小于這個數(shù) )，并且由于在搜索過程中充分利用了題目約束條件，其程序運行結(jié)果如下： 在這道題目中，原始的搜索方法搜索量巨大，我們通過分析，選擇適當(dāng)?shù)乃阉鲗ο?，在搜索量減少的同時充分利用了題目的約束條件，成為了程序的一個有利的剪枝，使題目得到較好的解決。 而題目的難點在于 Hash 表的構(gòu)造，經(jīng)過分析發(fā)現(xiàn)，對于狀態(tài)有影響的便是房間內(nèi)電燈的開關(guān)與否，還有當(dāng)時所在的房間。 這兩種方法構(gòu)造方法共同的特點是 Hash 表中儲存了大量的信息，并且在編程實現(xiàn)中比較困難。這里跳過。 小結(jié) 剪枝是所有搜索中必不可少的一個重點，充分的利用題目的特性進行剪枝可以2022 年全國信息學(xué)冬令營講座 10 很大程度的提高程序的效率。一天夜里， John 的牛們收到了一條經(jīng)過多次加密的信息。如圖為 N=10 時的一種情況?？墒呛懿恍?，他十分怕黑，因此他不會走入任何關(guān)著燈的房間，于是請你幫他找出一條路使他既能回到臥室又能關(guān)閉除臥室以外的所有燈。由之前的分析已經(jīng)知道，每個數(shù)只可能屬于 Si 和 Ti 中。讓我們換個角 度對這個問題進行思考： 搜索方法 B： 回過頭來看看題目提供給我們的約束條件，我們用 Si 表示前 I項的和，用 Ti 表示后 I項的和。 （ 1）搜索順序的選擇： 我們先來看一道比較簡單的題目： (zju1937) 已知一個數(shù)列 a0,a1......am 其中 2022 年全國信息學(xué)冬令營講座 2 a0 = 1 am = n a0 a1 a2 ... am1 am 對于每個 k(1=k=m),ak=ai+aj (0 = i, j = k1)，這里 i與 j可以相等 。對于約束滿 足問題，我們通?？梢詮乃阉鞯捻樞蚝退阉鞯膶ο笕胧郑M而提高程序的效率。當(dāng)存在多組可能數(shù)列的時候求左邊的數(shù)最小的數(shù)列。 因為題目的約束條件集中在 Si 和 Ti 中，我們改變搜索的對象，不再搜索原數(shù)列中每個數(shù)的值，而是搜索給出的數(shù)中出現(xiàn)在 Si 或者 Ti 中的位置。 2022 年全國信息學(xué)冬令營講座 6 直接取余法 選取一個素數(shù) M作為除數(shù)。 同時，在搜索中可以用位運算來判斷某個房間的狀態(tài)，使得 Hash 表的填充和查找變得簡單。完全可以在規(guī)定的時間內(nèi)得出結(jié)果。 ２、已知密文中的每個字符的個數(shù)除了 ’C’,’’O,’W’外必定都是固定的，而