比賽鏈接：https://vjudge.net/contest/763332。

A

最板子的雙搜，首先算出總和 \(\sum_{i=1}^{n} i\) 并將其除以二，然后對(duì)半去搜就行了。

B

甚至可以直接爆搜，因?yàn)榇螖?shù)限制過(guò)小，不需要上雙搜去輔助；當(dāng)然也是可以用 map 記錄字符串狀態(tài)然后折半去搜索的。

C

同樣也是非常板子的雙搜。

D

哎你說(shuō)得對(duì)啊，也是板子雙搜啊，咋滴個(gè)嘞，我最后存到數(shù)組里去的是 \(x\) 不是 \(sum\) 啊！后頭減的也是 \(x\) 不是 \(sum\) 啊！長(zhǎng)個(gè)記性咯。

E

定義 \(f_{i}\) 表示存在多少組 \(x^2 + y^2 = i\)，\((x,y)\) 為無(wú)序?qū)Γ?\((2,3)\) 和 \((3,2)\) 算作同一組。

這個(gè)可以最開(kāi)始先 \(O(n^2)\) 地跑出來(lái)。

然后枚舉最后的對(duì)角線(xiàn)長(zhǎng)度 \(p\) 以及高度 \(x\)，那么個(gè)數(shù)就是 \(f_{p^2-x^2}\)，因?yàn)檫€要把剩下的部分分給長(zhǎng)和寬嘛。

F

板子雙搜，記得對(duì) \(m\) 取模，以及最后的答案是 \(<m\) 不是 \(\le m\) 哦！取模后得到的值是不能超過(guò)或者等于模數(shù)的。

G

在二維矩陣上的雙搜，也很簡(jiǎn)單的，這里用的是橫縱坐標(biāo)的值相加 \(x+y\) 判斷步數(shù)情況，并且最后由于是把一個(gè)點(diǎn)重復(fù)走了兩次所以要把 \(a_{x,y}\) 最后再異或回來(lái)一次不然就會(huì)算錯(cuò)了。

H

用雙搜的話(huà)……感覺(jué)還好，但是代碼實(shí)現(xiàn)好像特別復(fù)雜，因?yàn)槟愕貌煌５貭顗海缓笥忠獕夯貋?lái)。暫時(shí)還沒(méi)寫(xiě)。

不過(guò)看題解區(qū)怎么一大片的 A*、IDA* 啊？這是什么，迭代加深，啟發(fā)式搜索，這是什么東西啊？不管了不管了哎不管了。

I

一開(kāi)始看到圖論一眼懵了，然后后面發(fā)現(xiàn)可以用二進(jìn)制壓縮存目前每個(gè)點(diǎn)的狀態(tài)，然后變化就是一個(gè)異或的條件，每個(gè)點(diǎn)連的邊的情況可以存下來(lái)，或者說(shuō)是度吧。然后雙搜一樣的從 \(1\) 跑到 \(mid\) 再?gòu)?\(n\) 跑回 \(mid+1\)，用 map 記錄。

注意了這題它卡常或者是卡 map 或者是什么的，總之不能寫(xiě)遞歸，抽出來(lái)改成遞推去枚舉兩部分分別的狀壓情況才能過(guò)。獵奇卡常題目。

J

這題它不是常規(guī)雙搜只有兩種選擇（我呃呃也只有最基本的雙搜只有兩種選擇了吧？），它一個(gè)奶牛可以選擇放入第一組或者第二組，或者也可以干脆不納入這個(gè)集合。當(dāng)然嘛就要用一個(gè) \(st\) 實(shí)時(shí)記錄當(dāng)前一二組總共的集合狀態(tài)了，二進(jìn)制壓縮。存的時(shí)候每種 \(sum\) push_back 多個(gè)合法的 \(st\) 進(jìn)去，對(duì)，用 map 套著 vector 記。然后后面找的時(shí)候枚舉 vector 中所有元素，或在一起整。注意這里不要用 map 或者什么的存最后的集合情況然后直接查 .size()，會(huì) T，直接用 bool 數(shù)組存下來(lái)最后枚舉一遍算一下就行。

小結(jié)

雙向搜索，即 meet-in-the-middle，是一個(gè)可以把 \(O(k^{n})\) 的算法優(yōu)化成 \(O(k^{n \div 2})\) 的算法，可能會(huì)帶上個(gè)把 \(\log\) 因?yàn)橛袝r(shí)候會(huì)用 map 或者其他 STL 容器進(jìn)行存儲(chǔ)。時(shí)間復(fù)雜度中的 \(k\) 為一常量，通常不會(huì)超過(guò) \(5\)，常見(jiàn)為 \(2\) 或 \(3\)。

常見(jiàn)多為 \(n\) 在 \(30 \sim 60\) 左右的這個(gè)數(shù)據(jù)范圍的情況下會(huì)用到雙向搜索，字面意思嘛，和英文解釋一樣，就是“在中間相遇”。等同于就是，對(duì)半拆分，拆成左邊 \([1,mid]\) 和右邊 \([mid+1,n]\) 兩段，然后分別從 \(1\) 跑到 \(mid\)，以及從 \(n\) 跑到 \(mid+1\)，然后中間相遇了，算出具體情況。通常為兩次 DFS 實(shí)現(xiàn)左右邊分別的情況，左邊存右邊算。有的時(shí)候題目時(shí)間需要可能會(huì)將遞歸改為遞推用二進(jìn)制狀壓來(lái)枚舉具體情況。

總之，雙向搜索是個(gè)不錯(cuò)的指數(shù)級(jí)別算法，它能把算法進(jìn)行大幅度的時(shí)間降低（通常就是把指數(shù)砍半），是個(gè)很棒的算法哦！