# 常用演算法及資料結構 1. 語法 C++基礎語法: [C++學習筆記](/9erTfSpQSKiKS9hrRS__-Q) Python基礎語法: [Python學習筆記](/mBWdRuDgQjmY3M_dp9-6kg) 1. 窮舉 邊權只有0跟1: [01BFS](/@erichung0906/BJ1PUSqsD) 每種路徑求法: [DFS](/@erichung0906/By-PtG2Fw) DFS加速: [剪枝](/F34g0xE0ROmGYeo12bZhwA) 計算所有子集合的合: [All sum of subset](/xGzQwtppSfqfN3bciJtEHw) 1. 資料結構(data structure) 區間求值: [Segment Tree](/nrT8D7eqSUWZYrTEj3SjNQ) 求區間最值: [Sparse Table](/jFKC0KV0S-6iQiPaao9Bcg?both) 計算前綴合: [BIT](/8dNFh3NlRm63uxx4gq4P-A) 二維前綴合: [二維前綴和](/@erichung0906/H1E2oT5lO) 集合合併問題: [Disjoint Set](/LUSqNVTCQ4KKsEBvh3PUIw) 用於優先對列: [Heap](/Dh5MylM0Sye9v8WLi1HxFQ) 滑動窗口問題: [單調隊列](/CSiMRPG_TkeHa5V692ixFA) 分成√塊: [分塊演算法](/86kWJsh6S5KjPzYLc1xsxg) 分塊延伸: [莫隊算法](/Z4K-UL1ySIOoVaz2FjwT-w) 區間第$k$小: [持久化線段樹](/K8qTIlbaTuWijADAnTDtGw) 區間第$k$小二分搜作法: [整體二分](/gtn_aX5kTamQXYoGkes28Q) 尋找子字串: [Suffix Array](/8BROsCyFTbWe6lx9_WqYiA) 區間不同數的個數: [Range Distinct values queries](/A-_5H0QRSIyUROldQ9r0fA) 斜線求最小$f(x)$: [李超線段樹](/Mn69f9ZMRmqxjMOZfURuWg) BST平衡樹: [Treap](/LYbYu-0bQPiRPJShrDAybQ) 1. 圖 兩點最短路徑求法: [Shortest Path](/335HecMuRRGVcp2I1QHyLw) 最少點圍成的區域包含所有點: [convex hull](/wO_ifMJlTZWIJvFnmJankg) 兩兩相配最大匹配數: [匈牙利演算法](/Wkx4XAYyQ02nkvsjBWXTlQ) 求兩兩有路徑相通的圖: [SCC](/wWfpnJZYR5K41kZSXc6piA) 任兩點都相通: [Eulerian Cycle](/wxlL-6qPRKGF3W7X30p28Q) 網路流問題: [flow](/cnB-y7u3Te62sxOLirD-Og) 兩條件必要有一條建成立問題: [2-SAT](/kjlbCsblRDCDNqDInlNL_w) $xa_1+ya_2+za_3=k$: [同餘最短路](/Pcxb5b5SSZGMnvtmm-brvQ) 1. 樹 樹的遍歷: [前序 後序 中序 遍歷](/hNKyvEC1Q2C9-7T-bODsXg) 一筆走完權重問題(最小生成數):[MST](/@erichung0906/ryfkjwtbu) 求最近共同祖先: [LCA](/OUckyOvoRvOHsVvsLMoPUA) 1. 數論 費馬小定理與歐拉定理:[數論](/AoUlaQA-SBqO0QbnHvhydw) 求最大的平均值: [最大化平均值](/6iTDRRaqRmO6_CNz3iEiEw) 數值太大卻要開陣列存時: [離散化](/@erichung0906/rytWoKFed) 把元素對應到特定的元素: [Hash Table](/@erichung0906/ByO2pdciw) 幾人一數淘汰,求倖存者問題: [約瑟夫問題](/rChcW7u1TkaMU3z0bykLPg?both) 快速求出$a^b$: [快速冪](/OBXWeBUOTH-Eo5FIcMIHDA) 求出費式數列極大值: [矩陣快速冪](/OX9XQCbvSy-8OX2jRrXhdw) 大數相乘取模: [快速乘](/Xp3mzZAbTLiimL9CgSIFVw) 求$i<j\ \&\&\ s[i]>s[j]$的數對: [逆序數對](/3C-optw6QFmJqfMfrfY3tw) 最大公因數與最小公倍數: [GCD&LCM](/w34AiEJmRj2hjRD747luIw) 組合數$C$幾取幾: [Combination](/KJUqMshaSayqZJXb_hEdqg) 質數: [Prime](/0QCdyOIHTu61cj9xmmMYsg) 1. DP DP經典問題: [DP](/7D1LBtrcQJSh5MW7sEeU1A) 求最大連續元素和: [MCS](/jIEo1F6TSTioxDtlKkY9oA?both) 求最長遞增子序列: [lIS](/QDTSox4XTpugAnYKfXv9Uw) 求最長共同子序列: [LCS](/wI57g8avSb6kq9pJ-AG1Xw) 求最長回文子字串: [LPS](/-NV6uo6DTfyq51vErQvNOA) 矩陣鏈相乘: [matrix chain](/N0TPQRoURAC8TdEdsBBhsw) 括號匹配數: [N個括號的匹配數](/g-25tHRfTBmf-5W1WyXLLQ) $a[i]×b[j]+c[j]$的狀態轉移: [斜率優化](/GDLXmEqaT32xfzeHmzPxmw) 3. 其他 最常回文子字串: [LPS](/-NV6uo6DTfyq51vErQvNOA) 犯蠢紀錄: [debug](/TiDknRw4TmqWyoCTDdy_Cg) 日期轉換: [時間函數庫](/80EQNjJMTNarPviBs4FJ8Q) github使用教學: [Github push 使用教學](https://medium.com/@erichung0906/github%E4%BD%BF%E7%94%A8%E6%95%99%E5%AD%B8-6f7305ed3122) 小技巧: 1. 0,1字串在轉INT時可以直接用(s[i] & 1) 2. 陣列初始成最大值時可以使用memset(a,0x3f,sizeof(a)),會自動偵測int or ll,且相加不會overflow 3. iota(dsu,dsu+N,0) 會從0填到N-1 4. 做unsigned long long運算會自動mod 2^63^且不會溢位
×
Sign in
Email
Password
Forgot password
or
Sign in via Google
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
Continue with a different method
New to HackMD?
Sign up
By signing in, you agree to our
terms of service
.