椰蘿Yerosius的博客

摘要： 拓?fù)渑判?拓?fù)渑判蚩梢暈閷?duì)圖上所有頂點(diǎn)不重不漏的遍歷，因此可采用BFS或DFS實(shí)現(xiàn) 拓?fù)渑判虻某湟獥l件是其為DAG(有向無(wú)環(huán)圖)，若拓?fù)渑判驘o(wú)解說(shuō)明圖該圖不是DAG，因此可對(duì)圖進(jìn)行判環(huán) 若為無(wú)向圖可看做有向圖進(jìn)行拓?fù)渑判?基環(huán)樹(shù)) 復(fù)雜度： O {O} O( V + E V+E V+E) 基于BFS 閱讀全文

摘要： Bellman-Ford 本質(zhì)：DP，對(duì)邊進(jìn)行操作特點(diǎn)：?jiǎn)卧醋疃搪罚蠼庖粋€(gè)源點(diǎn)到其他所有點(diǎn)的最短距離適用對(duì)象：小圖，允許負(fù)權(quán)有向圖，不能處理負(fù)權(quán)無(wú)向圖和和負(fù)環(huán)圖(負(fù)環(huán)：圖上邊權(quán)之和為負(fù)的環(huán))存儲(chǔ)結(jié)構(gòu)：直接存邊核心思想：每輪中反復(fù)松弛所有邊，若該邊使距離更優(yōu)則更新。最多進(jìn)行 V ? 1 V-1 V? 閱讀全文

摘要： Floyd 本質(zhì)：DP 存儲(chǔ)結(jié)構(gòu)：鄰接矩陣，若有重邊則讀入時(shí)必須取最小邊 算法特點(diǎn)：多源最短路，能一次性求解所有點(diǎn)對(duì)間的最短距離 適用對(duì)象：小圖，允許負(fù)權(quán)圖，無(wú)法適用于負(fù)環(huán)圖(負(fù)環(huán):環(huán)上邊權(quán)之和為負(fù)的環(huán),當(dāng)任意時(shí)刻出現(xiàn) d p [ i ] [ i ] < 0 dp[i][i]<0 dp[i][i]< 閱讀全文

摘要： Dijkstra 本質(zhì)：BFS+貪心，對(duì)點(diǎn)進(jìn)行操作 特點(diǎn)：?jiǎn)卧醋疃搪罚蠼庖粋€(gè)源點(diǎn)到其他所有點(diǎn)的最短距離 存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)角跋蛐?適用對(duì)象：非負(fù)權(quán)圖(一旦頂點(diǎn)已經(jīng)確定最短路，其將不再被考查， d i s dis dis將不再改變)；不能求最長(zhǎng)路 核心思想：不斷貪心選取 { d i s } \set{d 閱讀全文

摘要： 離散化 離散化適用于在一個(gè)較大區(qū)間內(nèi)，只關(guān)心數(shù)據(jù)的相對(duì)大小，而不關(guān)心數(shù)據(jù)的絕對(duì)大小，通常將較大的區(qū)間通過(guò)映射縮小到一個(gè)較小區(qū)間中，用相對(duì)值代替絕對(duì)值，進(jìn)行縮小區(qū)間范圍的技巧，以提升時(shí)空效率。哈希表本質(zhì)上就是利用了離散化的思想。 離散化只是一個(gè)思想，實(shí)際上并沒(méi)有規(guī)定如何進(jìn)行離散化。離散化的可行方式有： 閱讀全文

摘要： 最長(zhǎng)公共子序列(LCS) 給出兩序列 v 1 , v 2 v1,v2 v1,v2，求它們最長(zhǎng)公共子序列長(zhǎng)度(子序列可以不連續(xù)) 長(zhǎng)度問(wèn)題 DP( O ( n 2 ) O(n^2) O(n2)) 閆氏DP分析法 注： v 1 , v 2 v1,v2 v1,v2下標(biāo)從 0 0 0開(kāi)始， d p dp d 閱讀全文

摘要： Raicom CAIP系列比賽歷年真題均在PTA教育超市售賣(mài)。本場(chǎng)比賽真題售賣(mài)鏈接入口 RC-u1 熱?熱?熱? 分?jǐn)?shù) 10 熱?熱?熱?……最近熱得打的字都出汗了！ 幸好某連鎖餐廳開(kāi)啟了氣溫大于等于 35 度即可獲得一杯免費(fèi)雪碧的活動(dòng)。但不知為何，在每個(gè)星期四的時(shí)候，這個(gè)活動(dòng)會(huì)暫停一天…… 現(xiàn)在給 閱讀全文

摘要： 完全背包 背包容量為 V V V，有 n n n種物品，每種物品有無(wú)限多個(gè)，第 i i i種物品體積為 c i c_i ci?，價(jià)值為 w i w_i wi?，怎樣裝填背包使總價(jià)值最大？ 實(shí)際上，完全背包并不代表每種物品可以真正裝填“無(wú)限”多個(gè)，因?yàn)榇嬖诒嘲傮w積這一限制因素。 分析:閆氏DP分析法 閱讀全文

摘要： 群友的問(wèn)題 快速冪 關(guān)鍵在于拆分 2 22 = 2 16 + 4 + 2 = 2 16 × 2 4 × 2 2 2^{22}=2^{16+4+2}=2^{16} \times 2^4 \times 2^2 222=216+4+2=216×24×22 10進(jìn)制快速冪: 高精次冪的解決方案 數(shù)論基礎(chǔ) 取 閱讀全文

摘要： 快速冪 分治法((指數(shù)折半法, O ( log ? 2 n ) O(\log_2 n) O(log2?n)) 思想：不斷 n ? 1 n\gg1 n?1，每次將指數(shù)折半計(jì)算 例： a 4 = ( ( a ) 2 ) 2 a^4=((a)^2)^2 a4=((a)2)2, a 5 = ( a 2 ? 閱讀全文