--- ###### tags: `CRC` --- # 枚舉與 Greedy WiwiHo --- https://hackmd.io/@wiwiho/crc1082algo https://tg.pe/xgaG  --- # 枚舉 ---- 枚舉？ ---- 暴力 (X) 聰明的暴力 (O) --- ## 普通的枚舉 ----  ---- 枚舉 $k$ 和 $x$ 代進去檢查會不會等於 $n$？ ---- 有 $k$ 就可以算 $x=\frac{n}{2^k-1}$ 有 $x$ 就可以算 $2^k-1=\frac{n}{x}$ $\Rightarrow$ 只要枚舉一個就好 ---- 題目要 $x$，所以枚舉 $x$？ 時間複雜度：$O(n)$ 但 $n=10^9$ 怎麼辦？ ---- 那就枚舉 $k$ 吧 時間複雜度：$O(\log n)$ ----  ---- 枚舉 $2\sim n$ 的整數 $k$ 再對整數 $k$ 花 $O(k)$ 時間暴搜有沒有因數 是質數的話再判斷是不是 $n$ 的因數 時間複雜度：$O(n^2)$ ---- 有沒有辦法優化？ ---- 從判斷質數下手？ ---- 質數篩？？ 時間複雜度：$O(n)$ 不要中毒 ---- 根本就不用判 ---- 從小到大枚舉 $k$ 遇到 $n$ 的因數 就不斷 $n \gets \frac{n}{k}$ 直到 $n$ 不被 $k$ 整除為止 ---- 如果 $k$ 不是質數且它是一開始的 $n$ 的因數 因為是由小到大枚舉 $k$ 而 $k$ 的質因數小於 $k$ 此時的 $n$ 肯定不是 $k$ 的倍數 ---- 時間複雜度： $O(n)$ ---- 可以更好嗎？ ---- 如果某數字 $x$ 是合數 那它肯定有一個因數 $\leq \sqrt{x}$ ---- $\Rightarrow$ 只要從 $1 \sim \sqrt{n}$ 枚舉 $k$ 最後如果 $n>1$ 那剩下來的 $n$ 就也是本來的 $n$ 的質因數 ---- 時間複雜度：$O(\sqrt{n})$ --- ## 遞迴與剪枝 ----  ---- 枚舉 $C^n_k$ 個子序列 ---- 先枚舉第一個元素 再枚舉第二個…… 再枚舉第 $k$ 個 $\Rightarrow$ 遞迴 ---- ```cpp= int x = 0; int ans = 0; //已經枚舉了 cnt 項，現在要枚舉第 cnt+1 項，且這一項應該在第 lst 項之後 void solve(int lst, int cnt){ if(cnt == k){ ans = max(ans, x); //已經枚舉完整個子序列就更新答案 return; } for(int i = lst + 1; i < n; i++){ x ^= a[i]; solve(i, cnt + 1); x ^= a[i]; } } ``` ---- 遞迴深度：$k$ 終止點：$C^n_k$ 時間複雜度：$O(kC^n_k)$ ----  ---- 枚舉 $C^{n^2}_n$ 種位置組合再檢查？ 顯然不行 ---- 同一行上只有恰一個皇后 同一列上也是 ---- 枚舉每一列上的皇后在哪一行 有 $n!$ 種可能 再檢查有沒有同一條斜線上的 ---- 如果前面幾個就出現在同一條斜線上的了呢？ ---- ### 剪枝 ---- 遞迴枚舉每一列上的皇后在哪一行 如果發現同一斜線或同一行上也有 就不要繼續枚舉下一列 ---- 遞迴枚舉時不排除用過的行 可以做到 $n=14$ 再用一些方式避免枚舉到用過的行就好 (?) ---- ```cpp= int n, ans = 0; vector<bool> lr, rl; queue<int> c; void solve(int now){ if(now == n){ ans++; return; } int t = c.size(); while(t--){ int i = c.front(); if(lr[i - now + n] || rl[i + now]){ c.pop(); c.push(i); continue; } c.pop(); lr[i - now + n] = rl[i + now] = true; solve(now + 1); lr[i - now + n] = rl[i + now] = false; c.push(i); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); while(cin >> n){ ans = 0; lr.resize(2 * n); rl.resize(2 * n); while(!c.empty()) c.pop(); for(int i = 0; i < n; i++) c.push(i); solve(0); cout << ans << "\n"; } return 0; } ``` --- ## 0/1 枚舉 ----  ---- 遞迴？ ---- 當然可以 時間複雜度：$O(2^n)$ 但有點難寫 ---- 每一個元素都有兩種狀態： 取或不取 ---- 用一個整數表示每個元素的狀態 在二進位下的第 $i$ 個位元是 1 就表示第 $i$ 個元素要取 否則就是不取 ---- 枚舉 $1 \sim 2^n-1$ 再用 $O(n)$ 時間計算 xor 和 時間複雜度：$O(n2^n)$ ---- ```cpp= int ans = 0; for(int i = 0; i < (1 << n); i++){ int now = 0; for(int j = 0; j < n; j++){ if(i & (1 << j)) now ^= a[j]; } ans = max(ans, now); } ``` --- ## 排列枚舉 ---- - `next_permutation(a.begin(), a.end())` - `prev_permutation(a.begin(), a.end())` --- # 雙指標與單調隊列 --- ## 雙指標 ---- 用兩個指標做事 ----  ---- $O(NQ \log N)$ 作法： 用一個 map 存每一種數字的數量 詢問時對每一個 $a_i$ 找有沒有數字是 $a_i-K$ （注意 $K=0$ 時的狀況） $\Rightarrow$ TLE ---- $O(NQ)$ 作法： 雙指標 --- ## 單調隊列 ---- 想聽的話我下課後再講給你聽 (?) --- # Greedy --- ## Greedy 的原則 ---- 不斷用「目前看起來最好」的方式解決問題 ---- 1. 找出大問題中的小問題。 2. 對小問題求小問題的最佳解。 3. 用小問題的最佳解拼出大問題的最佳解。 ---- 有一個長度 $n$ 的數列 $a$ 這個數列裡取 $k$ 個元素的和最大能是多少？ ---- 0/1 背包問題 有 $n$ 個物品 價值和體積分別是 $v_1, v_2, ..., v_n$ 和 $w_1, w_2, ..., w_n$ 還有一個大小 $m$ 的背包 所有放進背包裡的物品體積和不能超過容量 求能放進的物品的總價值最多是多少 ---- 先取 CP 值大的？ ---- $n=4$、$m=6$ $v=\{8,3,3,3\}$ $w=\{5,2,2,2\}$ 得出的答案：$8$ 正確答案：$9$ ----  ---- 先亂想一個作法 先選擇左端點在較左邊的 如果不會跟之前選過的線段重疊就選 不然就不選 ---- $[1,10]$ $[2,3]$ $[4,5]$ 得出的答案：1 條（選了 $[1,10]$） 正確答案：2 條（$[2,3]$ 和 $[4,5]$） ---- 正確作法： 先取右端點在較左邊的線段 --- ## 證明 ---- - 證明小問題的最佳解可以拼成大問題的最佳解 - 反證法，證明不存在更佳解 - 證明所有的最佳解都能用某種方式變成你想的樣子 - ~~Proof by AC~~ ---- 我們得出的最佳解：$G$ 某一個最佳解：$G'$ $G$ 和 $G'$ 中第一條不一樣的線段：$G_i$、$G'_i$ ----  ---- $G$ 的大小肯定和 $G'$ 一樣 ---- $G'$ 肯定可以變成 $G$ --- ## 更多例題 ----