# 枚舉1
by:hush
---
## 枚舉?
----
很直觀的做法
就是把所有的可能性都檢查一遍，確保萬無一失
---
## 一般的枚舉
----
舉例：檢查一個數$n$($2\le n\le 10^6$)是否為質數
----
枚舉$[2,n-1]$
* 若存在任意一個數可以整除$n$
則$n$不為質數
----
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
signed main()
{
//colinorz;
int n; cin >> n;
bool ans=1;
for (int i=2;i<n;i++) if (n%i==0) ans=0;
cout << ans << endl;
}
```
---
### 剪枝
----
剛剛那個問題有一個明顯的性質：
* 若存在兩個自然數$p,q$為$n$的因數($n=p\cdot q$)
則$min(p,q)\le \sqrt n$ (否則$p\cdot q\gt n$)
* 所以其實只需要枚舉$[2,\lfloor \sqrt n\rfloor ]$
----
把 "$i\lt n$" 改成 "$i\times i\le n$" 即可
```cpp=14
for (int i=2;i*i<=n;i++) if (n%i==0) ans=0;
```
---
再看一題：
給你一個字串$s$，求$s$內的最長回文子字串的長度
$(\vert s\vert\le 10^4)$
----
子字串代表從原字串取一段**連續**的子字串
例如"csdcorz"是母字串，那麼：
* "csdc" 是子字串
* "csorz" 不是
* "csdcorz" 是
* "" 是
----
* 直覺的想法：
枚舉子字串的左界與右界，並檢測枚舉的子串是否為回文，紀錄最大的區間大小。
----
範例程式碼：
```cpp=
#include <bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
string s;
signed main()
{
//colinorz;
int ans=0; cin >> s;
for (int i=0;i<s.size();i++)
for (int j=i;j<s.size();j++)
{
if (j-i+1<=ans) continue; //剪枝
bool isp=1;
for (int l=i,r=j; isp&&l<r; l++,r--)
if (s[l]!=s[r]) isp=0;
if (isp) ans=j-i+1;
}
cout << ans <<'\n';
}
```
----
* 複雜度分析：
枚舉左右界的時間複雜度$O(\vert s\vert ^2)$，檢查是否符合條件$O(\vert s\vert)$，相乘$O(\vert s\vert^3)$，題目的$\vert s\vert \le 10^4$，帶進去要$10^{12}$次，TLE。
----
仔細分析回文的性質會發現：
* 若$s[l]$~$s[r]$不是回文
則$s[l-1]$~$s[r+1]$也絕對不是
* 若$s[l]$~$s[r]$是回文
則只需判斷$s[l-1]=s[r+1]$成立與否即可
共通點是他們的字串中心一樣
----
前面的做法會重複檢查到很多字串中心一樣的字串，所以我們改成枚舉每個字串中心，看可以擴展到多大。
----
範例程式碼：
```cpp=
#include <bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
string s;
signed main()
{
//colinorz;
int ans=0; cin >> s;
for (int i=0;i<s.size();i++)
{
for (int l=i,r=i;l>=0&&r<s.size()&&s[l]==s[r];l--,r++)
ans=max(ans,r-l+1);
for (int l=i,r=i+1;l>=0&&r<s.size()&&s[l]==s[r];l--,r++)
ans=max(ans,r-l+1);
}
cout << ans <<'\n';
}
```
----
* 複雜度分析：
中心點數量$O(\vert s\vert)$，擴展次數不超過$O(\vert s\vert)$，所以相乘不超過$O(\vert s\vert^2)$，不會TLE。
---
### 練習題
----
- [csdc358](https://csdc.tw/problem/358/)
- [csdc396](https://csdc.tw/problem/396/)
----
- CSDC 358題解
枚舉第一個骰子的每一面，對於它的第$i$面枚舉第二個骰子的每一面，檢查兩個相加是否符合特定數
時間複雜度：$O(面數^2)$
- 另解：
排序第二個骰子，枚舉第一個骰子，對於它的第$i$面二分枚舉第二個骰子
時間複雜度：$O(面數 log 面數)$
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
vector<int> a(1005),b(1005);
signed main()
{
int n,m,q,c=0; cin >> n >> m;
for (int i=0;i<n;i++) cin >> a[i];
for (int i=0;i<m;i++) cin >> b[i];
cin >> q;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
if (a[i]+b[j]==q) c++;
if (c==0) cout << 0 <<'\n';
else if (c==n*m) cout << n*m << '\n';
else cout << c/__gcd(c,n*m) << '/' << n*m/__gcd(c,n*m);
//不使用gcd函數也可使用枚舉
}
```
----
- CSDC 396題解
枚舉$1$~$n$天，對於第$i$天枚舉每一種報告，判斷當天是否有超過三種報告(也就是$i$是否在至少三個區間內)
- 另解
使用差分序列(有興趣的可以[自學](https://apcs.guide/courses/advanced/tricks/difference)或是以後可能會教)
----
```cpp=
#include<bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
vector<pii> r(10005);
signed main()
{
//colinorz;
int n,m,ans=0; cin >> n >> m;
for (int i=0;i<m;i++)
{
int a,b; cin >> a >> b;
r[i]={a,b};
}
for (int i=1;!ans && i<=n;i++)
{
int cnt=0;
for (int j=0;cnt<3 && j<m;j++)
if (r[j].fi<=i&&i<=r[j].se) cnt++;
if (cnt>=3) ans=1;
}
if (ans) cout << "No\n";
else cout << "Yes\n";
}
```
---
## 進階的枚舉
---
### 二分枚舉
----
又稱為二分搜
- 概念：就是透過枚舉中點每次排除一半可能性的枚舉
- 可用在有圖形具有單調性(遞增/遞減)的問題
題目關鍵字：找出符合條件的值最大(小)可以到多大(小)
----
#### 丟雞蛋問題
*by : chatgpt*
----
在一個$n$層的大樓，給你一種超硬的雞蛋無限多顆
測試雞蛋最低在哪一層會開始破掉$(n\le 10^{18})$
----
如果從第一層開始去一層一層慢慢砸效率太低
最多會算到$n$次，複雜度太高
----
在經過精密的計算後發現雞蛋破的情況長這樣:
破了
破了
⁝
破了
破了
沒破
⁝
沒破
沒破
----
所以當你在第$k$層丟一顆雞蛋
* 若它沒破，則$1$ ~ $k$層都沒破
否則$k$ ~ $n$層都是破了
----
那每次都從一半檢查，就可以排除一半可能性
直到找到沒破和破的交界處，複雜度$O(log$ $n)$
---
- 應用：終極密碼
在一個遞增(或減)的序列找到第一個大於(等於)或小於(等於)某數$k$的位置$i$
----
- 實作方法(以遞增、大於等於舉例)：
1. 手刻(常用於枚舉數值)
2. 使用STL(常用於搜尋)
----
#### 手刻：
----
變數
- $l$ 代表枚舉範圍的左界
- $r$ 代表枚舉範圍的右界
- $mid$ 代表枚舉的點
----
- $mid=(l+r)/2$
<span>$l+r太大可能會overflow$<!-- .element: class="fragment" data-fragment-index="1" --></span>
- $mid=l+(r-l)/2$
<span>用減法所以不會<!-- .element: class="fragment" data-fragment-index="2" --></span>
----
----
找到第一個$\ge k$的位置
```cpp=
int b_search(int l,int r,int k)
{
while(l<r) //[l,r)
{
int mid=l+(r-l)/2;
if (a[mid]>=k) //符合條件
r=mid; //把r移到已知符合條件的最小位置
else //不符合
l=mid+1; //把l移到不符合的下一個位置
}
return r;
}
```
----
使用STL:
- lower_bound(a,a+n,k)找到第一個$\ge k$的位置
- upper_bound(a,a+n,k)找到第一個$\gt k$的位置
```cpp=
#include<bits/stdc++.h>
using namespace std;
constexpr int n=6;
int a[n]={1,3,4,6,8,9};
signed main()
{
cout << lower_bound(a,a+n,0)-a <<'\n'; //0
cout << lower_bound(a,a+n,4)-a <<'\n'; //2
cout << upper_bound(a,a+n,4)-a <<'\n'; //3
cout << lower_bound(a,a+n,11)-a <<'\n'; //6(=n)
}
```
----
例題：[csdc199](https://csdc.tw/problem/199/) 因為有單調性，可使用二分搜
時間複雜度$O(Q\cdot log$ $n)$
----
手刻函式解：
```cpp=
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int b_search(int l,int r,int k)
{
while(l<r) //[l,r)
{
int mid=l+(r-l)/2;
if (a[mid]>=k) r=mid; //把r移到符合條件的位置
else l=mid+1; //把l移到不符合的下一個位置
}
return r;
}
signed main()
{
int n; cin >> n;
for (int i=0;i<n;i++) cin >> a[i];
int q; cin >> q;
while (q--)
{
int x; cin >> x;
cout << b_search(0,n,x) << '\n';
}
}
```
----
用STL解：
```cpp=
#include<bits/stdc++.h>
using namespace std;
int a[100005];
signed main()
{
int n; cin >> n;
for (int i=0;i<n;i++) cin >> a[i];
int q; cin >> q;
while (q--)
{
int x; cin >> x;
cout << lower_bound(a,a+n,x)-a << '\n';
}
}
```
---
### 練習題
----
- [csdc65](https://csdc.tw/problem/65/)
- [csdc236](https://csdc.tw/problem/236/)
- [APCS 202201 P4](https://zerojudge.tw/ShowProblem?problemid=h084)
----
- CSDC 65題解
題意：在遞增序列中找到最後一個元素大小$\le X$的位置，也就是第一個$\gt X$的前一個
可以手刻二分搜或使用upper_bound
----
AC code 1:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int b_search(int l,int r,int k)
{ //找到第一個大於k的位置-1
while (l<r)
{
int mid=l+(r-l)/2;
if (a[mid]>k) //符合條件
r=mid;
else
l=mid+1;
}
return r-1;
}
signed main()
{
int n,m; cin >> n >> m;
for (int i=1;i<=n;i++) cin >> a[i];
while (m--)
{
int x; cin >> x;
cout << b_search(1,n+1,x) << '\n';
//因為陣列範圍是[1,n]所以要再加1
}
}
```
----
AC code 2:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int a[100005];
signed main()
{
int n,m; cin >> n >> m;
for (int i=1;i<=n;i++) cin >> a[i];
while (m--)
{
int x; cin >> x;
cout << (upper_bound(a,a+n+1,x)-a)-1 << '\n';
}
}
```
----
CSDC 236題解
1. 若容積為$v$可以收集所有的雨水，則容積$\gt v$也一定可以，也就是定義函數$k=f(v)$為「對於容積$v$可收集的(雨水)杯數為$k$」，則$f(v)$具有單調性，所以可以對$v$做二分搜。
2. 二分搜的上下界( $r$ $\&$ $l$ )：
- $v$至少要跟最大杯的水一樣大，否則一定無法把水倒完，$l=min(w_i)$
- 若$v=$全部水的總體積，則一定可以倒完所有水，再大就浪費了，$r=\sum{w_i}$
----
3. 實作出$f(v)$
- 若$f(v)=m$，去使用$\gt r$的$v$都會浪費空間，則$r=v$
- 否則罐子太小，使用$\le l$的$v$都不可能成立，則$l=v+1$
4. 做到$l\not\lt r，$由於$r$一直是最小可能的答案，因此答案最後會是$r，(其實l=r)$
- 複雜度分析：二分搜複雜度$O(log(r-l))$，也就是$O(log(n\cdot w_i))$，每次檢查要$O(n)$，所以總複雜度是$O(n\cdot log(n\cdot w_i))$
----
AC code:
```cpp=
#include <bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define endl '\n'
using namespace std;
int n,m,w[5005];
int f(int v)
{
int cnt=1,rem=v;
for (int i=1;i<=m;i++) //第幾罐
{
while (cnt<=n && rem>=w[cnt]) rem-=w[cnt++];
if (cnt>n) return cnt; //裝完了!!!
rem=v;
}
return cnt;
}
signed main()
{
//colinorz;
int t; cin >> t;
int wmax=0,sum=0;
while (t--)
{
cin >> m >> n;
for (int i=1;i<=n;i++)
{
cin >> w[i];
sum+=w[i]; wmax=max(wmax,w[i]);
}
int l=wmax,r=sum;
while (l<r)
{
int mid=l+(r-l)/2;
if (f(mid)>n) r=mid; //因為我偷懶讓他多加一
else l=mid+1;
}
cout << r << endl;
wmax=sum=0;
}
}
```
----
- APCS 202201 P4 題解
----
AC code
```cpp=
```
---
### 雙指標
----
- **雙指標**(Two Pointers)又稱**滑動視窗**(Sliding Window)，是一種神奇的解題小技巧，用來(快速的)在一個序列中枚舉兩個指標。
- 常見問題：求序列中兩數相加(乘)等於x的個數、長度為$s$的子序列和極值、子序列和大(小)於$k$的最長長度...
----
- 直接看題目：
給你一個正整數$n\le 10^6$，輸出所有和為$n$的連續正整數數列(至少兩個數)
範例輸入：
```cpp=
9
```
範例輸出：
```cpp=
2 3 4
4 5
```
----
- 題解：
使用雙指針$l, r$代表一個正整數序列$l$~$r$(包含)
- 分三種情況：
若序列和$= n$，則輸出$l$~$r$
若序列和$\le n$，則$r$加一
若序列和$\gt n$，則$l$加一
- 時間複雜度：
$l, r$ 最多只會從一跑到$1$~$n$，總共跑$2n$次，所以時間複雜度為$O(n)$
----
AC code:
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
signed main()
{
//colinorz;
int n; cin >> n;
int l=1,r=1,sum=1; //[l,r]
while (r<n)
{
if (sum==n)
{
for (int i=l;i<=r;i++)
cout << i << " \n"[i==r];
}
if (sum<=n) r++,sum+=r;
else sum-=l,l++;
}
}
```
----
進階類題：[zerojudge_k464](https://zerojudge.tw/ShowProblem?problemid=k464)
----
題解：
- 變數：
1. 用雙指標$l, r$代表一個區間$p[l]$~$p[r]$(包含)
2. 用map紀錄區間內每個地主有幾塊地
3. 用一個變數紀錄區間內地主數量
- 執行(過程中要維護map)：
1. 每次先讓$r$加一
2. 把$l$加一，重複直到區間內地主數量$\le k$
3. 更新答案
----
AC code:
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
vector<int> a(200005);
map<int,int> cnt;
signed main()
{
//colinorz;
int n,k,ams; cin >> n >> k;
for (int i=1;i<=n;i++) cin >> a[i];
int l=1,r=1,ans=0,sum=0; //[l,r]
for (;r<=n;r++)
{
cnt[a[r]]++;
if (cnt[a[r]]==1) sum++;
for (;sum>k;l++)
{
cnt[a[l]]--;
if (cnt[a[l]]==0) sum--;
}
ans=max(ans,r-l+1);
}
cout << ans << endl;
}
```
---
# 謝謝大家
{"title":"枚舉1","description":"type : slide","contributors":"[{\"id\":\"b49547c8-0e7f-46d0-99b2-8a45dfee8e90\",\"add\":11457,\"del\":496}]"}