# 暴力玄學
###### tags: 明道中學校內培訓講義

### 內容

暴搜雖然聽起來沒什技術可言，但其實其中充滿了學(玄)問(學)。
如果認真分析一下複雜度，暴搜也是非常好用的。

---

### 複習

[自編題](http://mdcpp.mingdao.edu.tw/problem/T046) 都沒人做:cry::cry:

---

### Meet in the middle

中文稱作折半枚舉，先把問題分成兩塊枚舉，最後再想要怎麼合併起來，複雜度通常能夠變成原本的$1/2$次方

[CSES 裸題](https://cses.fi/problemset/task/1628)

[數學技巧複習](http://mdcpp.mingdao.edu.tw/problem/B016)

[配合二分搜](http://mdcpp.mingdao.edu.tw/problem/B022)

[有趣的應用](https://codeforces.com/problemset/problem/1006/F)

---

### BFS

題目通常很考驗實作能力，先想出所有 "狀態" 再進行枚舉。
就可以確保時間複雜度不會爛掉。

[八數碼問題](https://tioj.ck.tp.edu.tw/problems/1198)

[倒可樂問題](https://vjudge.net/problem/HDU-1495)

[UVA 到水問題](https://vjudge.net/problem/UVA-10603)

[好多杯子到水問題](https://tioj.ck.tp.edu.tw/problems/1008)

---

### 玄學

**要我分析複雜度的話，我還真的不會，但跑起來都比狀壓DP快很多。**

[減枝枚舉背包](http://poj.org/problem?id=3900)

[貪心枚舉](https://www.codechef.com/problems/SANSKAR)

[聽說複雜度很難證明的K著色問題類似題](https://atcoder.jp/contests/abc187/tasks/abc187_f)