算法合集之信息學(xué)競賽中搜索問題的常見優(yōu)化技巧(存儲(chǔ)版)
【正文】 合Ｓ或者 Snk 不存在與排序后的數(shù)列時(shí)，就回溯。 折疊法 把所有字符的 ASCII碼加起來。 廣度優(yōu)先搜索不能避免的是重復(fù)狀態(tài)，而用循環(huán)判斷重復(fù)是得不償失的，在狀態(tài)多的情況下，循環(huán)法甚至比深度優(yōu)先搜索的效率更低，而且低得多。只需 (2i1 and K)是否為 0就行了。 用 Hash[x1,y1,x2,y2,k]當(dāng) A到達(dá)坐標(biāo) (x1,y1)， B到達(dá)坐標(biāo) (x2,y2)，它們?cè)谕局械淖罱嚯x為 k時(shí)的最少時(shí)間。 小結(jié) Hash表是非常重要的廣度優(yōu)先搜索優(yōu)化方式之一，它能夠把搜索算法的效率從大指數(shù)級(jí)提高到小指數(shù)級(jí)、多項(xiàng)式級(jí)甚至常數(shù)級(jí)。 對(duì)于 Hash 表的構(gòu)造方法，可以采用 ELFhash 函數(shù)或者 SDBMhash(參見 05 年李羽修論文 )。 ４、第一個(gè)字符和加密字符 (’C’)之間必須是原文，同樣的，最后一個(gè)字符和最后一個(gè)加密字符 (’W’)之間也必須是原文。 參考文獻(xiàn)： [1] 劉汝佳，黃亮 . 《算法藝術(shù)與信息學(xué) 競賽》 (2022) [2] AngleForYou 《搜索算法的通用優(yōu)化方法》 [3] USACO 《解密牛語解題報(bào)告》 。 ２、已知密文中的每個(gè)字符的個(gè)數(shù)除了 ’C’,’’O,’W’外必定都是固定的，而且 ’C’,’O’,’W’三個(gè)字符的個(gè)數(shù)也必定在原始信息的基礎(chǔ)上增加了 (n47)/3 (n 為輸入信息長度 )。請(qǐng)你寫一個(gè)程序判斷它是不是這條信息經(jīng)過加密（或沒有加密）而得到的： Begin the Escape execution at the Break of Dawn 2022 年全國信息學(xué)冬令營講座 9 分析 基于密碼編譯規(guī)則，我們很容易地可以想出一個(gè)非常簡單的 dfs 方 法，當(dāng)然，那是明顯要超時(shí)的，而分析題目我們可以發(fā)現(xiàn)，題目要求的是一種得到信息的加密方法，也就是求的一種加密的路徑。完全可以在規(guī)定的時(shí)間內(nèi)得出結(jié)果。 分析： 本題是求路徑的一道題，所以是一道很明顯的廣度優(yōu)先搜索題目，題目的條件很多：首先是要 AB 都到達(dá)終點(diǎn)，然后是要路徑 中 AB 離得盡可能的遠(yuǎn)，同時(shí) AB 要盡快到達(dá)。 同時(shí)，在搜索中可以用位運(yùn)算來判斷某個(gè)房間的狀態(tài)，使得 Hash 表的填充和查找變得簡單。如果同時(shí) 有好幾條路線的話，請(qǐng)輸出最短的路線。 2022 年全國信息學(xué)冬令營講座 6 直接取余法 選取一個(gè)素?cái)?shù) M作為除數(shù)。當(dāng)我們已經(jīng)搜索出原數(shù)列的S1,S2…S i和 T1,T2…T j，此時(shí)對(duì)于正在搜索的數(shù) K,只可能有兩種存在的可能： Si+1和 Tj+1，分別依次搜索這兩個(gè)可能，即判斷 KSi 和 KTj 是否屬于已知集合Ｓ。 因?yàn)轭}目的約束條件集中在 Si 和 Ti 中，我們改變搜索的對(duì)象，不再搜索原數(shù)列中每個(gè)數(shù)的值，而是搜索給出的數(shù)中出現(xiàn)在 Si 或者 Ti 中的位置。 根據(jù)題目，我們得到的數(shù)據(jù)應(yīng)該是數(shù)列中的 S1,S2,S3?? Sn，以及 T1,T2,T3?? Tn。當(dāng)存在多組可能數(shù)列的時(shí)候求左邊的數(shù)最小的數(shù)列。 現(xiàn)給定 n的值，要求 m的最小值（并不要求輸出） ,及這個(gè) 數(shù)列的值 (可能 存在多個(gè)數(shù)列 ,只輸出任一個(gè)滿足條件的就可以了 )。對(duì)于約束滿 足問題，我們通?？梢詮乃阉鞯捻樞蚝退阉鞯膶?duì)象入手，進(jìn)而提高程序的效率。 一、深度優(yōu)先搜索的優(yōu)化技巧 我們?cè)谧鲱}的時(shí)候，經(jīng)常遇到這類題目 —— 給出約束條件，求一種滿足約束條件的方案，這類問題我們叫它“約束滿足”問題。 （ 1）搜索順序的選擇： 我們先來看一道比較簡單的題目： (zju
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1