椰蘿Yerosius的博客

摘要： Shell概念 本系列博客為MIT的《Missing in CS Class(2020)》的課程筆記。 注:<>或^在本文中指Ctrl，如c或^c指Ctrl-c 終端(命令行,CLI) <Alt+T>：打開終端 <L>：清空終端內(nèi)容 流的概念 文件被視為連續(xù)的字節(jié)流進行處理。文件分為普通文件與設(shè)備文 閱讀全文

摘要： 字符串模式匹配(一)——單模匹配(KMP) 單模匹配的常用算法為KMP，多模匹配常用算法為AC自動機。 暴力匹配法(BF, O ( ∣ S ∣ × ∣ T ∣ ) O(|S|\times |T|) O(∣S∣×∣T∣)) 設(shè)源串 S S S的匹配指針為 i i i，模式串 T T T的匹配指針為 j 閱讀全文

摘要： 線段樹 模板題:線段樹1-洛谷(代碼) 線段樹是一種平衡二叉樹，其核心思想為二分+分治+懶標記，可在 O ( log ? 2 n ) O(\log_2n) O(log2?n)的復(fù)雜度內(nèi)完成單點修改、區(qū)間修改、區(qū)間查詢等操作。 設(shè)原序列長度為 n n n，則每個節(jié)點 i d ( 1 ≤ i d ≤ 4 閱讀全文

摘要： 字符串基礎(chǔ)概念 字符串：簡稱串，是由字符組成的有限序列。串中所包含的字符個數(shù)為串長，串長為0的串為空串。串長與所有對應(yīng)位置字符都相同的串為相等串，空串一定為相等串。子串、子序列：設(shè)從原串 S S S某一位置開始，若以連續(xù)順序取 S S S中若干長度的字符，所組成的新串 S ′ S' S′即為 S S 閱讀全文

摘要： Johnson 本質(zhì)：SPFA+Dijkstra特點：多源最短路適用對象：允許負權(quán)圖，不允許負環(huán)圖(負環(huán)：圖上邊權(quán)之和為負的環(huán)，負環(huán)圖無法求解最短路)存儲結(jié)構(gòu)：鏈式前向星核心思想：先使用SPFA/Bellman-Ford計算潛在值，將所有邊的權(quán)值調(diào)整為非負，再對每個頂點使用Dijkstra算法流程： 閱讀全文

摘要： 最短路計數(shù) 算法流程：在最短路算法中另設(shè)置一個 d p dp dp數(shù)組用于計數(shù)最短路，并將源點的 d p [ S ] = 1 dp[S]=1 dp[S]=1。在松弛操作時： if(dis[V]==dis[U]+W) dp[V]+=dp[U]; if(dis[V]>dis[U]+W){ dis[V]= 閱讀全文

摘要： 堆 堆是一種在頻繁插入刪除情形下，仍能高效獲取序列最值的數(shù)據(jù)結(jié)構(gòu)。堆頂為樹根，始終保持所有元素的最優(yōu)值。堆總是一棵完全二叉樹，稱為二叉堆，因此其存儲結(jié)構(gòu)中定位其子節(jié)點無需left和right。堆可分類為大根堆、小根堆。 在堆中的任意節(jié)點，其總<=(大根堆,less)或>=(小根堆,greater)其 閱讀全文

摘要： SPFA 本質(zhì)：DP，基于隊列優(yōu)化的Bellman-Ford 特點：單源最短路，求解一個源點到其他所有點的最短距離，不穩(wěn)定 適用對象：允許負權(quán)圖，不允許負環(huán)圖(負環(huán)：圖上邊權(quán)之和為負的環(huán)，負環(huán)圖無法求解最短路)，同時也可求最長路。 存儲結(jié)構(gòu)：鏈式前向星 核心思想：用隊列保存松弛邊的出度點，調(diào)整其鄰接 閱讀全文

摘要： Raicom CAIP系列比賽歷年真題均在PTA教育超市售賣。本場比賽真題售賣鏈接入口 RC-u1 大家一起查作弊 分數(shù) 15 在今年的?？贡荣惿?，有同學(xué)的提交代碼如下： public asfiasfgwef12(){ int tsadflas=3; int masf11233=2; int[]wa 閱讀全文

摘要： 倍增 倍增是與二分相反的算法，其核心思想是每次擴大一倍，以 2 n 2^n 2n的速度極大擴展空間 原理：任意整數(shù)均可被分解為若干個以2為底的冪項和。最經(jīng)典的倍增是 2 i 2^i 2i(實際應(yīng)為 e i e^i ei) 流程：定義倍增表 g [ i ] [ j ] g[i][j] g[i][j], 閱讀全文