# 第二章 : 進階技巧 遞迴、枚舉、二分搜(後半)
>本篇取自2024資訊培訓教材
由於遞迴需要用到函式的概念，下面的枚舉也會頻繁用到迴圈，二分搜會用到排序，如果都還不熟建議先去了解。
同時也建議讀AP325前要確保能穩定解出APCS第二題，原因節錄AP325作者自序:
> 這一份教材設定的讀者對象是已經對基礎的程式語法與架構有所了解，而教材的目的是
透過解題的方式來介紹一些資料結構的使用與演算法的思考方式。以 APCS 實作題檢測
的程度來說，教材的對象就是從三級分要進步到五級分的人，或者說是學會基礎程式後
想要進入程式競賽的人。
### 遞迴
程式裡的遞迴跟數學上的很像，都是函數呼叫函數自己本身，先來個最簡單的例子:
***費式數列***
$$ f(1) = 1 $$
$$f(2) = 1$$
$$f(x) = f(x-1) + f(x-2), x\epsilon N $$
這就是費式數列的遞迴式，如果把每個遞迴分枝都畫出來，就會長這樣
程式其實跟數學式很像，只要呼叫$f(x-1)$和$f(x-2)$就好
```cpp=
int f(int x){
if(x<=2) return 1;
return f(x-1)+f(x-2);
}
```
但要注意，遞迴程式有個東西非常重要，就是base case，也就是程式執行==到最底==時要做的事，像是費式數列的base case就是$f(1) = 1 ,f(2)=1$，如果沒有處理好base case，程式很有可能會無窮遞迴，程式永遠不會結束。
遞迴另一個重要的點是，相信你的程式會給你正確答案，舉個例子:
***河內塔***
要把這三個環移到最右邊的柱子，但每次只能動一個環，而且大的環不能疊在小的環上(綠最小、藍色第二、紅色最大)，步驟如下:
再試試看四個環、五個環，可以發現他有某種規律，太複雜這裡就不畫了，規律就是:
>假設現在有$n$個環，先把上面$n-1$個環移到中間，再把第$n$個環移到最右邊，最後再把$n-1$個環移到最右邊。
但$n-1$個環要怎麼移動?可以發現跟$n$個環的時候一樣，先把$(n-1)-1$個環移到右邊，再把第$n-1$個環移到中間，最後把$(n-1)-1$個環移到中間，就出現遞迴關係了!
```cpp=
//有n個環 從a柱子透過b柱子移到c柱子
int f(int n,int a,int b,int c){
//沒環了 不用移
if(n==0) return;
//把n-1個環移到b
f(n-1,a,c,b);
//把第n個環移c
//把n-1個環移到c
f(n-1,b,a,c);
}
```
其中重點就是要相信自己的``f(n-1,a,c,b)``和``f(n-1,b,a,c)``都已經幫你把$n-1$個環移好了，只要照著我們找到的規律寫就好。
還有別忘記非常重要的base case，$n=0$的時候代表現在沒有環要移，可以直接結束遞迴。
最後講一題AP325的題目:
***Q_1_5. 二維黑白影像編碼***
題目說碰到2後長度切半，然後給左上、右上、左下、右下四個區域。碰到1代表正方形區域全部是黑色，0代表正方形區域全部是白色。
既然遇到0或1可以知道整個區域，代表可以直接回傳答案，**也是base case**，而遇到2則切成四塊告訴你，所以要遞迴找答案，分別對四個區域遞迴**然後相信你的程式可以正確計算出答案**，把四個區域的黑格子數量加起來回傳就好!
```cpp=
#include<bits/stdc++.h>
using namespace std;
int i=0; //i要是全域變數! 不然會算到重複的字串
string a;
int solve(int n){
int ans=0;
if(a[i]=='2'){
i++;
ans+=solve(n/2); //左上
i++;
ans+=solve(n/2); //右上
i++;
ans+=solve(n/2); //左下
i++;
ans+=solve(n/2); //右下
}else{
ans=n*n*(a[i]-'0'); //透過(a[i]-'0')知道是1還是0，*0必為0，*1必不變
}
return ans;
}
int main(){
cin>>a;
int n;
cin>>n;
cout<<solve(n);
}
```
### 枚舉
數學排列組合教過，解題最簡單暴力的方法是把所有可能列出來，再去找符合條件的可能，但數學跟程式的差別是，人類算很慢，但電腦算超快，所以可以把這個工作丟給電腦。
- 基礎枚舉
先來看個簡單的枚舉題：
[第五次APCS模擬賽第二題](https://apcs-simulation.com/problem/apcs0502)
很顯然地，題目重點是要找到震央的位置和SCPA度，尋找的方式是透過朋友給的座標和當地的SCPA度，我們可以枚舉每個點每個SPCA度的可能，然後比對所有朋友給的資訊來判斷符不符合，都符合的點就是震央。
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,m;
//枚舉每個座標的朋友收到的資訊
bool test(int xx,int yy,int sk,vector<vector<int>> &qry,vector<vector<int>> &g){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(qry[i][j]!=-1){
if(min(max((sk+g[i][j]-(abs(xx-i)+abs(yy-j))),0),50)!=qry[i][j]){
return false;
}
}
}
}
return true;
}
int main(){
int w,q;
cin>>n>>m>>w>>q;
vector<vector<int>> g(n,vector<int>(m)),Q(n,vector<int>(m,-1));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>g[i][j];
}
}
//把朋友的資訊存入座標
for(int i=0;i<w;i++){
int x,y,v;
cin>>x>>y>>v;
Q[x][y]=v;
}
int skx,sky,scpa;
//枚舉每個震央的每個SCPA
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
for(int sk=1;sk<=50;sk++){
//找到了 紀錄
if(test(i,j,sk,Q,g)){
skx=i;
sky=j;
scpa=sk;
}
}
}
}
//找答案
for(int i=0;i<q;i++){
int x,y;
cin>>x>>y;
int ans=min(max(scpa-(abs(skx-x)+abs(sky-y))+g[x][y],0),50);
cout<<ans<<'\n';
}
}
```
不過枚舉畢竟是最暴力的方法，很容易不小心超過時間限制，所以選擇暴力時要先精算複雜度，我的解法枚舉了所有點$o(nm)$的所有SCPA度$o(50)$，同時每次枚舉所有座標的朋友$o(nm)$判斷符不符合條件，所以整體複雜度是$o(50*n^{2}m^{2}$)，看起來複雜度非常糟糕，但看一下題目給的範圍（$n,m \le 30$），把數字帶進去就是$50 \times 30^{2} \times 30^{2}=40500000$大概是$4e7$，可以在一秒的時間內跑完。
APCS第一第二題的範圍通常會給很寬，暴力判斷每種可能符不符合有時候是很好的解法，不過雖然暴力，很多枚舉技巧並不簡單，下面這個枚舉技巧當初我花了不少時間理解，所以培訓的時候聽不懂很正常（主要我教好爛），聽懂的話就是你超強。
- 位元枚舉
位元枚舉其實排列組合時大概有提到，主要在計算的是**對於每個數字 選或不選** 的所有組合可能，有點抽象 我們帶個題目感受一下：
***ap325 Q-1-8. 子集合的和***
我們對每個數字選擇或不選擇都會岔出一個分支，都會是一種組合可能，我們要做的就是找出所有可能看看總合有沒有超過P，有沒有比目前的答案靠近P，透過遞迴 我們就能做到這件事。
```cpp=
void func(int i,int now){
//遞迴base case i走到底了 代表我們找到一種可能了 跟答案比對
if(i>=n){
if(now>maxi&&now<=p){
maxi=now;
}
return;
}
//選擇這個數字的分支
func(i+1,now+a[i]);
//不選擇這個數字的分支
func(i+1,now);
}
```
這是最經典的位元枚舉，判斷每個數字要拿或不拿，那時間複雜度呢？
因為每個數字都有拿跟不拿 兩種分支，所以雜度是$2^{n}$，他是指數函數，各位數學大神應該都知道他的增長極快，因此位元枚舉的題目測資都不能放太大，大概就是$n \le 20 到 30$，其實很明顯，看到這個範圍基本上可以往位元枚舉想。
而位元枚舉之所以叫位元枚舉，因為他的迴圈版本跟數字的二進位位元有關係，不過會用到一些位元操作，所以以下講兩個位元枚舉會用到的，對剩下其他位元操作有興趣的可以自行上網查。
- and &
> ``a&b``意思是，把a,b轉換成二進位後，對每個位元做and運算，圖例:
$43 \& 30 = 10$
- 左移 <<
> ``a<<b``意思是，把a轉換成二進位後，把每個位元往左推($2^{0}$在最右邊)，圖例:
$20 << 2 = 80$
$a<<b$可以想成$a\times 2^{b}$
- 其他
> xor ^
> or |
按位取反 ~
右移>>
```cpp=
//枚舉所有可能
for(int i=0;i<(1<<n);i++){
int now=0;
//判斷每個位元是0還是1
for(int j=0;j<n;j++){
//代表這一位是1 要選
if(i&(1<<j)){
//做你要做的事
now+=a[j];
}
}
if(now<=p&&now>maxi) maxi = now;
}
```
迴圈版本的時間複雜度是?
最外層的for迴圈從$0$跑到$2^{n} - 1$，總共跑了$2^{n}$次，
內層的for迴圈從$0$跑到$n-1$，總共跑了$n$次，
因此總時間複雜度是$O(2^{n})\times O(n) = O(n2^{n})$
雖然時間複雜度比遞迴慢，但$n$通常很小，時間上並不會差很多，而且很多時候位元枚舉需要做比較複雜的事時(像是位元dp)，迴圈版本會比遞迴版本靈活(我個人感受上)。
放一個題目當作練習:
[CSES apple division](https://cses.fi/problemset/task/1623)
提示 : (黑色可以點開)||可以把分給第一組當成選，分給第二組當成不選||
其實位元枚舉可以把$n$出到40，透過一個叫**折半枚舉**的技巧可以讓位元枚舉時間複雜度壓到$O(2\times2^{n/2} + 2^{n/2} \times \log{2^{n/2}})$，看起來複雜度好複雜，實作起來也確實有點複雜，不過這個技巧目前應該不需要學，有興趣可以自己去查，(我記得cchs judge上明達學長有非常詳細的解釋)。
- 全排列枚舉
這個技巧我在AP325上沒有翻到，但其實APCS有出過(上次APCS 2024/6 第三題)，而且我覺得也蠻重要的，不過沒聽懂的話也很正常，這部分有點像 ***第七章 圖論*** 的DFS，沒學過可能會比較難理解。
其實C++的函式庫裡已經有幫我們寫好的全排列枚舉函式``next_permutation()``，用法如下:
```cpp=
vector<int> a(n); //要全排列枚舉的陣列
sort(a.begin(),a.end()); //記得用之前一定要先排序!!!
do{
//做你要做的事 這裡用輸出舉例
for(int i=0;i<n;i++){
cout<<a[i]<<" \n"[i==n-1];
}
}while(next_permutation(a.begin(),a.end()));
```
這樣就可以找出所有排列了，但一定一定要記得，==使用前要先排序==，不然沒辦法找出所有排列，這跟他實現的原理有關。
時間複雜度的部分，數學課講過了，有$n!$種排列，而我們花$O(n)$的時間輸出，因此複雜度是$O(n\times n!)$，n最多只能到12。
那怎麼自己做全排列枚舉呢?有兩個重點
1.每排一個數字都要確認所有可能
2.不能排已經排過的數字
還是有點抽象，直接看程式:
```cpp=
vector<int> a(n); //要全排列的陣列
vector<bool> vs(n,false); //紀錄有沒有排過
void f(int i,vector<int> &now){
//base case 所有數字都排過了
if(i==n) {
for(int j=0;j<n;j++){
cout<<now[j]<<" \n"[j==n];
}
return;
}
//每一個數字都排排看
for(int j=0;j<n;j++){
//目前分支沒排過 排
if(!vs[j]){
//放進目前的排列後 遞迴枚舉
now.push_back(a[j]);
vs[j]=true;
f(i+1,now);
//枚舉完目前分支了 復原
now.pop_back();
vs[j]=false;
}
}
}
```
這樣就能枚舉所有排列了，但[APCS那題](https://zerojudge.tw/ShowProblem?problemid=o078)好像不太一樣，重複的數字可以選欸?
那就把vs陣列拿掉就好了!時間複雜度會變$O(K^{L})$(根據題意)，數字帶入是$10^{8}$可以在一秒的時間內跑完，剩下的部分只要放進``set``或***trie***或其他可以比對的資料結構比較就好，我的程式:
```cpp=
string s,ss;
vector<string> alls;
void dfs(int i,string &now){
if(i==0){
alls.push_back(n);
return;
}
for(auto x:s){
now.push_back(x);
dfs(i-1,n);
now.pop_back();
}
}
```
- 總結
枚舉沒有特定哪題就一定要用哪個技巧，最重要的是能夠列出所有可能，不能遺漏。
最後在講解一題,總結枚舉的精神:
***ap325 Q-1-11 刪除矩陣邊界-遞迴***
```cpp=
#include<bits/stdc++.h>
using namespace std;
int f(int x1,int y1,int x2,int y2,vector<vector<int>> &g){
if(x1>x2||y1>y2) return 0;
int zr=0,on=0;
for(int i=y1;i<=y2;i++){
if(g[x1][i]) on++;
else zr++;
}
int up=min(on,zr)+f(x1+1,y1,x2,y2,g);
zr=0,on=0;
for(int i=y1;i<=y2;i++){
if(g[x2][i]) on++;
else zr++;
}
int dw=min(on,zr)+f(x1,y1,x2-1,y2,g);
on=0,zr=0;
for(int i=x1;i<=x2;i++){
if(g[i][y1]) on++;
else zr++;
}
int lf=min(on,zr)+f(x1,y1+1,x2,y2,g);
zr=0,on=0;
for(int i=x1;i<=x2;i++){
if(g[i][y2]) on++;
else zr++;
}
int rg=min(zr,on)+f(x1,y1,x2,y2-1,g);
return min({rg,lf,dw,up});
}
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>> g(n,vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>g[i][j];
}
}
int ans=f(0,0,n-1,m-1,g);
cout<<ans<<'\n';
}
```
只要分別把上下左右的答案分別計算好，最後取min回傳即可，至於計算答案的方式，就是遞迴下去枚舉，然後相信你的程式會幫你計算好，還有千忘別忘記base case：區間不存在直接return 0。
枚舉的重點：別遺漏任何可能
遞迴的重點：記得base case，相信程式
### 二分搜
二分搜的用途非常廣，因為他$\log n$非常快的複雜度非常受到歡迎（APCS特別愛考），不過在使用二分搜時是有條件的，畫個圖的話他應該長這樣：
轉成文字就是，要二分搜的函數（或陣列）要滿足單調性。
單調性又是什麼？
可以把他想成，函數必須非嚴格遞增或遞減，前項一定要$\le$後項（或相反），只有滿足這個條件，才能二分搜。
### C++內建函式
C++有內建二分搜函式，``lower_bound``和``upper_bound``，用法如下:
```cpp=
vector<int> a(n); //要二分搜的陣列
sort(a.begin(),a.end()); //記得排序以滿足單調性
int x; //要二分搜的值
// 第一個大於等於的數字
auto it = lower_bound(a.begin(),a.end(),x);
//第一個大於的數字
auto it2 = upper_bound(a.begin(),a.end(),x);
cout<<*it<<' '<<*it2<<'\n';
```
這兩個函式的回傳值是迭代器，學過指標的可以把他想成C++特別設計的指標，沒學過的可以把它當成在電腦記憶體的位置，因此想要利用這兩個函式的值，前面要加*。
還有一定要記得，使用前要確定陣列是已經排序好的，不然會二分搜出亂數。
不過題目通常不會只是對陣分搜這麼簡單，更多時候是需要自己刻二分搜，以下介紹兩種二分搜方式。
### 傳統二分搜
二分搜的原理應該國中學過，就是每次都戳中，如果太小就戳右邊，太大就戳左邊，傳統二分搜的寫法就完全依照這個規則:
```cpp=
int l=0,r=1e9;
//若l+1==r時，代表只剩一個數字，即答案
while(l+1<r){
//戳中間
int mid = (l+r)/2;
//太大縮右界
if(f(mid)/*太大*/) r=mid;
//太小縮左界
else l=mid;
}
//輸出答案
cout<<l<<'\n';
```
傳統二分搜最需要注意的點是邊界情況，為了避免搞亂邊界情況，建議保持永遠統一左閉右開，也就是包含左界不包含右界，因此``l+1==r``時才會只包含一個數字。
### 跳跳二分搜
這是我個人比較喜歡的二分搜寫法，也是AP325推薦的二分搜寫法，因為邊界情況沒有傳統二分搜混亂(但我這幾天才被卡邊界)，但還是不能忽視邊界情況，主要原理是，先往前跳看看，如果跳太遠就不要跳，然後跳的距離砍半，直到跳的距離歸零，即為答案:
```cpp=
int ans=0;
for(int j=1e9;j;j>>=1){
//可以往前跳
while(f(ans+j)) ans+=j;
}
cout<<ans<<'\n';
```
雖然包了兩個迴圈，但顯然裡迴圈最多執行兩次(不然在j砍半前就會跳了)，而j每次都砍半，因此時間複雜度是$O(log(1e9))$。
### 對答案二分搜
二分搜其實並不難寫，二分搜題的難點大多在==發現單調性==，而這點只能靠觀察和經驗，而且二分搜題目通常都會跟其他演算法有關係，所以這邊就講個兩三題，剩下的只能靠你們慢慢摸索。
[APCS模擬賽 第五次第三題](https://apcs-simulation.com/problem/apcs0503)
看到題目應該會覺得 : 蛤?這跟二分搜有甚麼關係，不過很多題目看到當下很難直覺發現他是二分搜，這是我覺得二分搜最大的難點。
回到題目，觀察可以發現，往前跳的最小距離，就是板子跟板子中間的最小距離，如果最小距離越大，代表拿走的板子越多，我們可以設計$k=f(x)$代表板子間的最小距離為x時要拿走的板子數$k$，可以發現$x$越大$k$就越大，因此對這個函數二分搜$f(x)=k$時x的最大值即可，那這個函數怎麼實作?只要掃過去每個板子，如果兩個板子的間隔小於$x$就拿掉這個板子，最後統計拿掉的板子數:
```cpp=
vector<int> g(2000);
int n,k,t;
int f(int x){
//從起點開始
int now=g[0];
//拿掉的板子數
int ret=0;
//掃過每塊板子
for(int i=1;i<=n+1;i++){
//如果間隔距離小於x 拿掉板子
if(g[i]-now<x) ret++;
else now=g[i];
}
return ret;
}
signed main() {
cin>>n>>k>>t;
for(int i=1;i<=n;i++) cin>>g[i];
//起點
g[0]=0;
//終點
g[n+1]=t;
int ans=1e9;
for(int j=1e9;j;j>>=1){
//如果f(x)大於k就改變ans
while((ans-j)>0&&f(ans-j)>k) ans-=j;
}
//記得處理邊界情況
cout<<ans-1<<'\n';
}
```
[CSES array division](https://cses.fi/problemset/task/1085)
經過上一題，這題應該比較能看出單調性了，觀察發現：如果每個區間的最大總和越大，需要分割的區間就越少，我們只要設計$f(x)$代表區間最大總和為$x$時需要分割的區間數，此函數的$x$越大時，$f(x)$會非嚴格單調遞減，去二分搜$f(x)$為$k$時$x$的最小值即可。
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<int> g(2e5);
bool f(long long x){
long long ans=1,sum=x;
for(int i=0;i<n;i++){
//區間最大合根本放不下
if(x<g[i]) return false;
//如果這個區間放不下了 區間+1
if(sum<g[i]){
ans++;
sum=x;
}
//區間數太多
if(ans>k) {
return false;
}
sum-=g[i];
}
//判斷區間數符不符合條件
return sum>=0&&ans<=k;
}
int main(){
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>g[i];
}
//對f(x)二分搜
long long ans=8e18;
for(long long j=4e18;j;j>>=1){
while(f(ans-j)) ans-=j;
}
cout<<ans<<'\n';
return 0;
}
```
這題其實蠻經典的，非常推薦大家練練看。
最後在看一題難題，我當時想了蠻久的題目，最後還被邊界情況卡：
[Atcoder Beginner Contest 364 pD](https://atcoder.jp/contests/abc364/tasks/abc364_d)
這題的單調性更不明顯了，剛到時我也沒有馬上往二分搜想。
一樣設計一個$f_{b_{i}}(x)$代表查詢為$b_{i}$時，與$b_{i}$差距$x$的數字個數，與$b_{i}$差距$x$的數字個數**恰好**為$k$時，這個$x$就會是答案。
顯然$x$越大，$f_{b_{i}}(x)$就越大，在此處就有單調性可以二分搜出答案。
那問題就到$f_{b_{i}}(x)$要怎麼實做了，看起來要時間內找出有點困難，先來看看距離$b_{i}$為$x$這件事怎麼做，寫成數學式就是$|b_{i}-a_{i}| \le x$，展開移向就是就是$a_{i} \le b_{i}+x$同時$b_{i}-x \le a_{i}$的$a_{i}$個數，對$a$陣列排序後，二分搜$b_{i}-x$和$b_{i}+x$一個為頭一個為尾，尾減頭就是處在這個區間的數字個數了！時間複雜度是排序$a$陣列$O(NlogN)$，每個查詢二分搜$O(log(b_{i}+x))$，每次二分搜呼叫$f(x)$需要$O(logN)$，因此整體複雜度為$O(NlogN + Qlog(b_{i}+x)logN)$就能AC這題。
不過我當初寫跳跳二分搜被邊界情況卡了，有兩筆測資吃了WA，我也找到不到特殊邊界情況，因此以下用傳統二分搜寫：
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
int f(int b,int x,int k,vector<int> &a){
//二分搜頭
auto it1=lower_bound(a.begin(),a.end(),b-x);
//二分搜尾
auto it2=upper_bound(a.begin(),a.end(),b+x);
return (it2-it1)>=k;
}
signed main() {
int n,q;
cin>>n>>q;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
sort(a.begin(),a.end());
while(q--){
int b,k;
cin>>b>>k;
int l=-1,r=1e9;
while(l+1<r){
int mid = (r+l)/2;
//太大 縮右界
if(f(b,mid,k,a)) r=mid;
//太小 縮左界
else l=mid;
}
//我們二分搜到的是 最後不滿足的
//但我們要的是第一個滿足的
//所以+1
cout<<l+1<<'\n';
}
}
```
Sign in with Wallet
Connect another wallet