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