目錄

* dfs/bfs

* 動(dòng)態(tài)規(guī)劃

* 位運(yùn)算

* 日期枚舉

* 最后一點(diǎn): C/C++的對(duì)拍小技巧

dfs/bfs

dfs/bfs為最常用的搜索算法, 需要找好解空間的狀態(tài)和終止條件。

例題:?小朋友崇拜圈

班里?N?個(gè)小朋友，每個(gè)人都有自己最崇拜的一個(gè)小朋友（也可以是自己）。

在一個(gè)游戲中，需要小朋友坐一個(gè)圈，每個(gè)小朋友都有自己最崇拜的小朋友在他的右手邊。

求滿足條件的圈最大多少人？

小朋友編號(hào)為?1,2,3，?N。

思路: 我們使用 dfs 從每一個(gè)小朋友 i 開(kāi)始搜索, 看看從 i 出發(fā)最大的圈為多少, 全局定義一個(gè)變量然后更新最大的圈長(zhǎng)。

這題有意思的是dfs邊界條件，當(dāng)我們記錄的圈長(zhǎng) > N時(shí)說(shuō)明從 i 出發(fā)得不到一個(gè)圈, 因?yàn)闃O端條件下最大得圈只能是 N。

例題2.分考場(chǎng)

n?個(gè)人參加某項(xiàng)特殊考試。

為了公平，要求任何兩個(gè)認(rèn)識(shí)的人不能分在同一個(gè)考場(chǎng)。

求最少需要分幾個(gè)考場(chǎng)才能滿足條件。

分考場(chǎng)有兩種狀態(tài), 一種是新開(kāi)一個(gè)考場(chǎng)，另一種是往之前得考場(chǎng)里面安排座位, 接著通過(guò) dfs搜索回溯即可:

例題3.氣候變暖

dfs版本:

bfs版本:

動(dòng)態(tài)規(guī)劃

1. 0-1背包問(wèn)題

根據(jù)閆式DP分析法, 我們?cè)O(shè)狀態(tài)f[i][j]表示的子集為在前 i 個(gè)物品中選取不超過(guò)重量?j 的最大價(jià)值。

我們考慮最后一組情況 f[i][j], 對(duì)于第 i 件物品, 我們只有選和不選兩種情況，于是我們的狀態(tài)轉(zhuǎn)移方程為:?

f[i][j] = max(f[i-1][j], f[i-1][j-w[i]+v[i])

2. 完全背包問(wèn)題

狀態(tài)表示與 01背包問(wèn)題是一樣的，我們對(duì)第 i 件物品有 k 種選取情況(可以選 0, 1, ... , k件), 那么狀態(tài)轉(zhuǎn)移方程為:

f[i][j] = max(, f[i - 1][j - k * w[i]] + v[i], ...)?

來(lái)個(gè)枚舉可能的 k 值的樸素寫(xiě)法, 時(shí)間復(fù)雜度: O(n^3):

f[i][j] = max(,?f[i - 1][j - k?*?w[i]]?+ v[i], ...)?

遞歸地根據(jù)定義:

f[i][j - w[i]] =?max(f[i - 1][j - w[i]], f[i - 1][j - 2w[i]] + v[i], ...)

那么我們就可以把狀態(tài)轉(zhuǎn)移方程化簡(jiǎn)為:

f[i][j] = max(f[i - 1][j], f[i][j - w[i]] + v[i])

于是我們可以將時(shí)間復(fù)雜度降低到 O(n^2):

1.例題:砝碼稱重

先來(lái)個(gè) dfs 版本:

dp解法, 我們?cè)O(shè)狀態(tài)dp[i][j] 為在前 i 個(gè)砝碼中是否能稱出重量 j, 那么在第 i 個(gè)狀態(tài)中有放左邊，不選，放右邊 3 種情況, 那么狀態(tài)轉(zhuǎn)移方程為:

f[i][j] = max(f[i - 1][j], f[i - 1][abs(j - a[i])], f[i - 1][j + a[i]])

3. 線性dp問(wèn)題

這個(gè)沒(méi)有固定的模型, 只能依靠數(shù)學(xué)關(guān)系現(xiàn)場(chǎng)推導(dǎo).不過(guò)狀態(tài)的設(shè)置也是個(gè)技術(shù)活，而且需要靠大量的經(jīng)驗(yàn)(希望可以靈光一現(xiàn)吧。。。）

位運(yùn)算

大寫(xiě)轉(zhuǎn)小寫(xiě), 小寫(xiě)轉(zhuǎn)大寫(xiě):

二進(jìn)制的狀態(tài)壓縮:

我們要優(yōu)化空間復(fù)雜度時(shí), 我們可以一個(gè)二進(jìn)制整數(shù)來(lái)表示集合中的狀態(tài)(前提是集合中每個(gè)元素只有0和1兩種情況)

取出 n 在二進(jìn)制表示下的第k位 (n >> k) & 1

把整數(shù)n在二進(jìn)制表現(xiàn)下的第k位取反 n xor (1 << k)

把整數(shù)n在二進(jìn)制表現(xiàn)下的第k位賦值1 n | (1 << k)

把整數(shù)n在二進(jìn)制表現(xiàn)下的第k位賦值0 n & (~(1 << k))

日期枚舉

最不容易錯(cuò)的方法是一天一天地枚舉，同時(shí)注意日期合法性。

C/C++的對(duì)拍小技巧

當(dāng)你想到個(gè)優(yōu)化方法來(lái)優(yōu)化暴力法時(shí), 就要確定好這個(gè)方法得出來(lái)的結(jié)果是和暴力法一樣的。下面就來(lái)介紹一個(gè)對(duì)拍的方法來(lái)檢驗(yàn)?zāi)愕某绦颉?/p>

對(duì)拍其實(shí)很簡(jiǎn)單，改改源程序然后用 dos 命令就可以了, 下面介紹在 windows 下如何實(shí)現(xiàn)對(duì)拍:

./a1.exe > A.txt? 指的是運(yùn)行 a.exe，把結(jié)果輸出（>）到 A.txt 中

./a2.exe > B.txt

A.exe <?in.txt > C.txt?指的是運(yùn)行?A.exe，從 in.txt 中讀入（<）數(shù)據(jù)，把結(jié)果輸出（>）到 C.txt

然后使用 fc 命令就可以顯示出兩個(gè)文件的差異了:

fc A.txt B.txt

不過(guò)我們要改寫(xiě)一下源程序(最后備份一下), 改成像 codeforces 那樣?改成批量循環(huán)就可以了, 然后構(gòu)造一個(gè) in.txt 文件, 或者隨機(jī)生成輸入值放入in.txt里面。

當(dāng)然, 前提是自信--你的暴力代碼是正確的。。。

最后, 沒(méi)思路可以去去洗手間(不是去作弊哦)，是因?yàn)榭梢宰邉?dòng)一下, 畢竟比賽過(guò)程長(zhǎng)達(dá)個(gè)4小時(shí)的久坐。