Piau 的筆記本

Treap 是 Tree 跟 Heap 的結合體 同時有

線段樹可以用來做 的區間修改、區間查詢 只要有結合律的資訊都可以用線段樹進行維護 其主要分為 build、update、query、push、pull 等函式組成 當不需要更詳細的資訊時，可以使用懶標記來記錄大致訊息 在線段樹中儲存的編號有兩種表達形式 0-based: id2+1 / id2+2 1-based: id2 / id2+1 id 為當前線段樹節點的編號 l、r 代表當前第 id 個節點在原陣列的區間 ql、qr 代表當前查詢的區間 以下為 1-based 的範例程式碼 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061int n; // n 為節點數 struct Node { int data, tag; Node() : data(0), tag(0) {} }; vector<Node> seg; int get_val(int l, int...

跳躍二分搜 快速冪 12345678int f(int x, int y) { int ret = 1; for (; y; y >>= 1) { if (y&1) ret *= x; x *= x; } return ret; } 123456int f(int x, int y) { if (!y) return 1; if (y&1) return f(x, y-1) * x; int k = f(x, y/2); return k*k; } 互補團隊 1234m 為總共幾個元素 int k = (1 << m) - 1; for (auto &c : string) now |= (1 << (c-'A')); 計算現在物件有幾項元素 另一項互補物件即為 now^k

1234random_device rd; mt19937 gen(rd()); int randomValue = gen();

題目連結：CSES-1083 Missing Number 題意 給你一個 n，代表有一個數列的範圍是 1 ~ N 接著給你 n - 1 個數字 請你找出沒有出現的數字為何 思路 主要利用相同數字互相 xor 會為 0 特性 拿一個變數 N 去 xor 範圍內所有的數字 接著再 xor 測資給你的數列 這樣，如果有出現在數列裡的數字就會 xor 兩次而被抵銷 沒有出現的數字會因為只有 xor 一次，所以遺留在 N 裡 最後輸出 N 即可 程式碼 12345678910111213141516#include <bits/stdc++.h> using namespace std; #define WA() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) #define int long long signed main() { WA(); int n, xr = 0; cin >> n; vector<int> v(n-1); ...

針對我比較不熟的題目做的筆記 這樣下次考試前就不用翻程式碼進入回憶錄了 公式題 UVA 10021 Satellites 題意 計算兩個在相同軌道的衛星的距離 a：衛星到地球的距離 b：與地球形成的夾角 s：角度的單位 輸出：兩個衛星之間的弧長、弦長 思路 1 deg = 60 min 所以如果角度單位是 min，先幫將其換成 deg 如果角度大於 180 度的話，使用補角 衛星的軌道半徑為 （6440 是地球的半徑） 將度轉換成弧度 弧度度 弧長公式： 弦長公式： 程式碼 1234567891011121314#include <bits/stdc++.h> using namespace std; int main() { double a, b, r; string s; while (cin >> a >> b >> s) { r = 6440 + a; if (s == "min") b /= 60; if (b > 180) b = 360...

Kruskal’s Algorithm Kruskal’s Algorithm 是用來找最小生成樹的演算法 其尋找的方式是從不斷添加權重最小的邊，且如果添加後形成環就將其移除 在實作上，可以用 Union-Find 判斷會不會形成環 要點 需要一個一維陣列，裡面放邊權重、A 節點、B 節點 將其排序後遍歷，並且透過 Union-Find 檢查 如果兩者的祖先不相同則代表添加後不會形成環 添加後將兩節點 合併（Union） 實作 這邊是 Kruskal’s Algorithm 會用到的 Union-Find 詳細的解釋在 這裡 12345678910111213141516vector<int> anc; int Find(int x) { return (anc[x] == x ? x : anc[x] = Find(anc[x])); } bool Union(int a, int b) { anc[Find(b)] = Find(a); } int main() { int n; cin >> n; ...

Maximum-Flow 中文叫做最大流，什麼是流？可以把一個圖上邊看作為水管，其權重看作為水流能夠通過的量 若圖為有向圖代表水流只允許單向流動，若為無向圖則代表可以同時往兩邊流動 而最大流是在一個圖中，在所有可能的 s-t 流（從源點 s 到 匯點 t）尋找最大值 要找到最大流可以使用 Ford-Fulkerson 演算法 但是 Ford-Fulkerson 演算法中，會因為其沒有對尋找增廣路徑的策略限制，有可能會導致不斷重複選擇非最佳解 所以我們這篇筆記主要會以 Ford-Fulkerson 的改良版：Edmonds-Karp 為主 要點 Ford-Fulkerson 觀念 s-t 流的過程會由許多大大小小的支流匯聚 演算法的目標就是不斷的尋找最適合的支流（也就是增廣路徑）並進行加總 該如何尋找增廣路徑呢？ 先找一條可以從 s 走到 t...

Dijkstra’s Algorithm Dijkstra 是根據邊的權重進行比較，用來找節點之間的最小路徑 注意：Dijkstra 演算法無法處理負權重 要點 除了用來儲存圖的二維陣列外 Dijkstra 演算法需要 距離陣列：起點到每一點的最短距離 優先佇列：快速尋找當前最短路徑的節點 觀念 從起點開始尋找 如果佇列裡的距離比已知的最短距離還遠，就跳過 遍歷所有與之相連的節點，比較從鎖定後的節點走還是原有的路徑比較短 如果新計算的路徑較短，則更新距離並重新放入佇列裡面 實作 初始化 dis 中，所有點的原距離，初始值設為極大值（除了起點設為 0） pq 的 first 是距離，second 是節點編號，且排序為從小到大 12vector<int> vis(n), dis(n, 0x3f3f3f3f); // n 為節點樹 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>...

Trie Trie 專門用於儲存和快速查找字串 O(n) 查詢會比在一般的陣列 O(m*n) 中還快 副作用是空間複雜度很高 別名：字典樹、前綴樹 要點 觀念 每個節點內會有 unordered_map，key 為下一個字元，value 該字元的節點 pointer 布林變數，用於紀錄該節點是否為一個字串的結束點 圖片引用自 這裡 功能 insert：插入字串 search：查詢字串是否存在 delete：刪除字串 實作 結構本體 1234struct Node { unordered_map<char, Node*> child; bool isWord = false; }; 宣告結構 1Node *root = new Node; 插入 從根節點開始往下尋找有無特定字元的子節點 若沒有子節點，新增一個子節點 接著移動到下一個節點 移動到最後一個字元時，設定 isWord 為 true 以記錄該節點為字尾 1234567void insert(Node *p, string s) { for (auto c : s) { ...