---
# System prepended metadata

title: 程式設計 筆記
tags: [algorithm, C++, STL]

---

# 程式設計 筆記
## 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 (log⁡n)
```cpp=1
update(i,num)
    while(i<size):
        BIT[i]+=num
        i+=(i&-i)
```
				
2. prefixSum(idx)：求从数组第一个位置到第idx（含idx）个位置所有数字的和。O(log⁡n)
```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(log⁡n)
```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]
![](https://i.imgur.com/h0vk167.png)

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”，求最長回文子序列和長度。
![](https://i.imgur.com/xzHKAO2.png =500x300)

    ( 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的
![](https://i.imgur.com/YG5tp63.png)
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
![](https://i.imgur.com/6WO9SDD.png)
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
## 大數乘法
![](https://i.imgur.com/PG9BLRk.png =300x300)

    加速
    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`