枚舉與 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\)

更多例題

Select a repo