ACM主要算法介紹

ACM主要算法介紹


(以下是自己覺得比較好的算法學習的博客鏈接,自己做了部分順序和分類調(diào)整)(以下算法分類來自于:ACM主要算法

后續(xù)將繼續(xù)補充

數(shù)據(jù)結構

圖論

  • 基本圖算法圖
    廣度優(yōu)先遍歷
    深度優(yōu)先遍歷
    拓撲排序
    割邊割點
    強連通分量
    Tarjan算法
    雙連通分量
    強連通分支及其縮點
    圖的割邊和割點
    最小割模型立膛、網(wǎng)絡流規(guī)約
    2-SAT問題
    歐拉回路
    哈密頓回路
  • 最小生成樹
    Prim算法
    Kruskal算法(稀疏圖)
    Sollin算法
    次小生成樹
    第k小生成樹
    最優(yōu)比例生成樹
    最小樹形圖
    最小度限制生成樹
    平面點的歐幾里德最小生成樹
    平面點的曼哈頓最小生成樹
    最小平衡生成樹
  • 最短路徑
    有向無環(huán)圖的最短路徑->拓撲排序
    非負權值加權圖的最短路徑->Dijkstra算法(可使用二叉堆優(yōu)化)
    含負權值加權圖的最短路徑->Bellmanford算法
    含負權值加權圖的最短路徑->Spfa算法
    (稠密帶負權圖中SPFA的效率并不如Bellman-Ford高)
    全源最短路弗洛伊德算法Floyd
    全源最短路Johnson算法
    次短路徑
    第k短路徑
    差分約束系統(tǒng)
    平面點對的最短路徑(優(yōu)化)
    雙標準限制最短路徑
  • 最大流
    增廣路->Ford-Fulkerson算法
    預推流
    Dinic算法
    有上下界限制的最大流
    節(jié)點有限制的網(wǎng)絡流
    無向圖最小割->Stoer-Wagner算法
    有向圖和無向圖的邊不交路徑
    Ford-Fulkerson迭加算法
    含負費用的最小費用最大流
  • 匹配
    Hungary算法
    最小點覆蓋
    最小路徑覆蓋
    最大獨立集問題
    二分圖最優(yōu)完備匹配Kuhn-Munkras算法
    不帶權二分匹配:匈牙利算法
    帶權二分匹配:KM算法
    一般圖的最大基數(shù)匹配
    一般圖的賦權匹配問題
  • 拓撲排序
  • 弦圖
  • 穩(wěn)定婚姻問題

搜索

  • 廣搜的狀態(tài)優(yōu)化
    利用M進制數(shù)存儲狀態(tài)
    轉(zhuǎn)化為串用hash表判重
    按位壓縮存儲狀態(tài)
    雙向廣搜
    A*算法
  • 深搜的優(yōu)化
    位運算
    剪枝
    函數(shù)參數(shù)盡可能少
    層數(shù)不易過大
    雙向搜索或者是輪換搜索
    IDA*算法
  • 記憶化搜索

動態(tài)規(guī)劃

  • 四邊形不等式理論
  • 不完全狀態(tài)記錄
    青蛙過河問題
    利用區(qū)間dp
  • 背包類問題
    0-1背包,經(jīng)典問題
    無限背包梯码,經(jīng)典問題
    判定性背包問題
    帶附屬關系的背包問題
    + -1背包問題
    雙背包求最優(yōu)值
    構造三角形問題
    帶上下界限制的背包問題(012背包)
  • 線性的動態(tài)規(guī)劃問題
    積木游戲問題
    決斗(判定性問題)
    圓的最大多邊形問題
    統(tǒng)計單詞個數(shù)問題
    棋盤分割
    日程安排問題
    最小逼近問題(求出兩數(shù)之比最接近某數(shù)/兩數(shù)之和等于某數(shù)等等)
    方塊消除游戲(某區(qū)間可以連續(xù)消去求最大效益)
    資源分配問題
    數(shù)字三角形問題
    漂亮的打印
    郵局問題與構造答案
    最高積木問題
    兩段連續(xù)和最大
    2次冪和問題
    N個數(shù)的最大M段子段和
    交叉最大數(shù)問題
  • 判定性問題的dp(如判定整除宝泵、判定可達性等)
    模K問題的dp
    特殊的模K問題,求最大(最小)模K的數(shù)
    變換數(shù)問題
  • 單調(diào)性優(yōu)化的動態(tài)規(guī)劃
    1-SUM問題
    2-SUM問題
    序列劃分問題(單調(diào)隊列優(yōu)化)
  • 剖分問題(多邊形剖分/石子合并/圓的剖分/乘積最大)
    凸多邊形的三角剖分問題
    乘積最大問題
    多邊形游戲(多邊形邊上是操作符,頂點有權值)
    石子合并(N3/N2/NLogN各種優(yōu)化)
  • 貪心的動態(tài)規(guī)劃
    最優(yōu)裝載問題
    部分背包問題
    乘船問題
    貪心策略
    雙機調(diào)度問題Johnson算法
  • 狀態(tài)dp
    牛仔射擊問題(博弈類)
    哈密頓路徑的狀態(tài)dp
    兩支點天平平衡問題
    一個有向圖的最接近二部圖
  • 樹型dp
    完美服務器問題(每個節(jié)點有3種狀態(tài))
    小胖守皇宮問題
    網(wǎng)絡收費問題
    樹中漫游問題
    樹上的博弈
    樹的最大獨立集問題
    樹的最大平衡值問題
    構造樹的最小環(huán)

數(shù)學

  1. 數(shù)論

    • 中國剩余定理
    • 歐拉函數(shù)
    • 歐幾里得定理
    • 歐幾里德輾轉(zhuǎn)相除法求GCD(最大公約數(shù))
    • 擴展歐幾里得
    • 大數(shù)分解與素數(shù)判定
    • 佩爾方程
    • 同余定理(大數(shù)求余)
    • 素數(shù)測試
      一千萬以內(nèi):篩選法
      一千萬以外:米勒測試法
    • 連分數(shù)逼近
    • 因式分解
    • 循環(huán)群生成元
    • 素數(shù)與整除問題
    • 進制位.
    • 同余模運算
  2. 組合數(shù)學

    • 排列組合
    • 容斥原理
    • 遞推關系和生成函數(shù)
    • Polya計數(shù)法
      Polya計數(shù)公式
      Burnside定理
    • N皇后構造解
    • 幻方的構造
    • 滿足一定條件的hamilton圈的構造
    • Catalan數(shù)
    • Stirling數(shù)
    • 斐波拉契數(shù)
    • 調(diào)和數(shù)
    • 連分數(shù)
    • MoBius反演
    • 偏序關系理論
    • 加法原理和乘法原理
  3. 計算幾何

    • 基本公式
      叉乘
      點乘
      常見形狀的面積轩娶、周長儿奶、體積公式
      坐標離散化
    • 線段
      判斷兩線段(一直線、一線段)是否相交
      求兩線段的交點
    • 多邊形
      判定凸多邊形,頂點按順時針或逆時針給出,(不)允許相鄰邊共線
      判點在凸多邊形內(nèi)或多邊形邊上,頂點按順時針或逆時針給出
      判點在凸多邊形內(nèi),頂點按順時針或逆時針給出,在多邊形邊上返回0
      判點在任意多邊形內(nèi),頂點按順時針或逆時針給出
      判線段在任意多邊形內(nèi),頂點按順時針或逆時針給出,與邊界相交返回1
      多邊形重心
      多邊形切割(半平面交)
      掃描線算法
      多邊形的內(nèi)核
    • 三角形
      內(nèi)心
      外心
      重心
      垂心
      費馬點

    • 判直線和圓相交,包括相切
      判線段和圓相交,包括端點和相切
      判圓和圓相交,包括相切
      計算圓上到點p最近點,如p與圓心重合,返回p本身
      計算直線與圓的交點,保證直線與圓有交點
      計算線段與圓的交點可用這個函數(shù)后判點是否在線段上
      計算圓與圓的交點,保證圓與圓有交點,圓心不重合
      計算兩圓的內(nèi)外公切線
      計算線段到圓的切點
      點集最小圓覆蓋
    • 可視圖的建立
    • 對踵點
    • 經(jīng)典問題
      平面凸包
      三維凸包
      Delaunay剖分和Voronoi圖
  4. 計算方法

    • 二分法
      二分法求解單調(diào)函數(shù)相關知識
      用矩陣加速的計算
    • 迭代法
    • 三分法
    • 解線性方程組
      LUP分解
      高斯消元
    • 解模線性方程組
    • 定積分計算
    • 多項式求根
    • 周期性方程
    • 線性規(guī)劃
    • 快速傅立葉變換
    • 隨機算法
    • 0/1分數(shù)規(guī)劃
    • 三分法求解單峰(單谷)的極值
    • 迭代逼近
    • 矩陣法
  5. 博弈論

    • 極大極小過程

    • Nim問題

?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末鳄抒,一起剝皮案震驚了整個濱河市闯捎,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌许溅,老刑警劉巖瓤鼻,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異贤重,居然都是意外死亡茬祷,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門并蝗,熙熙樓的掌柜王于貴愁眉苦臉地迎上來牲迫,“玉大人,你說我怎么就攤上這事借卧№镌鳎” “怎么了?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵铐刘,是天一觀的道長陪每。 經(jīng)常有香客問我,道長,這世上最難降的妖魔是什么檩禾? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任挂签,我火速辦了婚禮,結果婚禮上盼产,老公的妹妹穿的比我還像新娘饵婆。我一直安慰自己,他們只是感情好戏售,可當我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布侨核。 她就那樣靜靜地躺著,像睡著了一般灌灾。 火紅的嫁衣襯著肌膚如雪搓译。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天锋喜,我揣著相機與錄音些己,去河邊找鬼。 笑死嘿般,一個胖子當著我的面吹牛段标,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播炉奴,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼怀樟,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了盆佣?” 一聲冷哼從身側(cè)響起往堡,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎共耍,沒想到半個月后虑灰,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡痹兜,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年穆咐,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片字旭。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡对湃,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出遗淳,到底是詐尸還是另有隱情拍柒,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布屈暗,位于F島的核電站拆讯,受9級特大地震影響脂男,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜种呐,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一宰翅、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧爽室,春花似錦汁讼、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至戈擒,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間艰毒,已是汗流浹背筐高。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留丑瞧,地道東北人柑土。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像绊汹,于是被迫代替她去往敵國和親稽屏。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 今天從澳洲回來的閨蜜和我約見薄腻,跳跳跟爸爸和爺爺奶奶一起赴宴(和其他親戚一起聚會),因為閨蜜車子出了問題届案,所以他們?nèi)?..
    崔峰媳婦孫小瑩閱讀 353評論 0 0
  • 攜一片前世的記憶庵楷,與一段曲折的水袖相逢,在一處古樸清雅的橋邊小驛楣颠,把一杯茶喝到陶然忘機尽纽。 是中華荷園,在北方微涼的...
    吳雙小姐閱讀 371評論 0 2
  • 香嚴上樹 香嚴和尚云童漩。如人上樹弄贿。口[啣-止+山]樹枝矫膨。手不攀枝挎春。腳不踏樹看疙。樹下有人。問西來意直奋。不對即違他所問能庆。若對...
    石竹閱讀 566評論 2 1
  • 那是一只格外安靜的大蚊子,悄悄的躲在角落里脚线,瞪圓了眼搁胆,虎視眈眈的窺視著房間里的一切。有個小姑娘從門外走進來邮绿,她全然...
    九筆閱讀 444評論 0 0