---
###### 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$ 遞迴

----

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$

再用一些方式避免枚舉到用過的行就好 (?)

----

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)$

----

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$

---

## 更多例題

----