# 程式設計 筆記
## Table of Contents
[TOC]
# Data Structure
---
## 位元運算技巧
^ 消除相同
找2進位下從左邊數來第一個1的位置 -> a & -a (補數的關係)
## bitset
宣告長度為n的bitset陣列
bitset<n> b
n 必須是const int，不可使用變數宣告
bitset 實際儲存陣列與輸出,to_string等是相反的
bitset<10>
輸出bitset 0101010101
實際陣列 1010101010
陣列註標 9876543210
```cpp
建構子
unsigned int
bitset<32> bs(a)
將a轉為二進制存在bs裡面
ex:
a=0xffff
bs ->
實際: 1111 1111 1111 1111 0000 0000 0000 0000
輸出: 0000 0000 0000 0000 1111 1111 1111 1111
string
bitset<16> bs(string)
將string讀入bs裡面
ex:
s="1100"
bs->
實際: 0011 0000 0000 0000
輸出: 0000 0000 0000 1100
bitset<> bs(s,begin)
從begin開始直到s末位讀入bs
bitset<> bs(s,begin,length)
由右往左將 substr(begin,length)由左至右讀入bs裡面
ex:
s="1100"
bitset<4> bs(s,1,2)
bs->
實際: 0100
輸出: 0010
xin>>bs 輸入
xout<<bs 輸出
bs.to_ulong() 把bitset當作binary 轉換成decimal
bs.to_string() 把bitset轉成string
bool any() 有1?
bool none() 沒有1?
size_t count() 1的數量
size_t size() 長度
bool operator[] 存取該註標的值
void set() 所有位設為1
void reset() 所有位設為0
```
---
## Binary Tree
``` cpp=1
class BinaryTree;
class TreeNode{
private:
TreeNode *leftchild;
TreeNode *rightchild;
TreeNode *parent;
char data;
public:
TreeNode():leftchild(0),rightchild(0),parent(0),data('x'){};
TreeNode(char s):leftchild(0),rightchild(0),parent(0),data(s){};
friend class BinaryTree;
};
class BinaryTree{
private:
TreeNode *root;
public:
BinaryTree():root(0){};
BinaryTree(const char* str);
void LevelorderConstruct(std::stringstream &ss);
void InsertLevelorder(char data);
TreeNode* leftmost(TreeNode *current);
TreeNode* InorderSuccessor(TreeNode *current);
void Inorder_by_parent();
};
```
---
## 樹狀數組（Binary Indexed Tree）
高效更新一個儲存數字的列表及求前綴和
1. update(idx, num)：在列表idx的位置上加num。O (logn)
```cpp=1
update(i,num)
while(i<size):
BIT[i]+=num
i+=(i&-i)
```
2. prefixSum(idx)：求从数组第一个位置到第idx（含idx）个位置所有数字的和。O(logn)
```cpp=1
prefixSum(idx)
result=0
for(int i=idx;i>0;i-(i&-i)):
result+=BIT[i]
return result
```
3. rangeSum(from_idx, to_idx)：求从数组第from_idx个位置到第to_idx个位置的所有数字的和。 O(logn)
```cpp=1
rangeSum(from_idx, to_idx)= prefixSum(to_idx) - prefixSum(from_idx)
```
4. BIT(int list[])：建構子 O(n)
```cpp=1
for i in range(0,n):
BIT[i] = list[i]
for i in range(0,n):
j=i+(i&-i)
if(j<n):
BIT[j]+=BIT[i]
```
範例
[1, 7, 3, 0, 5, 8, 3, 2, 6, 2, 1, 1, 4, 5]
sample code:
```cpp=1
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long
#define ALL(x) x.begin(),x.end()
#define INSERT(x) inserter(x,x.end())
using namespace std;
const int BIT_size=1000;
int BIT[BIT_size];
void update(int pos,int num){
while(pos<BIT_size){
BIT[pos]+=num;
pos+=(pos&(-pos));
}
}
int prefixsum(int pos){
int ans=0;
while(pos>0){
ans+=BIT[pos];
pos-=(pos&(-pos));
}
return ans;
}
int main(){
int n,m;
cin>>n>>m;
//construct
for(int i=1;i<=n;i++){
cin>>BIT[i];
}
for(int i=1;i<=n;i++){
int j=i+(i&-i);
if(j<BIT_size)
BIT[j]+=BIT[i];
}
//update
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
update(a,b);
}
//preSum
int k;
cin>>k;
cout<<prefixsum(k)<<endl;
/*
//print ALL
for(int i=1;i<=n;i++)
cout<<BIT[i]<<' ';
cout<<endl;
*/
}
/*
input:
2 integer n,m
next line consist n integer
next m lines
each line consist 2 integer a,b mean at position a plus a number b
next line consist an integer k mean print prefixsum of position k
*/
/*
14 0
1 7 3 0 5 8 3 2 6 2 1 1 4 5
5
*/
```
---
---
## complex
與一般數字類別用法大致相同
```cpp
template<class T>
complex<T> cT(real , imag);
成員函數
T real(T n) 設定實部為n，若n為void則僅回傳實部
T imag(T n) 設定虛部為n，若n為void則僅回傳虛部
```
---
## deque 雙向佇列
double ended queue
用 vector 用法大致相同，不能使用[]隨機存取
---
## inserter_iterator
用於在STL容器中插入元素
---
## The other DS
```cpp=1
// 比較類別
class cmp{
public:
bool operator()(int a,int b){return a<b;}
};
set<int,cmp> iset;
class Test{
public:
int data;
Test(int a):data(a){}
}
namespace std{
template<>
struct less<Test>{
bool operator()(const Test &t1,const Test &t2)const{return t1.data<t2.data;}
};
template<>
struct equal_to<Test>{
bool operator()(const Test &t1,const Test &t2)const{return t1.data==t2.data;}
};
}
set<Test> iset{Test(1),Test(2),Test(3),Test(3)};
```
---
# Dynamic Program
## 簡介
遞迴分割問題時，當子問題與原問題完全相同，只有數值範圍不同，我們稱此現象為 recurrence ，再度出現、一再出現之意。
此處以爬樓梯問題當作範例。先前於遞歸法章節，已經談過如何求踏法，而此處要談如何求踏法數目。
踏上第五階，只能從第四階或從第三階踏過去。因此「爬到五階」源自兩個子問題：「爬到四階」與「爬到三階」。
「爬到五階」的踏法數目，就是總合「爬到四階」與「爬到三階」的踏法數目。寫成數學式子是「 f(5) = f(4) + f(3) 」，其中「 f(‧) 」表示「爬到某階之踏法數目」。
依樣畫葫蘆，得到「 f(4) = f(3) + f(2) 」、「 f(3) = f(2) + f(1) 」。
「爬到兩階」與「爬到一階」無法再分割、沒有子問題，直接得到「 f(2) = 2 」、「 f(1) = 1 」。
整理成狀態轉移方程式
f(x) = 1, when x=1;
2, when x=2;
f(x−1)+f(x−2),when x≥3
爬到任何一階的踏法數目，都可以藉由這道遞迴公式求得。 n 代入實際數值，遞迴計算即可。
## 兌換錢幣方法數
```cpp=1
const int coin[]={1,5,10,50,100} //錢幣面額
int n; //想要兌幣的金額
for(int i=0;i<coin.size();i++)
for(int j=1;j<=n;j++)
dp[i]+=dp[i-coin[j]];
```
## LIS(Longest Increasing Subsequence)
輸入: vector s
輸出: int v.size()
```cpp=1
vector<int> v;
v.push_back(-1); //塞最小值避免空值比較
for i in range(0,s.size())
if( s[i] > v.back() )
v.push_back(s[i]);
else
for j in range(0,v.size())
if( s[i] < v[j] )
v[j] = s[i];
```
## Robinson-Schensted-Knuth Algorithm
- 字串s的第一個字元加入陣列v
- 比較目前LIS(v)的末位與字元s[i]的大小
- s[i]較大 -> 直接塞入v
- v.back()較大 -> 找出v裡面第一個比s[i]小的字元替換
- 輸出v.size()即為LIS長度
若要找出LIS序列:
建立一個與字串s同大小的陣列pos做紀錄，在s[i]被加入v時，pos紀錄其
加入的位置，最後反向查找pos即可。(若需找出第一個LIS序列，則先將字
串reverse，然後改成找longest decease subsequence)
```cpp=1
int LIS(vector<int>& s)
{
// 不得不判斷的特例
if (s.size() == 0) return 0;
// 先放入一個數字，免得稍後 v.back() 出錯。
vector<int> v;
v.push_back(s[0]);
for (int i = 1; i < s.size(); ++i)
{
int n = s[i];
if (n > v.back())
v.push_back(n);
else
*lower_bound(v.begin(), v.end(), n) = n;
}
return v.size();
}
```
```cs
舉例說明:
sequence : -7 10 9 2 3 8 8 1
temp LIS :
position :
sequence :(-7) 10 9 2 3 8 8 1
temp LIS : -7
position : 1
// -7 在 LIS 的第一個位置
sequence : -7 (10) 9 2 3 8 8 1
temp LIS : -7 10
position : 1 2
// 10 在 LIS 的第二個位置，以此類推。
sequence : -7 10 (9) 2 3 8 8 1
temp LIS : -7 9
position : 1 2 2
/* 9 成為 LIS 的潛力比 10 大, 所以以 9 代替 10 */
sequence : -7 10 9 (2) 3 8 8 1
temp LIS : -7 2
position : 1 2 2 2
/* 2 成為 LIS 的潛力比 9 大, 所以以 2 代替 9 */
sequence : -7 10 9 2 (3) 8 8 1
temp LIS : -7 2 3
position : 1 2 2 2 3
sequence : -7 10 9 2 3 (8) 8 1
temp LIS : -7 2 3 8
position : 1 2 2 2 3 4
sequence : -7 10 9 2 3 8 (8) 1
temp LIS : -7 2 3 8
position : 1 2 2 2 3 4 4
/* 8 成為 LIS 的潛力比 8 大, 所以以 8 代替 8 */
sequence : -7 10 9 2 3 8 8 (1)
temp LIS : -7 1 3 8
position : 1 2 2 2 3 4 4 2
/* 1 成為 LIS 的潛力比 2 大, 所以以 1 代替 2 */
```
## LCS(Longest Common Subsequence)
1. 求字符串x和字符串y最長共同子序列長度：略…
2. 求字符串x和字符串y最長共同子序列：略…
*空間不足用兩列跑，或2*2陣列。
將LCS轉換成2D LIS，依照第一維索引值由小到大排序，當第一維索 引值相等時，則依第二維索引值由大到小排序，再找出第二維度的LIS。
## LPS(Longest Palindromic Subsequence)
if(s[i]==s[j])
DP[i][j] =DP[i+1][j-1]+2
else
DP[i][j] = max( DP[i+1][j], DP[i][j-1])
Longest Palindromic Subsequence（最長回文子序列）
字符串s=“abbca”，求最長回文子序列和長度。
( i , j ) -> ( 0 , 1 ) -> ( 1 , 2 ) -> ( 2 , 3 ) -> … -> ( 0 , 2 ) -> ( 1 , 3 ) -> … -> ( 0 , 4 )
if s[i]==s[j] , DP[i][j] . iMaxLength = DP[i+1][j-1] . iMaxLength+2 ;
DP[i][j] . sPalindromic = s[i]+DP[i+1][j-1] . sPalindromic+s[j] ;
else if s[i]!=s[j] ,
if DP[i][j-1] . iMaxLength > DP[i+1][j] . iMaxLength ,
DP[i][j] . iMaxLength = DP[i][j-1] . iMaxLength ;
DP[i][j] . sPalindromic = DP[i][j-1] . sPalindromic ;
else if DP[i+1][j] . iMaxLength > DP[i][j-1] . iMaxLength ,
DP[i][j] . iMaxLength = DP[i+1][j] . iMaxLength ;
DP[i][j] . sPalindromic = DP[i+1][j] . sPalindromic ;
else , 相等的情況依題目要求修改;
Longest Palindromic Substring（最長回文子字串）
• 在每個字元間加入一個不會出現的字元,尋找以i為中心的最長回文
## 背包問題
sample code:
```cpp=1
int dp[1000000];
int c[55], m[110];
int sum;
void CompletePack(int c) {
for (int v = c; v <= sum / 2; ++v){
dp[v] = max(dp[v], dp[v - c] + c);
}
}
void ZeroOnePack(int c) {
for (int v = sum / 2; v >= c; --v) {
dp[v] = max(dp[v], dp[v - c] + c);
}
}
void multiplePack(int c, int m） {
if (m * c > sum / 2)
CompletePack(c);
else{
int k = 1;
while (k < m){
ZeroOnePack(k * c);
m -= k;
k <<= 1;
}
if (m != 0){
ZeroOnePack(m * c);
}
}
}
```
### 01背包
```cpp=1
void bag01(int cost,int weight) {
for(i = v; i >= cost; --i)
dp[i] = max(dp[i], dp[i-cost]+weight);
}
```
### 完全背包
```cpp=1
void complete(int cost, int weight) {
for(i = cost ; i <= v; ++i)
dp[i] = max(dp[i], dp[i - cost] + weight);
}
```
### 多重背包
```cpp=1
void multiply(int cost, int weight, int amount) {
if(cost * amount >= v)
complete(cost, weight);
else{
k = 1;
while (k < amount){
bag01(k * cost, k * weight);
amount -= k;
k += k;
}
bag01(cost * amount, weight * amount);
}
}
```
---
# Graph
---
## 最短路徑
### Dijkstra Algorithm
初始化：將各點距離設為無限大
1. 從起點往open set擴張，逐個修改最短路徑
2. 所有向外路徑都確認過後，將該起點設為 close set
3. 將距離起點最近的點設為新的起點
### A* Algorithm
• 試探函數(heurisitic function)
- 預估最少的代價，記為 h(n)
- 可使用priority_queue
- 距離
§ 曼哈頓距離
四種移動方向時可用
§ 切比雪夫距離
八種移動方向且移動距離相同可用
§ 歐幾里得距離
sqrt( a^2 +b^2 )
f(n) = g(n) + h(n)
實際距離g(n)
跟Dijkstra一樣是逐個點搜尋相鄰的點，差別在於起點的選擇
起點選擇 f(n)最小者
### Floyd-Warshall
```cpp
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
```
## 最近點對
### 簡介
分治法 (Divide and Conquer)
1. 將所有點遞迴分成左、右兩群，分別去找兩群的最短距離。
2. 取兩群的最短距離較小者，再找跨群間是否有更短的距離
3. 回傳左右兩群中最短距離點對。
• 最近點對問題合併時，共有三種可能情況:
1. 最近點對出現在左群
2. 最近點對出現在右群
3. 最近點對之左端點位於左群，右端點位於右群
• 所以合併時在左群找左端點、右群找右端點，暴搜最短距離即可
1. 找左端點時，找距離右群左端點x軸距離≤ min的
2. 找右端點時，找距離左群右端點x軸距離≤ min的
sample code:
```cpp=
double divide(iter begin,iter end)
{
int size=end-begin;
if(size<2)
return INTMAX;
if(size==2)
return distance(*begin,*(begin+1));
iter mid=begin+size/2;
double mindis=min( divide(begin,mid) , divide(mid,end) );
//尋找兩群間最短
vector<Point> left,right; //儲存找到的左點和右點
//從左群找x軸距離右端點mindis以內的點
for(iter templ=mid-1;templ>=begin;templ--)
{
if(abs((*mid).x-(*templ).x) > mindis)
break;
left.push_back(*templ);
}
//從右群找x軸距離左端點mindis以內的點
for(iter tempr=mid;tempr<end;tempr++)
{
if(abs((*tempr).x-(*(mid-1)).x) > mindis)
break;
right.push_back(*tempr);
}
if(left.empty() || right.empty())
return mindis;
for(auto el:left)
for(auto er:right)
{
double temp=distance(el,er);
if(temp<mindis)
mindis=temp;
}
return mindis;
}
```
## 網路流
增廣路徑: 剩餘網路裡，還能用的路徑
（廣搜剩餘網路）
從起點開始，能走且沒走過的塞進queue裡面，能走的標上來自哪裡，直到終點被標記。
從終點開始查來自哪裡的路徑，就是增廣路徑
while ( 找得到增廣路徑 )
最大流 += 增廣路徑上容量最少的
所有路徑容量 -= 增廣路徑上容量最少的
輸出: 最大流
## 最大團
挑選任一點為起點，找尋所有相鄰點
## 找負環
### 貝爾曼福特最短路徑 (Bellman–Ford algorithm)
• 資料結構
一維陣列: 點代價陣列val、edge陣列path、from點陣列from
1. 初始化
a. 將所有點上的代價設為 ∞
b. 將初始點代價設為0，來自點設為自己
2. 鬆弛
a. 將所有edge嘗試一遍，盡可能更新從起點到i點的代價、更新來自點
b. 重複a步驟至少n-1次，確保所有代價以鬆弛到極限
3. 檢查
a. 若鬆弛後再做一次鬆弛，代價又再度下降，說明有負環存在
## 最小生成樹
### Kruskal's Algorithm
將所有邊依距離(代價)排序，確認加入後Spanning Tree不成環，就加入Spanning Tree
sample code
```cpp=1
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define ALL(x) x.begin(),x.end()
#define INSERT(x) inserter(x,x.end())
class edge{
public:
int b,e;
double dis;
edge(int q=0,int w=0,double a=0){b=q;e=w;dis=a;};
};
bool cmp(edge a,edge b){
return a.dis<b.dis;
}
vector<pair<double,double> > v;
double dis(pair<double,double> p,pair<double,double> p2){
return sqrt((p.first-p2.first)*(p.first-p2.first)+(p.second-p2.second)*(p.second-p2.second));
}
vector<int> UF;
int uf(int a){
if(UF[a]==a)
return a;
return uf(UF[a]);
}
void uni(int a,int b){
int ta=uf(a);
int tb=uf(b);
if(ta!=tb)
UF[ta]=tb;
}
int main(){
#ifdef mark
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
ios::sync_with_stdio(0),cin.tie(0);
int kase;
cin>>kase;
while(kase--){
int n;//n個點
cin>>n;
v.resize(n);
for(auto&e:v){
cin>>e.first>>e.second;
}
vector<edge> ve;//ve.size()個邊
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
ve.pb(edge(i,j,dis(v[i],v[j])));
//cout<<ve.size()<<':';
sort(ve.begin(),ve.end(),cmp);
vector<edge> MST;
UF.resize(n);
for(int i=0;i<n;i++)
UF[i]=i;
for(int i=0;i<ve.size() && MST.size()<n;i++){
if(uf(ve[i].b)!=uf(ve[i].e)){
uni(ve[i].b,ve[i].e);
MST.pb(ve[i]);
}
}
double ans=0;
for(auto&e:MST){
ans+=e.dis;
}
/*
for(auto e:UF)
cout<<e<<' ';
cout<<endl;
*/
printf("%.2f\n",ans);
if(kase)
printf("\n");
}
}
```
---
### Prim's Algorithm
選一個點為起點加入點集合S，從所有與S連接的邊裡面選擇代價最小者連通，直到邊數 = 頂點數-1
## 並查集
```cpp
int Find(int n):
if(UF[n]==n)return n;
return Find(UF[n]);
void Union(int a,int b):
int ta=Find(a);
int tb=Find(b);
if(ta!=tb)UF[ta]=tb;
```
## 匈牙利演算法
### 匹配
無向圖上一個包含若干條邊的集合，且其中任意兩條邊沒有公共端點
(兩個一組配對)
• 最大匹配 - 匹配邊數最多的匹配
### 路徑
交錯路徑：以非匹配點作為起點，依序走非匹配邊、匹配邊、非匹配邊…。
增廣路徑（擴充路徑）：起點和終點皆為非匹配點的交錯路徑，其目的在於改進匹配，
將路徑上的非匹配邊與匹配邊互相交換，此路徑的總匹配變數就會加1。
### 算法
用途: 找二分圖上的最大匹配
步驟： 以二分圖其中一個集合內所有的點作為起點走交錯路徑，若是找到增廣路徑，
則將路徑上的匹配顛倒，然後總匹配變數加1，再從下一個起點繼續尋找，
等所有點都走完後，總匹配變數為最大匹配。
# Mathematics
## 向量
$$\vec{a} \times \vec{b}= \vert{a}\vert \cdot\vert{b}\vert \cdot sin \theta = det(a,b)$$$$\vec{a}=(a_x,a_y,a_z)$$$$\vec{b}=(b_x,b_y,b_z)$$
## 圓周率
π= 4 * atan(1)
## 距離
1. 曼哈頓距離
• 四種移動方向時可用
• 路徑長
2. 切比雪夫距離
• 八種移動方向且移動距離相同可用
3. 歐幾里得距離
• hypot(x1-x2,y1-y2)
• sqrt( a^2 +b^2 )
## 次方(快速冪運算)
將指數以2進制讀，若該位元為1，將C乘上對應值
$a^b$ = C
```cpp
int temp=a,c=1;
while(b)
{
if(b%2)
c*=a;
a*=a;
b/=2;
}
```
## 歐拉函數
定義：
若n為自然數，定義φ(n)為不大於n且與n互質的自然數的個數。
ϕ(1)=1
如果n是質數
ϕ(n) = n−1
ϕ(n^b )=nb−n(b-1)=n^b (1−1/b)
若ab互質
ϕ(ab)=ϕ(b)×ϕ(b)
## 排容公式
$t({},A ∪ B ∪ C)$ = $t(A,B ∪ C)$ - $t(A ∩ B,C)$
A̅$∩$B = A̅ -(A-B)
```cpp
int t(int A, int B∪C){
if(C==0)
return A;
return t(A,C)−t(A∩B,C)
}
```
# Divide and Conquer
## 大數乘法
加速
AD+BC = AC+AD+BC+BD-AC-BD =(A+B)(D+C)-AC-BD
## Merge sort
```cpp=1
ll v[500000];
ll t[500000];
ll usort(ll*b,ll*e){
if(e-b<2)
return 0;
if(e-b==2){
if(*b>*(b+1)){
swap(*b,*(b+1));
return 1;
}
return 0;
}
ll mid=(e-b)/2,temp=0,k=b-v;
//left & right
ll div=usort(b,b+mid)+usort(b+mid,e);
//merge
for(ll*i=b,*j=b+mid;i<b+mid||j<e;){
if(*i<=*j)
t[k++]=*i++;
else{
t[k++]=*j++;
temp+=(mid-(i-b));
}
while(i>=b+mid && j<e)
t[k++]=*j++;
while(j>=e && i<b+mid)
t[k++]=*i++;
}
for(int i=b-v;i<k;i++)
v[i]=t[i];
return div+temp;
}
int main(){
int n;
while(cin>>n,n){
//memset(v,0,sizeof(ll)*500000);
for(int i=0;i<n;i++)
cin>>v[i];
cout<<usort(v,v+n)<<endl;/*
for(int i=0;i<n;i++)
cout<<v[i]<<' ';
cout<<endl;*/
}
}
```
# Others
## 內建函數
```cpp
int __builtin_popcount (unsigned int x) 回傳x在二進制下有幾個1
ios_base::sync_with_stdio(0); 神秘的黑科技
cin.tie(0);
bool binary_search(iter begin,iter end,const T& val) STL 二分搜尋
iter lower_bound(iter begin, iter end, const T& val) 二分搜尋，回傳第一個≥val的位址
iter upper_bound(iter begin, iter end, const T& val) 二分搜尋，回傳第一個>val的位址
pow(x,y)
pow計算後為浮點數，某些情況下若直接轉成int會產生微小誤差，需要先做round運算再轉成int。
(int)pow(10,2)=99
(int)round(pow(10,2))=100
*MinGW，其他編譯器不確定
iter next( iter it , int forward) 回傳 it 往後 n 個位置的指標 (等同於 it + n)
```
## 時間戳記
```cpp
clock_t begin,end;
begin = clock();
//run code
end = clock();
cout<<(double)(end - begin)/CLOCKS_PER_SEC<<endl;
```
---
:::info
**Find this document incomplete?** Leave a comment!
:::
###### tags: `C++` `STL` `algorithm`
Sign in with Wallet
Connect another wallet