---
###### tags: `CRC`
---
# 枚舉與 Greedy
WiwiHo
---
https://hackmd.io/@wiwiho/crc1082algo
https://tg.pe/xgaG
![](https://i.imgur.com/KqGWkCw.png)
---
# 枚舉
----
枚舉?
----
暴力 (X)
聰明的暴力 (O)
---
## 普通的枚舉
----
![](https://i.imgur.com/PiznJNi.png)
----
枚舉 $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)$
----
![](https://i.imgur.com/gXa0xtM.png)
----
枚舉 $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})$
---
## 遞迴與剪枝
----
![](https://i.imgur.com/qCBf5qq.png)
----
枚舉 $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)$
----
![](https://i.imgur.com/JmlqPD1.png)
----
枚舉 $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 枚舉
----
![](https://i.imgur.com/4gLYwSg.png)
----
遞迴?
----
當然可以
時間複雜度:$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())`
---
# 雙指標與單調隊列
---
## 雙指標
----
用兩個指標做事
----
![](https://i.imgur.com/ZqFmljr.png)
----
$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$
----
![](https://i.imgur.com/mg2YR9e.png)
----
先亂想一個作法
先選擇左端點在較左邊的
如果不會跟之前選過的線段重疊就選
不然就不選
----
$[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$
----
![](https://i.imgur.com/oefI4pJ.png)
----
$G$ 的大小肯定和 $G'$ 一樣
----
$G'$ 肯定可以變成 $G$
---
## 更多例題
----
![](https://i.imgur.com/XerUT7v.png)
{"metaMigratedAt":"2023-06-15T08:50:30.398Z","metaMigratedFrom":"Content","title":"枚舉與 Greedy","breaks":"false","contributors":"[{\"id\":\"02353542-5acb-4a66-abd0-128b1af24abb\",\"add\":4578,\"del\":98}]"}