---
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;
}
```
Sign in with Wallet
Connect another wallet