嘎嘎喵

摘要： 本文章同步發(fā)表在洛谷博客。 什么是博弈 DP？ 博弈，是一個(gè)多名玩家參與的競(jìng)爭(zhēng)游戲。每次只允許一個(gè)人行動(dòng)，并且通常采用輪流行動(dòng)的方式。 每個(gè)人的目標(biāo)都是在游戲中獲勝，并且題目一般會(huì)假定所有人都足夠聰明，都會(huì)采用最優(yōu)策略。 一般的獲勝或者失敗條件，可能是分?jǐn)?shù)達(dá)到一定值（或者最大或者最小），也可能是運(yùn)轉(zhuǎn) 閱讀全文

摘要： 什么是倍增？ 倍增？倍增？倍增！ 之前學(xué)了最近公共祖先 LCA，其是倍增的子問(wèn)題。 倍增是什么，什么是倍增？倍增，顧名思義，就是一倍兩倍往上增。其實(shí)上，就是一步跳 \(2^k\)，可把速度從 \(O(n)\) 直降到 \(O(\log n)\)，是一個(gè)非常 nice 的算法。 ST 表！ ST 表？ 閱讀全文

摘要： Floyd 是什么？ Floyd 是一種圖論算法，全源最短路，可以在 \(O(n^3)\) 的時(shí)間內(nèi)求出所有 \(x\) 到 \(y\) 的最短路。一般用于 \(n\) 比較小并且為稠密圖的情況下。 Floyd 的求解 首先簡(jiǎn)單看一下 Floyd 的定義：\(f_{k,i,j}\) 表示當(dāng)前只考慮前 閱讀全文