清北第二天，感受到了來自這個世界的不友善，大概把沒聽過不會的“名詞”記錄下來就已經(jīng)一面了，然后被大佬說這都是最基礎(chǔ)的東西，就很皮，那就趁別人練習(xí)字符串的題的時候，來寫波博客了，倒不是不想寫，（MD這么快就KMP，Hash，Manacher，AC自動機(jī)，Tire樹，我毛都不會啊沒法寫啊，講的巨難，詳細(xì)也聽不懂啊，上來一個指針就蒙了）
不扯沒意思的，從早上開始積累的問題慢慢總結(jié)吧。
1、倍增：第一次聽到這個詞是懵逼的，然后什么樹上倍增的直接讓我就傻逼了，實(shí)際上在之前有次上課的時候，老師提了一句話，現(xiàn)在想起來倒是發(fā)現(xiàn)體現(xiàn)了倍增的思想，倍增倍增，成倍增加，就是在算Nm的時候，可以直接把m拆成2*4*8*16*32*……，那么這個2 4 8 16 32 這一連串就體現(xiàn)了倍增的思想，加快了化學(xué)反應(yīng)速率算法的的速度，提高效率，避免了不必要的重復(fù)計(jì)算。
2、樹：可謂有各種奇葩的不奇葩的麻煩的難的樹，今天講的大概有如下幾個幾百個：生成樹、最大生成樹、最小生成樹、LCA最近公共祖先、線段樹、樹狀數(shù)組、樹上倍增、有根樹、重構(gòu)樹、虛樹、樹剖等……
一個一個來：
生成樹：如果連通圖G的一個子圖是一棵包含G的所有頂點(diǎn)的樹，則該子圖稱為G的生成樹(SpanningTree)。生成樹是連通圖的包含圖中的所有頂點(diǎn)的極小連通子圖。
最小生成樹：一個有 n 個結(jié)點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結(jié)點(diǎn)，并且有保持圖連通的最少的邊。即最小權(quán)重生成樹，每個邊所帶的權(quán)重值的和最小即為最小生成樹。
嚴(yán)格次小生成樹：
最大生成樹：與最小生成樹相對，每個邊所帶的權(quán)重值和最大即為最大生成樹。
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動安全 [無線安全]玩轉(zhuǎn)無線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識別反義詞同義詞 2017-07-26
- 從棧不平衡問題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式