---
# System prepended metadata

title: NHDK 程式暑期培訓營

---

---
title: 'NHDK 程式暑期培訓營'
disqus: hackmd
---

NHDK 程式暑期培訓營
===

[TOC]


# 模板
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define pll pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define sz(s) (int)s.size()
#define max(p,q)((p)>(q)?(p):(q))
#define fast ios::sync_with_stdio(0), cin.tie(0)
#define N 10000000
#define MOD 1000000007
struct P{
    int x, y, t;
    P(){}
    P(int x, int y):x(x), y(y){}
    P(int x, int y, int t):x(x), y(y), t(t){}
    int operator-(const P r)const{return abs(x-r.x)+abs(y-r.y);}//曼哈頓距離
};

int main() {
  fast;cout.tie(0);
  return 0;
}
```

## 遞迴

### 遞迴 [zero judge f640: 函數運算式求值](https://zerojudge.tw/ShowProblem?problemid=f640)
:::info
解題關鍵:
用遞迴解!!
:::
```csharp=
#include <iostream>
#include <string>
using namespace std;
int eval(){
    string s;
    cin>>s;
    if (s[0]=='f') {
        int x=eval(); //要宣告在區域，不然宣告在全域會賦值
        return 2*x-3;
    } 
    else if(s[0]=='g') {
        int x=eval();
        int y=eval();
        return 2*x+y-7;
    } 
    else if(s[0]=='h') {
        int x=eval();
        int y=eval();
        int z=eval();
        return 3*x-2*y+z;
    } 
    else  return stoi(s);
}
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(0);
    cout<<eval()<<endl;
    return 0;
}
```

## 競賽入門
* 時間複雜度可看成程式的規模
### 前綴和　[TPR #23 H2 區間求和問題【Two-dimensional Version】(2*)](https://codeforces.com/group/H0qY3QmnOW/contest/383582/problem/H2)
:::info
解題關鍵:
題目超長，重點只有幾句話:
* 求$(x_1,y_1)$到$(x_2,y_2)$所圍成的矩形內(包括邊上)的所有數字和。
* 其值=(0,0)∼$(x_2,y_2)$ 的總和扣掉 (0,0)∼$(x_1−1,y_2)$ 的總和再扣掉 (0,0)∼$(x_2,y_1−1)$ 的總和，最後再加上 $(x_1−1,y_1−1)$ (多扣掉的要加回來)。
* 關於上式的推導，可以用矩形面積來思考。
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define maxi 2600
ll mp[maxi][maxi],pre[maxi][maxi];
ll q,n,m,x_1,y_1,x_2,y_2;

int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)
      cin>>mp[i][j];
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)
      pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+mp[i][j];
  }
  cin>>q;
  while(q--){
    cin>>x_1>>y_1>>x_2>>y_2;
    cout<<pre[x_2+1][y_2+1]+pre[x_1][y_1]-pre[x_1][y_2+1]-pre[x_2+1][y_1]<<endl;
  }
  return 0;
}
```
### 前綴和ZJ b844: 一堆按鈕(3*)
:::success
可能卡關的點:
如果我們每輸入一個數字K就要reset一次array，輸入完的複雜度會是O($n^2$)。接著再查詢Q次，總體複雜度會是O($n^2$+Q)，然後就會吃TLE拉。
:::

:::info
解題關鍵:
如果我們把輸入的數值K都先由小至大sort，那我們就可以推算數字a到底是0還是1(只要知道按a~n的按鈕的奇偶性即可)
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 500005
ll n,q,i,u,k;
vector<ll> v;
ll q_v[N]; //存按過按鈕的點

int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  while(cin>>n>>q){
    v.clear(); ///記得要clear()他
    for(i=1;i<=n;i++){
      cin>>k;
      v.push_back(k);
    }
    sort(v.begin(),v.end()); //小至大sort
    for(i=0;i<q;i++){ 
      cin>>q_v[i];
      u=upper_bound(v.begin(),v.end(),q_v[i])-v.begin(); //記得-v.beign()
    //因為以後有包含=，所以要用沒有=的func.
      if(u%2==0) cout<<0<<'\n';
      else cout<<1<<'\n';
    }
  }
  return 0;
}
```
## 資料結構I
### vector 2022年1月APCS第二題
[h082: 2. 贏家預測-1(4*)](https://zerojudge.tw/ShowProblem?problemid=h082)
:::info
解題關鍵:
開三個vector，存贏家、輸家、第i輪的參賽人員，並開一個array去紀錄每個人的失敗次數，超出m則被淘汰。
有些小細節要注意，請看程式碼的註解
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define N 1050
ll n,m,ind; 
ll x,y,a,b,c,d; //紀錄對戰者的編號、戰力、應戰力
ll s[N],t[N],lose[N]; //戰力\應戰力\編號
vector<ll> vw,vl,v;
//贏家編號\輸家編號\每個人輸了幾次\每輪玩家編號

int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++) cin>>s[i];
  for(int i=1;i<=n;i++) cin>>t[i];
  for(int i=0;i<n;i++) {
    cin>>ind;
    v.push_back(ind);
  }//第一輪玩家編號
  while(v.size()>1){//每輪遊玩人數>1
    for(int i=0;i<v.size()-1;i+=2){//兩個一組pk
      x=v[i];y=v[i+1];
      a=s[x];b=t[x];c=s[y];d=t[y];
      //不要寫成s[i]，因為s[i]不一定是指第i個人的戰力
      if(a*b>=c*d){
        s[x]=a+(c*d)/(2*b); 
        t[x]=b+(c*d)/(2*a);
        s[y]=c+c/2;
        t[y]=d+d/2;
        lose[y]++;
        vw.push_back(x);
        if(lose[y]<m)vl.push_back(y);
        //失敗次數不超出m，超出m則淘汰(不會進入敗部復活)
      }
      else{
        s[y]=c+(a*b)/(2*d); 
        t[y]=d+(a*b)/(2*c);
        s[x]=a+a/2;
        t[x]=b+b/2;
        vw.push_back(y);
        lose[x]++;
        if(lose[x]<m)vl.push_back(x);
      }
    }
   if(v.size()%2==1) vw.push_back(v.back());
   //落單直接晉級   
   v=vw;
   for(ll j:vl) v.push_back(j);
   vw.clear();
   vl.clear();
  }
  cout<<v[0]<<'\n';
  return 0;
}
```
### priority_queue [TPR #7 PC 中位數 (3*)](https://www.google.com/url?q=https://codeforces.com/group/H0qY3QmnOW/contest/316436/problem/C&sa=D&source=editors&ust=1659524344077458&usg=AOvVaw3uemvuuLyfJFhcD4ADvAv_)
:::info
解題關鍵:
算中位數需要把序列由小至大排列，使序列具有某種單調性，同時元素可能會重複=>所以選擇priority_queue實作啊!

我們可以把元素分成兩半，左邊放小的，右邊放大的。
讓max{左邊數字}<=({右邊數字})、左邊的數字比右邊的數字多，因為這樣可以直接開top算出中位數。
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
priority_queue<int,vector<int>,less<int>> pq_l;
priority_queue<int,vector<int>,greater<int>> pq_r;
//注意優先佇列沒有pq[i]這種東西 
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  int a;
  while(cin>>a){
    if(a==0) break;
    if(pq_l.empty() || a<=pq_l.top()) pq_l.push(a);
    else  pq_r.push(a);
    while(pq_l.size()>pq_r.size()){
      pq_r.push(pq_l.top());
      pq_l.pop();
    }
    while(pq_r.size()>pq_l.size()){ //確保左邊的數字比較多
      pq_l.push(pq_r.top());
      pq_r.pop();
    }
    if(pq_r.size()==pq_l.size()) 
      cout<<(pq_r.top()+pq_l.top())/2<<'\n';
    else cout<<pq_l.top()<<'\n';
  }  
  return 0;
```
### set [d129: 00136 - Ugly Numbers](https://zerojudge.tw/ShowProblem?problemid=d129)
:::success
可能卡關的點--要用什麼資料結構呢?
原題等價於求$2^a 3^b 5^c$($a,b,c \in Z$)第1500大的數字。
最直觀的方法就是枚舉原本資料結構所有元素，再加入這些元素*2、*3、*5的元素，然後刪掉重複的元素，並按照大小排列。複雜度直接炸開(指數成長)。想起set具有"刪掉重複的元素"、"按照大小排列"的特性，所以當然用set阿!!
同時如果s.size()>=1499也沒差。
:::
:::info
解題關鍵:
注意
* set沒有set[i]這種東西，只能用指標*it代表它的值
* s.begin()、s.end()是一種疊代器interator
* auto可以自動判別型體，就不用寫interator了
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 1e9
set<ll> s;
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  s.insert(1);
  ll cnt=0;
  for(auto it=s.begin();it!=s.end();it++){
    cnt++;
    if(cnt==1500) {
      cout<<"The 1500'th ugly number is "<<*it<<".";
      break;
    }
    s.insert(*it *2);//*interator=ptr
    s.insert(*it *3);
    s.insert(*it *5);
  }
  return 0;
}
```
### set h083: 3. 數位占卜 2022年1月APCS第三題
[h083: 3. 數位占卜](https://zerojudge.tw/ShowProblem?problemid=h083)
:::info
解題關鍵:
1. 設字串P可與字串B形成｢聖杯｣，則P必可切割成sl、B、sr。
稍微比對一下，可推知sl=sr。
2. s.substr(l.r)範圍是[l,r) 
3. binary_search回傳bool值(值存在回傳1，反之回傳0)
4. O(n*s.size()*log s.size())=O($10^7$)，不會TLE。
5. 因為對於任意兩個相異的字串s[i]、s[j]，s[i]!=s[j]。
所以sl.size()=sr.size()>0、B.size()>0
⇒sl.size()+sr.size()=2*len<P.size。
6. 字串的sort是按照a~z的順序下去排，先比對第一個元素，一路比對到第n個元素。
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 1e9
ll m;
string s,st,sl,sr,B;
vector<string> str;

int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  ll ans=0;
  cin>>m;
  for(int i=0;i<m;i++){
    cin>>st;
    str.push_back(st);
  }
  sort(str.begin(),str.end());
  for(int i=0;i<m;i++){
    s=str[i];
    for(int len=1;len*2<s.size();len++){
      sl=s.substr(0,len);
      sr=s.substr(s.size()-len);
      if(sl!=sr) continue;
      B=s.substr(len,s.size()-(2*len));
      if(binary_search(str.begin(),str.end(),B))
        ans++;
    }
```
### bitset [C - Jumping Takahashi(2*)](https://atcoder.jp/contests/abc240/tasks/abc240_c)
:::info
解題關鍵
* 怎麼判斷在第i步驟，可不可以跳到第j個數字呢?
因為第i步一定是由前一步跳a或b步而來，所以只要去遞迴他就行了。
可以開一個大小為(n+1)的資料結構，來知道在第i步驟，可不可以跳到第j個數字，而因為記錄的數字不超過20000($a*100+b*100$)個數字，所以每個子資料結構的大小可以開20000，紀錄每個子資料結構的第j個值是否可以跳到。
阿因為範圍固定，然後又只要知道可不可以達成，所以開一個具有bool性質的資料結構--bitset
* bitset需要先宣告大小，可初始化成數字、串列、字元等
* 位元運算
跳a或b步，可以想像成位元往左跳了a或b格，所以用"<<"阿。


:::
```csharp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bitset<20000> vis[101];
//宣告101個陣列 長度為20000(maxi:100*100+100*100)
//,並初始化為0
//判斷第i步驟是否會跳到j(1<=j<=20000)

int main(){
  vis[0][0]=1;
  ll n,x,a,b;
  cin>>n>>x;
  for(ll i=1;i<=n;i++){
    cin>>a>>b;
    vis[i]=vis[i-1]<<a|vis[i-1]<<b;
//<< 和 >> 將一個變數的所有位元向左 / 向右移動。最左位元 / 最右位元消失，最右位元 / 最左位元補 0 //一定要跳a或b步 
// "|"位元的or，因為第i步可以由第(i-1)步跳a或b步而來，所以取or
  }
  if(vis[n][x]) cout<<"Yes"<<'\n';
//像是stack，越右邊(早)索引值越大
  else cout<<"No"<<'\n';
  return 0;
}
```
### bitset [zj f630: 5. 共同朋友(3*)](https://zerojudge.tw/ShowProblem?problemid=f630)
:::info
解題關鍵:
* 我們要去得知兩人是否有共同好友，只需要開兩個bitset去紀錄兩人的共同好友，兩個bitset取&(取兩者好友的交集)(注意道自己跟自己不能為好友，所以某A跟某B共同好友不可能擁有A或B)(因此，共同好友必定與本身互斥，所以取完&不用檢驗c=a或b)，然後再看取完&的bitset是否為全0的bit就行啦
* 不能用count!!!(因為時間複雜度是$O(n^3)$,會炸開)，
要改成用.any()(時間複雜度$O(1)$)
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define MAXI 2600
bitset<MAXI> k[2600];
ll n,d,f,cnt;

int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  cin>>n;
  for(ll i=1;i<=n;i++){
    cin>>d;
    for(ll j=1;j<=d;j++){
      cin>>f;
      k[i][f]=true;
    }
  }
  cnt=0;
  for(ll a=1;a<n;a++){
    for(ll b=a+1;b<=n;b++){ //因為b>a
      if((k[a]&k[b]).any()!=0)cnt+=1; 
      //兩者好友關係取完and不為全0 bit
      //any函式:如果有存在一個bit不為0，則回傳1，否則回傳0
    }
  }
  cout<<cnt;
  return 0;
}
```
## 枚舉
### 枚舉所有操作 TNGS IRC Final Exam pE. 倒水問題(2*)
:::info
解題關鍵:
看到a、b的執行次數至多為10，直接砸兩個for loop也不會TLE阿~
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 1000000
ll mini,n,k,a,b;
ll p1,p2,x;
ll i,j;

int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  mini=N; //所剩差距
  cin>>n>>k>>a>>b;
  for(j=0;j<=10;j++){
    for(i=0;i<=10;i++){
      x=i*a+j*b;
      if(n-x>=k && n-x-k<mini){
          mini=n-x-k;
          p1=i;
          p2=j;
      }
    }
  }
  cout<<p1<<" "<<p2<<" "<<mini<<'\n';
  return 0;
}
```
### 位元枚舉 [CSES Problem Set Apple Division(2*)](https://cses.fi/problemset/task/1623/)
:::warning
位元相關知識
1. x & 1 is equivalent to x % 2.
舉例:當x=1011，1=0001，每個位置做and的結果是0001=1，相當於x的奇偶性。
2. <<、>>分別為左移運算子，右移運算子。
3. 1<<x，相當於1向左位移x格
舉例:當x=3。1<<x其值為0001
4. x=x>>1，可簡寫成x>>=1(右移並附值)
:::
:::info
因為分推方法數至多為$2^{20}$，所以窮舉他吧。
注意到同一物件分堆情形數有二，所以只要用0、1表示他被分在哪堆即可。
而至多有n件物品，所以窮舉0~$2^n-1$即可。
(全部分在左邊~全部分在右邊)
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 1e12
ll apple[25],total,n,gap=N,num,i,p,rt,rl,idx;
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  total=0;
  cin>>n;
  for(i=0;i<n;i++) {
    cin>>apple[i];
    total+=apple[i];
  }
  p=pow(2,n);
  for(i=0;i<p;i++){
    num=i;
    idx=0;
    rt=0;
    rl=0;
    while(num!=0){
      if((num&1)==0) rt+=apple[idx];
      idx++;
      num/=2;
    }
    rl=total-rt;
    gap=min(gap,abs(rl-rt));
  }
  cout<<gap<<'\n';
  return 0;
}
```
### 全排列枚舉 [Zerojudge e446 排列生成(2*)](https://zerojudge.tw/ShowProblem?problemid=e446)
:::info
解題關鍵:
你只要知道next_permutation這個內建函式就秒殺了，
值得一提的是這個函式很常搭配do-while loop。
這個loop需要先寫的事項，再寫條件
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 1e9
vector<ll> a;
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  ll n;
  cin>>n;
  a.clear();
  for(ll i=1;i<=n;i++) a.push_back(i);
  do{
    for(ll i=0;i<n;i++) cout<<a[i]<<" "; //要排列的對象
    cout<<'\n';
  }while(next_permutation(a.begin(),a.end()));
  //全排列函式//對[first,end)做排列
  return 0;
}
```
### 有限度的枚舉 [Ten Point Round #20 飲品調配(2*)](https://codeforces.com/group/H0qY3QmnOW/contest/377732/problem/A)
:::info
解題關鍵:
因為c=n-a-b、$a \leq n \leq 5000$,$b \leq n \leq 5000$。
又發現枚舉a、b的複雜度為$O(n^2)$，不會炸開，那就直接枚舉吧!
* 有O(1)作法:取a=0=b、c=n。(超級梗)
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
ll a,b,c,mint=-1,n,t;
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  cin>>n;
  for(a=0;a<=n;a++){
    for(b=0;b<=n-a;b++){
      c=n-a-b;
      t=2022+abs(b-c)+c*c+a*b+b*c-abs(b*b-a*a);
      mint=max(mint,t);
    }
  }
  cout<<mint<<'\n';
  return 0;
}
```
### 枚舉答案 [CSES Problem Set Common Divisors(4*)](https://cses.fi/problemset/task/1081/)
:::success
可能卡關的點:
1. 枚舉$x_i$、$x_j$，時間複雜度為$O(n^2log(min(x_i, x_j)))$。(炸開)
2. 假設i<j，枚舉$x_i$、$x_j$，時間複雜度為$O(n^2log(min(x_i, x_j)))$。(炸開)

所以上述方法都行不通。
:::
:::info
解題關鍵:
假設a<b，gcd(a,b)=k的充要條件為a,b同時等於k或2k或3k....。
所以我們只要枚舉k，再確認a,b可不可以同時為k或2k或3k.... 。
時間複雜度為$O(\frac{n}{1}+\frac{n}{2}+...+\frac{n}{n})=O(nlogn)$。這樣就不會TLE了!!(注意因為兩個for迴圈是相關的，時間複雜度!=$O(n*nlogn)$)
至於怎麼知道a,b可不可以同時為k或2k或3k....，開一個bool陣列去紀錄數字有沒有出現過就行了!!
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 1000005
ll num[N];
ll n,x,g;
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  cin>>n;
  for(ll i=0;i<n;i++){
    cin>>x;
    num[x]++;//紀錄每個數字出現的次數
  }
  g=1;
  for(ll i=1;i<N;i++){
    ll cnt=0;
    for(int j=i;j<N;j+=i){
      cnt+=num[j];//注意數字可能會重複出現
    }
    if(cnt>=2) g=i;
  }
  cout<<g<<'\n';
  return 0;
}
```
### BFS模板 [Zerojudge d406: 倒水時間](https://zerojudge.tw/ShowProblem?problemid=d406)(3*)
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define pll pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define sz(a) (int)s.size()
#define max(p,q)((p)>(q)?(p):(q))
#define fast ios::sync_with_stdio(0), cin.tie(0)
#define N 10000000
#define MOD 1000000007
ll G[110][110],vis[110][110],ans[110][110];
queue<pll> qu;
ll dx[4]={0,1,-1,0};
ll dy[4]={1,0,0,-1};
int main() {
  ll n,m,num,k,sta,cnt=1;
  fast;cout.tie(0);
  while(cin>>k>>n>>m){
    for(ll i=0;i<n;i++) for(ll j=0;j<m;j++) {ans[i][j]=0;vis[i][j]=0;}
    for(ll i=0;i<n;i++){
      for(ll j=0;j<m;j++){
        cin>>G[i][j];
      }
    }
    for(ll j=0;j<m;j++) if(G[0][j]==1) sta=j;
    qu.push(mp(0,sta));
    vis[0][sta]=1;
    ans[0][sta]=1;
    while(!qu.empty()){
      pll cur=qu.front();qu.pop();
      ll x=cur.first;
      ll y=cur.second;
      //cout<<"x="<<x<<"y="<<y<<endl;
      for(ll i=0;i<4;i++){
        if(k==2 && i==2) continue;
        ll nx=x+dx[i],ny=y+dy[i];
        if((-1<nx && nx<n)&&(-1<ny && ny<m) && vis[nx][ny]==0 && G[nx][ny]==1){
          //cout<<"nx="<<nx<<"ny="<<ny<<'\n';
          //cout<<"YES\n";
          vis[nx][ny]=1;
          ans[nx][ny]=ans[x][y]+1;
          qu.push(mp(nx,ny));
        }
      }
    }
    cout<<"Case "<<cnt<<":\n";
    for(ll i=0;i<n;i++){
      for(ll j=0;j<m;j++){
        cout<<ans[i][j]<<" ";
      }
      cout<<"\n";
    }
    cnt+=1;
  }
  return 0;
}
```
## 搜尋
### 二分搜尋 [Codeforces EDU A. Binary Search(2*)](https://codeforces.com/edu/course/2/lesson/6/1/practice/contest/283911/problem/A)
:::info
這題只要知道binary_search函式就能秒殺了。
自己手刻一個函式還需要去驗在左還右界，還是開絕招比較容易!
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 100005
ll n,k,q,left,right,mid;
vector<ll> a;
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  cin>>n>>k;
  for(ll i=0,b;i<n;i++) {cin>>b;a.push_back(b);}
  sort(a.begin(),a.end());
  while(k--){
    cin>>q;
    if(binary_search(a.begin(),a.end(),q)) 
      cout<<"YES"<<'\n';
    else cout<<"NO"<<'\n';
  }
  return 0;
}
```
### 雙指針 [CSES Problem Set Sum of Three Values(3*)](https://cses.fi/problemset/task/1641)
:::info
破題關鍵:
注意到如果直接寫的話，複雜度為$O(n^3)$。
$\because n<=5000$，帶入進去$O(n^3)=1.25*10^{11}$
$∴$炸開拉。
所以我們可以換個想法，我們可以對其中兩個數開雙指針$(O(n^2))$，剩下一個我們只要開lower_bound$(O(log n))$二分搜他就行了阿~
有一些點注意:
①同一個數字不能取兩次
②小心lower_bound不存在的時候會回傳size+1，所以要判斷lower_bound是否存在
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 1e9
ll x,n,A,m,i,j;
vector<pair<ll,ll>> a;
vector<ll> num;

int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  bool yes=0;
  cin>>n>>x;
  for(ll i=0;i<n;i++){
    cin>>A;
    a.push_back({A,i+1});
  } 
  sort(a.begin(),a.end());
  for(i=0;i<n;i++) num.push_back(a[i].first);
  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      m=lower_bound(num.begin(),num.end(),x-num[i]-num[j])-num.begin();  
      if(i==m && num[m]==num[m+1] && m+1<n)m+=1;
      if(m!=i && m!=j && m<n && num[i]+num[m]+num[j]==x){ 
          
        yes=1;
        cout<<a[i].second<<" "<<a[m].second<<" "<<a[j].second<<'\n';
        break;
      }
    }
  }
  if(yes==0) cout<<"IMPOSSIBLE\n";
  return 0;
}
```
## 分治
0,
:::info
解題關鍵:
可以用merge sort來解決他，而merge sort的方法正是分治的精神--
1. 大問題切割成小問題(利用遞迴)
2. 破解小問題(在小到某一程度也能使用暴力解)
3. 小問題合併成大問題

相信遞迴的力量!
:::
```csharp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000005
ll n;
ll a[N];
int main(){
  while(cin>>n){
    for(ll i=0;i<n;i++){
      cin>>a[i];
    }
    sort(a,a+n);
    for(ll i=0;i<n;i++){
      cout<<a[i]<<" ";
    }
    cout<<'\n';
  }
  return 0;
}
```
## 數學
**快速幂**
時間複雜度O($log_2$次方)
程式碼(推導請參考wiki) 
記憶方法:很像是$n^p=(n^2)^{\frac{p} {2}}$
```csharp=
int fastpow(int n,int p){
    int res=1;
    while(p){
        if(p&1) res=res*n%mod; //p等於1嗎//返回n%mod
        n=n*n%mod;
        p/=2; //做log_2 p次
    }
    return res;
}
```
### 快速幂 CSES - Exponentiation(2*)
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define mod 1000000007

ll fastpow(ll a,ll b){
  int res=1;
  while(b){
    if(b&1) res=res*a%mod;
    a=a*a%mod;
    b/=2;
  }
  return res;
}
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  ll a,b,n;
  cin>>n;
  while(n--){
    cin>>a>>b;
    if(a==0 & b==0) cout<<1<<'\n';
    else if(a==0) cout<<0<<'\n';
    else{
      cout<<fastpow(a,b)<<'\n';
    }
  }
  return 0;
}

```
**費馬小定理**
:::warning
敘述:設a屬於正整數、P屬於質數，則$a^{P-1}≡1(mod P)$
(反之不然)
證明:我懶之後補。
:::

### 費馬小定理 CSES Problem Set Exponentiation II(2*)
:::info
解題關鍵:
令k=b^c mod (P-1)，由費馬小定理可以得知
$a^{b^c}≡a^k$($\because a^{b^c}=a^k* a^{P-1} *...* a^{P-1}≡a^k*1*...*1(mod P)$)
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define P 1000000007
#define N 1000000006

ll fastpow(ll a,ll b,ll c){
  ll res=1;
  if(a==0 && b==0) return 1;
  else if(a==0) return 0;
  else{
    while(b){
      if(b&1) res=res*a%c;
      a=a*a%c;
      b/=2;
    }
    return res;
  }
}
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  ll n,x,y,z;
  cin>>n;
  while(n--){
    cin>>x>>y>>z;
    cout<<fastpow(x,fastpow(y,z,N),P)<<'\n';
  }
  return 0;
}
```
### 歐拉函數 [ETF - Euler Totient Function(3*)](https://www.spoj.com/problems/ETF/)
:::info
解題關鍵
注意到歐拉函數有一個性質--
若一大於1的正整數a，可質因數分解成$a=p_1^{\alpha_1}*p_2^{\alpha_2}*...*p_n^{\alpha_n}$，則φ(a)=a$\Pi_{k=1}^n(1-\frac{1}{p_k})$。
注意到$p_k|a$，所以先除再乘也沒差~(比較不容易超出range)
:::

```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 1e9

ll eft(int n){
  ll ans=n;
  for(int i=2;i*i<=n;i++){
    if(n%i==0) ans=ans/i*(i-1);
    while(n%i==0) n/=i;
  }
  if(n>1) ans=ans/n*(n-1); //當n為質數時,其因數為本身和1
  return ans;
}
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  ll n,q;
  cin>>n;
  while(n--){
    cin>>q;
    cout<<eft(q)<<'\n';
  }
  return 0;
}
```

## 動態規劃(一)
### 線性DP [CSES Problem Set Dice Combinations(2*)](https://cses.fi/problemset/task/1633)
:::info
解題關鍵:
dp[i]可分別由dp[i-1]、dp[i-2]、dp[i-3]、dp[i-4]、dp[i-5]、dp[i-6]跳1、2、3、4、5、6點而來。(但這只有適用於i>=6時)
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define MAXI 1000010
ll n;
ll dp[MAXI];//湊出點數i的可能情形
int main() {
  cin>>n;
  dp[0]=1;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=min(i,6);j++){
      //要取min不然可能會爆(點數太多)
      dp[i]+=dp[i-j];
      dp[i]%=mod;
    }
  }
  cout<<dp[n]<<'\n';
  return 0;
}
```
### 線性DP [CSES Problem Set Minimizing Coins(2*)](https://cses.fi/problemset/result/4349093/)
:::info
破題關鍵:
dp[i]:=湊出第i個值，所需要的最少硬幣數
第i個值可由$i-C_0$、$i-C_1$、...、$i-C_n$，分別加上$C_0$、$C_1$、...、$C_n$硬幣(硬幣數+1)湊出。
所以$dp[i]=min(dp[i-C_0],dp[i-C_1],...,dp[i-C_n])+1$
$=min(dp[i],dp[i-c_j]+1)$，記得判斷索引值>=0的case。
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXI 1000005 //陣列開太大會RE
#define coin 105
ll n,x,in;
ll dp[MAXI],c[coin];//湊出點數i的可能情形之方法數

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin>>n>>x;
  memset(dp, 0x3F, sizeof(dp));
  dp[0]=0;
  for(int i=0;i<n;i++){
    cin>>c[i];
  }
  for(int i=0;i<=x;i++){
    for(int j=0;j<n;j++){
      if(i-c[j]>=0){
        dp[i]=min(dp[i],dp[i-c[j]]+1);
      }
    }
  }
  if(dp[x]>x)cout<<-1<<'\n'; //dp[x]等於0x3f時
  else cout<<dp[x]<<'\n';
  return 0;
}
```

### 線性DP [CSES Problem Set Grid Paths(2*)](https://cses.fi/problemset/task/1638/)
:::info
解題關鍵:
i+c[j]點是由i點加上c[j]點而來，所以dp[i+c[j]]=dp[i];。
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define MOD 1000000007
ll n,x,c[110],dp[1000010];

int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  cin>>n>>x;
  dp[0]=1;
  for(int i=0;i<n;i++) cin>>c[i]; 
  //注意幣值相同的硬幣視為相異
  for(int i=0;i<x;i++){
    for(int j=0;j<n;j++){
      if(i+c[j]>x) continue;
      dp[i+c[j]]+=dp[i];
      dp[i+c[j]]%=MOD;    
    }
  }
  cout<<dp[x]<<'\n';
  return 0;
}
```
### 線性DP [CSES Problem Set Coin Combinations I(5*)](https://cses.fi/problemset/task/1635/)
:::info
破題關鍵:
因為只能往右或上有，所以轉移式
* dp[i][j]=dp[i][j-1]+dp[i-1][j]

但記得要判斷起點(1,1)的情形，可能可以走(方法數=1)，或者不能走(方法數=0)，不能用轉移式遞迴得到!!!
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define MAXI 1010
#define mod 1000000007

int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  ll n,i,j;
  cin>>n;
  string map[MAXI];//char陣列只有1維的 //map:建圖
  ll dp[MAXI][MAXI]; 
  memset(dp,0,MAXI);//初始化成0
  for(i=1;i<=n;i++){
    cin>>map[i];
    for(j=1;j<=n;j++){
      if(i==1&&j==1){
        if(map[i][j-1]=='*') dp[1][1]=0; 
        else dp[1][1]=1;
        continue;
        //要寫continue，不然會做下列事情，dp[1][1]會變成遞迴而得。
        //但dp起點不能由遞迴而得!!       
      }
      if(map[i][j-1]=='*') continue;
      dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod;
    }
  }
  cout<<dp[n][n]<<endl;
  return 0;
}
```
### 線性DP [Atcoder DP Contest pE. Knapsack 2(3*)](https://atcoder.jp/contests/dp/tasks/dp_e)
:::info
解題關鍵:
1. 定義dp[i]
dp[i]定義成湊出背包價值為i時，所需的最小重量。
注意到:如果定義dp[i]為當重量為i時的最大價值，很容易加一加然後
2. 列出轉移式 dp[j]=min(dp[j-v[i]]+w[i],dp[j]);
 dp[j]可能由dp[j-v[i]]+w[i] (取第i件物品)而來，或是原來的dp[j] (不取第i件物品)而來。
3. 利用迴圈遞迴
注意要從價值為W開始往回算，不然可會會重複算到，變成無限背包問題。
4. 計算在背包重量$\leq$W的條件下，所能獲得地最大價值。
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  ll N,W;
  ll v[1005],w[1005];
  ll dp[1000001]; //dp[i]代表湊出背包價值為i時的最小重量
  fill(dp,dp+100001,1e18);  //取min，記得要先初始化成很大的數字
  dp[0]=0;
  cin>>N>>W;
  for(ll i=1;i<=N;i++){
    cin>>w[i]>>v[i];
    for(ll j=100000;j>=v[i];j--){//轉移後背包價值不能為負值
      dp[j]=min(dp[j],dp[j-v[i]]+w[i]); //列出轉移式
    }
  }
  ll ans=0;//計算在背包重量<=W的條件下，所能獲得地最大價值
  for(ll i=0;i<=100000;i++) if(dp[i]<=W) ans=max(ans,i);//最大可能的價值
  cout<<ans<<'\n';
  return 0;
}
```
## 圖論一
### dfs [CSES Problem Set Building Roads(2*)](https://cses.fi/problemset/task/1666/)
:::info
解題關鍵:
(相鄰:=只需要走一條edge就能到達)
* dfs精神
1. 呼叫起點
2. 枚舉起點所有相鄰連通城市
3. 枚舉符合條件2的所有城市

按上面三步驟，就能知道與起點相鄰的所有連通城市。

接著再來枚舉所有城市，如果與1不相鄰通者，就建路。
接著把建路的城市dfs，得知建路後與1相鄰的所有城市，同理，
做完所有城市。
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define MAXI 200010
vector<ll> G[MAXI];
//G[i]紀錄第i座城市和哪些城市是connection的
bool vis[MAXI];//記錄哪些城市被dfs過，dfs過表是連通
ll n,m,a,b; 
vector<pair<ll,ll>> ans; //紀錄哪些路要被建

int dfs(ll i){ //遍歷第i張圖
  vis[i]=true; //dfs第i座城市
  for(ll e:G[i]){ 
//枚舉與i相鄰的城市e=1~n，dfs第i座城市的所有相鄰連通城市
    if(!vis[e]){ //如果它沒被dfs過，就dfs他，把連通但不相鄰i的城市枚舉
      dfs(e); //枚舉與i連通，但不相鄰連通的城市
    }
  }
  return 0; //記得就算不用return，還是要return。
}
//整個做完，如果第j個跟第i城市是相鄰的，vis[j]=1
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  cin>>n>>m;
  for(ll i=1;i<=m;i++){ //建m條路
    cin>>a>>b;
    G[a].push_back(b);
    G[b].push_back(a); //因為是無向圖
  }
  dfs(1);//一定要有一個城市與城市1連通
  for(ll i=2;i<=n;i++){//dfs n座城市
    if(!vis[i]){ 
  //如果第i個城市不與1連通，需要一條edge使其連通
      ans.push_back({1,i}); //蓋城市
      dfs(i);//找到與i連通的所有城市
    }
  }
  cout<<ans.size()<<"\n";
  for(auto it:ans) 
    cout<<it.first<<" "<<it.second<<'\n';
  return 0;
}
```
### DFS [TIOJ 1152 銀河帝國旅行社(4*)](https://tioj.ck.tp.edu.tw/problems/1152)
:::info
解題關鍵:
看到這題不難覺得要開DFS，但是要知道最遠距離，該怎麼修改扣呢?(直接看扣理解)
注意事項
* 某個點u，經過點i，走到點v的距離d(u,i,v)怎麼算呢，首先先看i為根結點的情形，距離d(u,i,v)=dep(u)+dep(v)-2。再看i深度=2的情形，距離d(u,i,v)=dep(u)+dep(v)-2*dep(i)。
* 有了這個關係式，接著思考何時d(u,i,v)有maxi。
得知當dep(i)=0、dep(v)、dep(u)時，距離有maxi
* 接著我們去dfs整張圖，並記錄最大跟次大深度dep(u)、dep(v)，用pair<ll,ll> mx(並要求mx.first $\ge$mx.second)存取。
* 每次dfs回傳最大深度mx.first
:::
```csharp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXI 10005
ll n,ans=0,a;
ll d[MAXI];
vector<ll> G[MAXI];
ll dfs(ll i,ll dep){//回傳最大深度
  d[i]=dep;//記錄每點的深度，雖本題不需要知道
  pair<ll,ll> mx(dep,dep);
  //紀錄dep(u)、dep(v)，並使兩者值最大化
  for(auto e:G[i]){//dfs他
    ll tmp=dfs(e,dep+1);//依序往下dfs，每往下一次，深度+1
    if(tmp>mx.first) mx={tmp,mx.first}; 
    //把dep小的換掉，而mx.second<=mx.first，所以換掉mx.second
    else if(tmp>mx.second) mx={mx.first,tmp}; //把dep小的換掉//mx.first>=mx.second
  }
  ans=max(ans,mx.first+mx.second-2*dep);//d(u,i,v)的算法
  return mx.first;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin>>n;
  for(ll i=0;i<n;i++) 
      while(cin>>a && a>0) 
          G[i].push_back(a);
  dfs(0,1);
  cout<<ans<<'\n';
  return 0;
}
```
## DP II
### [LIS CSES - Increasing Subsequence](https://cses.fi/problemset/task/1145)
```csharp=
#include<bits/stdc++.h>
#define pb push_back
#define ll long long 
using namespace std;
vector<ll> v,dp;
int main(){
  ios::sync_with_stdio(false);
  cin.tie();
  ll n;
  cin>>n;
  vector<ll> point(n);
  for(ll i=0;i<n;i++) {
    cin>>point[i];
    ll ind=lower_bound(v.begin(),v.end(),point[i])-v.begin();
    if(v.empty() || ind>=(ll)v.size()) v.pb(point[i]);
    else v[ind]=point[i];
  }
  cout<<v.size();
  return 0;
}
```
### [LIS APCS 2021 一月場 p4 - 飛黃騰達 (4*)](https://zerojudge.tw/ShowProblem?problemid=f608)
:::info
先對(x,y)排序，然後對y做嚴格LIS。
如何實作LIS
1. 定義v[j]為當dp[i]=j時，$a_i$的最小值。
2. 注意到v[j]為遞增序列，加入新點時，對v做二分搜，把$a_i$插入
:::
```csharp=
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
using namespace std;
vector<ll> v;
vector<pll> point;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  ll n;cin>>n;
  for(ll i=0;i<n;i++){
    ll x,y;
    cin>>x>>y;
    point.pb(mp(x,y));
  }
  sort(point.begin(),point.end());
  for(ll i=0;i<n;i++){
    ll ind=upper_bound(v.begin(),v.end(),point[i].S)-v.begin();//嚴格遞增子序列
    if(v.empty() || ind>=v.size()) v.pb(point[i].S);
    else v[ind]=point[i].S;//因為v[ind+1]>=arr[i]
  }
  cout<<v.size()<<'\n';
  return 0;
}
```
## 計算幾何
### 向量應用 [CSES Problem Set Polygon Area(2*)](https://cses.fi/problemset/task/2191)
:::info
破題關鍵:
怎麼用程式算平面圖形的面積呢?
開鞋帶公式(測量師公式)
:::
```csharp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> x,y;
ll n;

int main() {
  cin>>n;
  ll area=0;
  for(int i=1,a,b;i<=n;i++){
    cin>>a;
    x.push_back(a);
    cin>>b;
    y.push_back(b);
  }
  x.push_back(x[0]);y.push_back(y[0]);
  for(int i=0;i<=n-1;i++){
    area+=x[i]*y[i+1];
    area-=y[i]*x[i+1];
  }
  cout<<abs(area)<<endl;
  return 0;
}
```