cin cout加快讀取速度：
ios::sync_with_stdio(false);高精度*高精度
vector<int> mul(vector<int>& a, vector<int>& b) {vector<int>c(b.size()+a.size()+5,0);for (int i = 0; i < a.size(); i++) {for (int j = 0; j < b.size(); j++) {c[i + j] += a[i] * b[j];}}for (int i = 0; i < c.size(); i++) {if (c[i] > 9) {c[i + 1] += c[i] / 10;c[i] = c[i] % 10;}}while (c.size() > 1 && c.back() == 0)c.pop_back();return c;
}高精度+高精度
vector<int> add(vector<int> &A, vector<int> &B)
{if (A.size() < B.size()) return add(B, A);vector<int> C;int t = 0;for (int i = 0; i < A.size(); i ++ ){t += A[i];if (i < B.size()) t += B[i];C.push_back(t % 10);t /= 10;}if (t) C.push_back(t);return C;
}二分：
bool check(int x) {/* ... */} // 檢查x是否滿足某種性質// 求右邊界時用，滿足右區間性質為true
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid; // check()判斷mid是否滿足性質else l = mid + 1;}return l;
}
// 求左邊界時用，滿足左區間性質為true
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}return l;
}
int res=upper_bound(num,num+n,q)-num;
int res=lower_bound(num,num+n,q)-num;
upper尋找第一個大于q的數的地址，lower尋找第一個大于等于q的數的地址。在"algorithm"庫中。
?滑動窗口：
//進窗口
......
//處理結果
......
//出窗口
......動態規劃：
- 確定dp數組（dp table）以及下標的含義
- 確定遞推公式
- dp數組如何初始化
- 確定遍歷順序
- 舉例推導dp數組
- 01背包：物品只有一個。dp[i][j]從前i個物品中選，容量為j時選擇的最大價值是dp[i][j]。
?dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);區別就是對i物品選與不選。
- 完全背包：每個物品無數個。dp[i][j]定義一樣。
dp[i][j]=max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
兩者在選擇i物品上有區別，
dfs:
深搜三步曲：
1.確定遞歸函數，參數
2。確認終止條件
3.處理目前搜索節點出發的路徑
void dfs(參數) {if (終止條件) {存放結果;return;}for (選擇：本節點所連接的其他節點) {處理節點;dfs(圖，選擇的節點); // 遞歸回溯，撤銷處理結果}
}
bfs:
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四個方向
// grid 是地圖，也就是一個二維數組
// visited標記訪問過的節點，不要重復訪問
// x,y 表示開始搜索節點的下標
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que; // 定義隊列que.push({x, y}); // 起始節點加入隊列visited[x][y] = true; // 只要加入隊列，立刻標記為訪問過的節點while(!que.empty()) { // 開始遍歷隊列里的元素pair<int ,int> cur = que.front(); que.pop(); // 從隊列取元素int curx = cur.first;int cury = cur.second; // 當前節點坐標for (int i = 0; i < 4; i++) { // 開始想當前節點的四個方向左右上下去遍歷int nextx = curx + dir[i][0];int nexty = cury + dir[i][1]; // 獲取周邊四個方向的坐標if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 坐標越界了，直接跳過if (!visited[nextx][nexty]) { // 如果節點沒被訪問過que.push({nextx, nexty}); // 隊列添加該節點為下一輪要遍歷的節點visited[nextx][nexty] = true; // 只要加入隊列立刻標記，避免重復訪問}}}}快排：
void quick_sort(int q[], int l, int r)
{if (l >= r) return;int i = l - 1, j = r + 1, x = q[l + r >> 1];while (i < j){do i ++ ; while (q[i] < x);do j -- ; while (q[j] > x);if (i < j) swap(q[i], q[j]);}quick_sort(q, l, j), quick_sort(q, j + 1, r);
}歸并排序：
void merge_sort(int q[], int l, int r) {if (l >= r)return;int mid = l + r >> 1;merge_sort(q, l, mid);merge_sort(q, mid + 1, r);int k = 0, i = l, j = mid+1;while (i <= mid && j <= r) {if (q[i] <= q[j])tmp[k++] = q[i++];else tmp[k++] = q[j++];}while (i <= mid) { tmp[k++] = q[i++]; }while (j <= r) { tmp[k++] = q[j++]; }for (int i = l,j=0;i<=r;i++,j++) q[i] = tmp[j];
}前綴與差分：
a[n]是b[n]的前綴和數組，b[n]是a[n]的差分數組。
a[n]=b[1]+b[2]+...+b[n]。b[n]=a[n]-a[n-1]。
如果對a數組l到r均+c，那么只需對b數組b[l]+c，b[r+1]-c。
如果求b數組從l到r的和，那么只需查詢a[r]-a[l]。
并查集：
1.將兩個元素添加到同一個集合中。
2.判斷兩個元素在不在同一個集合中。
int n = 1005; // n根據題目中節點數量而定，一般比節點數量大一點就好
vector<int> father = vector<int> (n, 0); // C++里的一種數組結構// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}
// 并查集里尋根的過程
int find(int u) {if (u == father[u]) return u;else return father[u] = find(father[u]); // 路徑壓縮
}
// 判斷 u 和 v是否找到同一個根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 將v->u 這條邊加入并查集
void join(int u, int v) {u = find(u); // 尋找u的根v = find(v); // 尋找v的根if (u == v) return ; // 如果發現根相同，則說明在一個集合，不用兩個節點相連直接返回father[v] = u;
}最小生成樹：
prim三部曲：
1.選距離生成樹最近節點
2.最近節點加入生成樹
3.更新非生成樹節點到生成樹的距離（即更新minDist數組）
Kruskal算法：
思路：邊的權值排序，因為要優先選最小的邊加入到生成樹里。
遍歷排序后的邊，如果邊收尾的兩個節點在同一個集合中，說明如果連上這條邊圖中會出現環；如果邊首尾的兩個節點不在同一個集合，加入到最小生成樹，并把兩個節點加入同一個集合
