tag:blogger.com,1999:blog-6101425146514847182024-03-19T00:31:19.453-07:00日月卦長的模板庫日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.comBlogger97125tag:blogger.com,1999:blog-610142514651484718.post-38436748601330143642021-12-18T22:26:00.001-08:002021-12-18T22:26:38.610-08:00[Counting Sort, Radix Sort] 計數排序, 基數排序<p> Counting Sort是一種效率很高的排序方式,複雜度為$\ord{n+k}$,其中$k$是Bucket的大小,由此可知僅限於整數且數字範圍不能太大。根據觀察在很多應用中會有對物件以編號大小進行排序的行為,在這方面應該能做到很大的加速。</p><p>另外一個問題是Counting Sort雖然簡單,很多人甚至可以自己想到實作方法,但這也導致了標準的作法常常被人忽略。因此這裡就來給大家展示標準的Counting sort:</p><p><script src="https://gist.github.com/jacky860226/6f56ec7f8c6048dec6779ea32a51a1de.js?file=CountingSort.hpp"></script></p><p>參數的解釋如下:<br /></p><ul style="text-align: left;"><li>First, Last:<br />和std::sort的定義一樣,需要排序的範圍,注意不一定要是random access iterator。</li><li>BucketFirst, BucketLast:<br />Counting Sort正統的實作方式會有一個正整數陣列作為Bucket,考量到各種應用所以這裡接傳Bucket的範圍進來能做的優化會比較多,必須要是random access iterator。</li><li>OutputFirst:<br />Counting Sort的output是直接將input存到另一個陣列中,因此OutputFirst指的是Output陣列的開頭,必須要是random access iteator,且要注意output的空間是足夠的。這邊將input存進output時是用std::move的方式,如果想要保留原本input的話可以將其拿掉。</li><li>Key:<br />這是一個函數,Key(x)必須要回傳一個0~(BucketLast-BucketFirst-1)的正整數作為被排序物件x的關鍵值。</li></ul><div>有了Counting sort,Radix Sort就比較好解釋了。首先正統的Counting sort是stable sort,所以Key值相同的東西排序前後的先後順序是不變的。因此可以透過多次的Counting Sort來完成一些原本Counting Sort無法完成的事情。</div><div>以整數(int, -2147483648~2147483647)排序為例,可以先針對第十億位做為Key進行排序,接著再對第一億位做為Key、第一千萬位做為Key...直到十位數、個位數作為Key,最後再以正負號最為Key進行排序,這樣就可以完成一般範圍的整數排序。</div><div>實際上一般不會這樣用,通常是用在有多個Key值的情況,以下面的程式碼來說,可以自行執行看看花費的時間有多少:</div><div><br /><script src="https://gist.github.com/jacky860226/6f56ec7f8c6048dec6779ea32a51a1de.js?file=main.cpp"></script></div><p></p>日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-25249794885190670022021-12-13T06:11:00.004-08:002021-12-13T06:11:57.935-08:00[Discretizer] 離散化器<p>離散化是演算法競賽常用的操作,在各種實際問題上也能看到其應用。最基本的情況,是對於n個可排序的元素,製造一個map使得它們可以和自己的名次一一對應,但通常的應用中這n個元素確定之後就不太會有增減的動作,因此可以存到vector中排序去除重複的部分,搜索的部分就用二分搜尋來取代。</p>
<script src="https://gist.github.com/jacky860226/286bacaf5b75a1fbfe31fb2502a607ae.js"></script>日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-89911200741123073352021-08-13T01:09:00.000-07:002021-08-13T01:09:50.295-07:00[Multiple line segment intersection] Bentley–Ottmann 演算法<p> 基本上這個問題就是給你一些線段(格式通常為兩個端點),你要找出這些線段的交點。直觀的做法兩兩進行計算會花上$\ord{n^2}$的時間,但大多數的情況下交點不會很多。為了解決這個問題,修改自Shamos–Hoey演算法的Bentley–Ottmann演算法可以在$\ord{(n+k)\log n}$的時間內找出所有交點,其中$k$是交點數量。</p><p>這裡附上實作時需要用到的基本資料結構:</p><script src="https://gist.github.com/jacky860226/bf7912ff3ada0ff1d2210fbecc9cc71f.js?file=Basic.cpp"></script><p>演算法使用掃描線進行。掃描線是一條垂直線從左邊掃到右邊(有些實作是水平線從上面掃到下面),並且在遇到<b>事件點</b>的時候進行相關處理。</p><p>線段的兩端點以及交點都作為<b>事件點</b>被紀錄在最終結果中。對於每個事件點$P$,我們會計算三個集合:<br /></p><ul style="text-align: left;"><li>U集合:所有以$P$為起始點的線段集合</li><li>C集合:所有包含$P$的線段集合</li><li>L集合:所有以$P$為結束點的線段集合</li></ul><div>當然要先保證每條線段的起始點移動會在結束點的左方,只要得到線段後稍微判斷一下就可以做到了。每個事件點找出這三個集合後就可以很容易的判斷相交資訊,但要注意的是會有以下的退化情形:<br /><ul style="text-align: left;"><li>線段退化成點:這種情況該點的U和L都會包含該線段。</li><li>兩線段重合:只有重合處的兩端點會被紀錄為事件點,可以根據UCL判斷出是否線段重合</li><li>垂直線段:排序點和線段時如果x一樣就按照y來比較<br /></li></ul><div>最後是掃描線的資料結構,需要一棵平衡的BST根據當前掃描線和各個線段切點的y值進行排序,但這件事是可以用STL做到的!我們把當前事件點傳進比較函數裡面進行計算,因為在任何一個時刻BST中的資料都是根據當前的比較函數由小排到大的,應該不算undefined behavior。另外該演算法的浮點數誤差很大,建議使用時套上<a href="https://sunmoon-template.blogspot.com/2015/12/round-off-error-eps.html" target="_blank">處理誤差的模板</a>或是直接用分數計算:</div></div><div><script src="https://gist.github.com/jacky860226/bf7912ff3ada0ff1d2210fbecc9cc71f.js?file=SegmentIntersection.cpp"></script><br /></div><div>最後是測試的部分,以下圖做為測試範例:</div><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjtqgLATikpNxdDDHvs9tr5lRJofSta5qi-lyc3Bdxv0M-NnLNRXQJM1bc2s2a3rKaCyx8wfr4AG-k83gRP5u-2mL7LgsWAXYOUCIUN3QtTQhRhkV1qOAv7sGTUgTap5_cmD4eKSgwhsMHf/" style="margin-left: 1em; margin-right: 1em;"><img alt="" data-original-height="727" data-original-width="713" height="444" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjtqgLATikpNxdDDHvs9tr5lRJofSta5qi-lyc3Bdxv0M-NnLNRXQJM1bc2s2a3rKaCyx8wfr4AG-k83gRP5u-2mL7LgsWAXYOUCIUN3QtTQhRhkV1qOAv7sGTUgTap5_cmD4eKSgwhsMHf/w435-h444/GGGG.PNG" width="435" /></a></div><div class="separator" style="clear: both; text-align: left;">將該圖轉換成我們接受的input如下:</div><blockquote><div class="separator" style="clear: both; text-align: left;"><div class="separator" style="clear: both;">10</div><div class="separator" style="clear: both;">-2 7 2 0</div><div class="separator" style="clear: both;">-2 7 -2 0</div><div class="separator" style="clear: both;">-2 6 2 5</div><div class="separator" style="clear: both;">-2 6 2 2</div><div class="separator" style="clear: both;">-2 4 2 7</div><div class="separator" style="clear: both;">-2 4 2 2</div><div class="separator" style="clear: both;">-2 4 4 1</div><div class="separator" style="clear: both;">-2 0 2 2</div><div class="separator" style="clear: both;">0 1 0 1</div><div class="separator" style="clear: both;">0 3 4 1</div></div></blockquote><p>最後附上測試程式碼,需要的話可以自己執行看看:<br /><script src="https://gist.github.com/jacky860226/bf7912ff3ada0ff1d2210fbecc9cc71f.js?file=main.cpp"></script><br /></p><br /><p></p>日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-4632996076088124102019-08-01T23:22:00.000-07:002019-08-01T23:31:42.952-07:00[ Minimum Spanning Tree, kruskal, prim ] 最小生成樹經典演算法以前覺得這應該是很簡單的東西,但我發現網路上使用priority_queue的prim演算法相關程式碼我覺得寫不好,我就把我自己的放上來。這裡順便也放上kruskal的程式碼。<br />
<br />
prim $\ord{\left(\abs{V}+\abs{E}\right)\log{\abs{V}}}$:<br />
<script src="https://gist.github.com/jacky860226/03ff7645bd1b52c162890b63475fcec0.js?file=prim.cpp"></script>
kruskal $\ord{\abs{V}+\abs{E}\log{\abs{E}}}$:<br />
<script src="https://gist.github.com/jacky860226/03ff7645bd1b52c162890b63475fcec0.js?file=kruskal.cpp"></script>
日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-14293041588960777972019-01-29T04:08:00.000-08:002019-01-29T04:08:34.349-08:00[ Delaunay Triangulation ] Delaunay 三角剖分<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6s0oKB2etn4yPQfxgki2daB-gveGMFxCe-4_sp06yTxugNpvV1DBN9eJMUsngYK0o-0lTyajEeDd1Ymyf3DyMVUb8_Y82npTRMSASVHqyuzVd216l-JD5tGSg0o9y4xHwfnlhEDCKeiJh/s1600/%25E4%25B8%2589%25E8%25A7%2592%25E5%2589%2596%25E5%2588%2586.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="638" data-original-width="750" height="272" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi6s0oKB2etn4yPQfxgki2daB-gveGMFxCe-4_sp06yTxugNpvV1DBN9eJMUsngYK0o-0lTyajEeDd1Ymyf3DyMVUb8_Y82npTRMSASVHqyuzVd216l-JD5tGSg0o9y4xHwfnlhEDCKeiJh/s320/%25E4%25B8%2589%25E8%25A7%2592%25E5%2589%2596%25E5%2588%2586.PNG" width="320" /></a></div>
我高中的時候在<a href="http://morris821028.github.io/2014/12/05/uva-10397/" target="_blank">morris的網站</a>第一次看到這個東西,那個時候就很想試著寫出來看看,但那時候英文很不好所以不會找資料就沒有成功。直到今年的NPSC,聽說台大出了一題找Voronoi Diagram的題目沒有人寫出來,於是我就想挑戰看看,寒假開始之後就認真研讀相關資料,終於在前幾天完成了隨機增量法以及分治法的模板。<br />
<br />
先來說說甚麼是三角剖分 Triangulation 吧!假設平面上散布很多不重複的點,現在用一些線段將這些點連成許多的三角形,滿足所有三角形的內部不會有其他點,而且三角形的數量越多越好,這就是一個三角剖分。<br />
<br />
Delaunay Triangulation是一種特殊的三角剖分,滿足所有的三角形其外接圓中不會出現其他的點,這樣的性質會使得所有三角形中最小的角盡量大,而且最重要的是它是 Voronoi Diagram 的對偶圖,Voronoi Diagram 直接求的話很容易有浮點誤差而且程式也不好寫,因此從Delaunay Triangulation直接轉換過去會更加方便。<br />
<br />
還有一個很重要的點,透過Delaunay Triangulation 的邊集合可以找出平面歐幾里得距離最小生成樹。<br />
<br />
這裡我先給出點的資料結構,方便接下來的講解:<br />
<script src="https://gist.github.com/jacky860226/522e94ed7c14ff1564e9c1534dd6c7a4.js?file=point2D.cpp"></script>
<br />
一般來說找出 Delaunay Triangulation 的其中一個操作是要判斷一個點是不是在一個三角形的外接圓內,但直接去求外接圓圓心會有浮點誤差,因此有一個作法是將所有點投影到三維的拋物線曲面中,也就是下圖的碗狀曲面,會發現把一個圓投影上去之後,該圓會落在一個平面上,圓內的點會在平面下面,圓外的點會在平面上面,這樣就可以利用一些處理三維幾何的技術就可以避免浮點誤差的判斷點是否在外接圓內了。<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9wEo7tdRpJS79Julz_YMn7a9_zKb4zhk2B8lx1g30vBJoXLZtrYVcWjjXRL-aPxQfANZ7CZjufCXVx-_meWahtZEifRuDS5O-MqG_flYJ6fDG_HSo1PELON8PGhQkHZB6hcueI1t48vvW/s1600/%25E6%258B%258B%25E7%2589%25A9%25E5%258D%2580%25E9%259D%25A2%25E6%258A%2595%25E5%25BD%25B1.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="477" data-original-width="525" height="290" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9wEo7tdRpJS79Julz_YMn7a9_zKb4zhk2B8lx1g30vBJoXLZtrYVcWjjXRL-aPxQfANZ7CZjufCXVx-_meWahtZEifRuDS5O-MqG_flYJ6fDG_HSo1PELON8PGhQkHZB6hcueI1t48vvW/s320/%25E6%258B%258B%25E7%2589%25A9%25E5%258D%2580%25E9%259D%25A2%25E6%258A%2595%25E5%25BD%25B1.PNG" width="320" /></a></div>
<br />
範例程式碼中點在圓內輸出1,圓外輸出-1,圓上輸出0:<br />
<script src="https://gist.github.com/jacky860226/522e94ed7c14ff1564e9c1534dd6c7a4.js?file=inCircle.cpp"></script>
<br />
當然實作時並不會真正的寫一個三維點的資料結構,這樣程式碼會比較長。<br />
<br />
Delaunay Triangulation 我所知道的有兩種,分別是隨機增量法以及分治法。隨機增量法再點隨機加入的時候複雜度是$\ord{n\log n}$,分治法則是穩定$\ord{n\log n}$,但我的實作分治法的效能是隨機增量法的三倍快。由於兩種做法都已經有詳細教學了這裡就不用文字敘述。<br />
<br />
<ol>
<li>隨機增量法教學在《Computational Geometry - Algorithms and Applications》書中有提到,該書有中文版</li>
<li>分治法教學請點該<a href="http://www.geom.uiuc.edu/~samuelp/del_project.html" target="_blank">網站</a>連結</li>
</ol>
這裡附上程式碼,順帶一提morris的分治法好像在某些測資會因為三點共線爛掉<br />
<div>
<br /></div>
<div>
隨機增量法:</div>
<script src="https://gist.github.com/jacky860226/522e94ed7c14ff1564e9c1534dd6c7a4.js?file=DelaunayRandom.cpp"></script>
<div>
<br /></div>
<div>
分治法:</div>
<script src="https://gist.github.com/jacky860226/522e94ed7c14ff1564e9c1534dd6c7a4.js?file=DelaunayDivideAndConquer.cpp"></script>
<div>
<br /></div>
日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com2tag:blogger.com,1999:blog-610142514651484718.post-67246698968526307282018-12-31T07:52:00.000-08:002018-12-31T07:52:52.994-08:00[ Cyclic Longest Common Subsequence ] 環狀最長共同子序列相信會看我發的文的人應該多少都知道LCS(最長共同子序列)是什麼吧?對於這樣的問題很早以前就有人提出$\ord{nm}$的方法了。<br />
現在如果將問題中的字串改成頭尾相接環狀的字串,我們稱其最長共同子序列為CLCS,例如:<br />
<div style="text-align: center;">
設A,B為頭尾相接環狀字串</div>
<div style="text-align: center;">
A = "aabaa" , B = "aaabb"</div>
<div style="text-align: center;">
CLCS(A,B) = "aaab"</div>
<div style="text-align: left;">
像這樣的問題要怎麼解呢?剛好codeforces上面就有一題:<a href="http://codeforces.com/gym/100203/problem/B" target="_blank">http://codeforces.com/gym/100203/problem/B</a></div>
<div style="text-align: left;">
為了解決這一題,查閱了不少奇怪的文章,最後給我找到了這篇論文:<a href="https://arxiv.org/abs/1208.0396" target="_blank">Solving Cyclic Longest Common Subsequence in Quadratic Time</a></div>
<div style="text-align: left;">
對於CLCS提出了$\ord{nm}$的演算法,在這裡附上該演算法的實作:</div>
<div style="text-align: left;">
<script src="https://gist.github.com/jacky860226/504c2b7579fc75226bf38a92959f38ba.js?file=reRoot.cpp"></script><br /></div>
<div style="text-align: left;">
作法大致上是將b字串變成原來的兩倍,然後做一般的LCS,但在過程中要注意更新答案的順序。接著修改DP來源表格,每次將來源表格的第一個row刪掉(reRoot函數),然後計算當前的答案。<br />
<br />
當我AC這一題後,我看到了一個非常驚人的作法,也是用DP複雜度是$\ord{nm}$,但是我目前還無法完全理解為何這樣是可行的,而且這樣的做法我也不知道如何回溯找出一組解,只能知道CLCS的長度,希望路過的大大們能提供想法:
<script src="https://gist.github.com/jacky860226/504c2b7579fc75226bf38a92959f38ba.js?file=HV.cpp"></script><br />
<br /></div>
日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-38176363355081516502018-12-23T08:32:00.000-08:002018-12-23T08:36:10.212-08:00[ lower convex hull self-balancing binary search tree ] 下凸包平衡樹下凸包平衡樹是一個動態維護下凸包的資料結構,他至少能在$\ord{\log n}$時間完成以下兩個操作:<br />
<div>
<ol>
<li>查詢 point(x,y) 是否被包含於下凸包中</li>
<li>將 point(x,y) 加入至下凸包中,然後將不位於下凸包頂點上的點刪除</li>
</ol>
<div>
由於繼承自C++ STL map,因此所有能對map用的操作都能被使用,對於那些會改動map資料的操作請小心使用避免影響到凸包的正確性,例如operator[]就盡量不要使用。<br />
<br />
對於某些動態規劃問題需要用凸包斜率優化時應該非常有用,有空會補上專門用來動態做斜率優化的版本</div>
</div>
<div>
<br />
<script src="https://gist.github.com/jacky860226/cf476e744f60bdb3770233076e2a4ddb.js"></script>
</div>
日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-83179141037169708032018-11-30T09:05:00.002-08:002018-11-30T19:05:46.153-08:00[ simplex algorithm ] 線性規劃 - 單純形法<h2>
線性規劃簡介</h2>
<a href="https://zh.wikipedia.org/wiki/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92" target="_blank">線性規劃</a>是在線性約束條件下尋找某個目標線性函數的最大、最小值,例如:<br />
$$<br />
\begin{array}{lrl}<br />
\min& -3x_1+2x_2 & \\<br />
\mathrm{subject~to}<br />
&4x_1-6x_2&\le 5\\<br />
&5x_1-2x_2&\ge 7\\<br />
&x_1&\ge 0.<br />
\end{array}<br />
$$<br />
<br />
在最佳化問題中,線性規劃是非常重要的領域,很多的演算法問題都可以轉換成線性規劃問題來解決,例如:最大網路流、最大匹配等。因此研究如何系統化的解決線性規劃問題是非常重要的事情<br />
<br />
<h2>
線性規劃標準形</h2>
<div>
所有的線性規劃問題都可以轉換成下列標準型:</div>
<div>
$$<br />
\begin{array}{lrl}<br />
\max &\sum_{j=1}^n c_j \times x_j &\\<br />
\mathrm{subject~to}<br />
&\sum_{j=1}^n A_{i,j} \times x_j &\le b_j ,\; \forall i=1\sim m\\<br />
&x_j& \geq 0, \; \forall j = 1\sim n<br />
\end{array}<br />
$$<br />
<br />
一般來說大多數解線性規劃的演算法都會要求將問題轉換成標準形,因此務必要理解其轉換方法。轉換成標準形的步驟如下:<br />
<br />
<ol>
<li>將最小化改成最大化:<br />只要改變目標函數的正負號,即可將最小化問題改成標準型設定的最大化問題,也就是說$$\min \sum_{j=1}^n c_j \times x_j$$等價於$$\max \sum_{j=1}^n -c_j \times x_j$$</li>
<li>去除等式:<br />如果約束條件中存在等式,將其轉化為兩個分別為大於等於及小於等於的不等式取代,例如:<br />$$x_1+x_2=5$$等價於$$x_1+x_2 \le 5\\x_1+x_2 \ge 5$$</li>
<li>去除大於等於:<br />如果約束條件中存在大於等於約束,將約束兩邊取負即可,例如:<br />$$x_1+x_2 \ge 5$$ 等價於 $$-x_1-x_2 \le -5$$</li>
<li>去除自由變數:<br />如果未知數 $x_i$ 沒有非負約束,我們說 $x_i$ 是自由變數。加入新變量 $x_i'$,並用 $x_i-x_i'$替換原來的變量 $x_i$,並增加$x_i,x_i' \ge 0$的條件即可</li>
</ol>
<div>
標準化範例:</div>
</div>
<div>
$$<br />
\begin{array}{lrl}<br />
\min& -x_1+2x_2 & \\<br />
\mathrm{subject~to}<br />
&x_1+x_2&= 5\\<br />
&x_1-x_2&\le 2\\<br />
&x_2&\ge 0.<br />
\end{array}<br />
$$<br />
首先將最小化改成最大化:<br />
$$<br />
\begin{array}{lrl}<br />
\max& x_1-2x_2 & \\<br />
\mathrm{subject~to}<br />
&x_1+x_2&= 5\\<br />
&x_1-x_2&\le 2\\<br />
&x_2&\ge 0.<br />
\end{array}<br />
$$<br />
接著去除等式:<br />
$$<br />
\begin{array}{lrl}<br />
\max& x_1-2x_2 & \\<br />
\mathrm{subject~to}<br />
&x_1+x_2&\le 5\\<br />
&x_1+x_2&\ge 5\\<br />
&x_1-x_2&\le 2\\<br />
&x_2&\ge 0.<br />
\end{array}<br />
$$<br />
去除大於等於:<br />
$$<br />
\begin{array}{lrl}<br />
\max& x_1-2x_2 & \\<br />
\mathrm{subject~to}<br />
&x_1+x_2&\le 5\\<br />
&-x_1-x_2&\le -5\\<br />
&x_1-x_2&\le 2\\<br />
&x_2&\ge 0.<br />
\end{array}<br />
$$<br />
最後去除自由變數,將$x_1$用$x_1-x_3$取代:<br />
$$<br />
\begin{array}{lrl}<br />
\max& x_1-2x_2-x_3 & \\<br />
\mathrm{subject~to}<br />
&x_1+x_2-x_3&\le 5\\<br />
&-x_1-x_2+x_3&\le -5\\<br />
&x_1-x_2-x_3&\le 2\\<br />
&x_1,x_2,x_3&\ge 0.<br />
\end{array}<br />
$$<br />
<br />
<h2>
<span style="font-size: x-large;">
單純形法</span></h2>
</div>
<div>
<h2>
輸入input</h2>
</div>
<div>
本人實作的單純形法其輸入是一個被稱為單純形表的 $m+1 \times n+1$ 矩陣$A$,標準形中每個項目的值都可以對應到矩陣$A$上:<br />
$$<br />
\begin{array}{lrl}<br />
\max &\sum_{j=1}^n A_{0,j} \times x_j &\\<br />
\mathrm{subject~to}<br />
&\sum_{j=1}^n A_{i,j} \times x_j &\le A_{i,0} ,\; \forall i=1\sim m\\<br />
&x_j& \geq 0, \; \forall j = 1\sim n<br />
\end{array}<br />
$$<br />
可以發現:<br />
<br />
<ol>
<li>$A_{0,1} \sim A_{0,n}$對應標準形中的$c_1 \sim c_n$</li>
<li>$A_{i,0}$對應標準形中的$b_i ,\; \forall i=1\sim m$</li>
</ol>
為了方便計算請設$A_{0,0}=0$</div>
<div>
<br /></div>
<div>
上面標準化範例寫成單純形表為以下形式:</div>
<div>
$$<br />
\begin{bmatrix}<br />
0& 1 &-2 &-1 \\<br />
5 &1& 1 &-1 \\<br />
-5 &-1 &-1 &1 \\<br />
2 &1 &-1& -1<br />
\end{bmatrix}<br />
$$<br />
<h2>
輸出output</h2>
</div>
<div>
輸出為一個$size=n+1$的vector $ans$,其中:</div>
<div>
<ol>
<li>$ans[0]$為線性規劃的解,也就是最大值</li>
<li>$ans[1] \sim ans[n]$為變數$x_1 \sim x_n$的其中一組滿足條件的答案</li>
<li>如果無解或是解無限大則$ans$的$size=0$</li>
<li>注意如果答案是 $0$ 由於浮點數誤差的關係可能會產生 $``-0"$ 這種東西,要小心處理</li>
</ol>
上面標準化範例的解如下:</div>
<div>
$$\{0.5,\; 3.5,\; 1.5,\; 0\}$$</div>
<div>
意即在 $x_1=3.5,\;x_2=1.5,\;x_3=0$ 的情況下會有最大值 $x_1-2x_2-x_3=0.5$</div>
<h2>
<span style="font-size: x-large;">
程式碼</span></h2>
<div>
使用C++11</div>
<div>
<script src="https://gist.github.com/jacky860226/4354a8b7bb6c9148c1c6bfdedf5807d4.js"></script>
</div>
<h2>
<span style="font-size: x-large;">原理</span></h2>
<div>
有空時會補上,先讓我好好休息吧!終於可以正常睡覺了</div>
日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-58431463263873649582018-01-11T06:50:00.002-08:002018-01-11T06:50:34.712-08:00[ Implement Queue using Stacks ] 用堆疊實作佇列一般在C++ STL中queue都是用deque實作的,而deque用和vector類似的倍增法來實作(稍微多了一些操作導致常數有點大但是每次操作時間較為平均),雖然夠用但有些時候這不是一個好選擇。<br />
大二資料結構期中考時,考了一題叫你用stack實作queue的方法,我那時候想了一下想了一個超帥的作法,需要用到兩個stack,我把它成為stack A和B。<br />
<ul>
<li>push:<br />push時直接把資料push進B中,$\ord{1}$</li>
<li>pop:<br />這是個問題,我們把A的top當成是queue的front,所以直接把A pop就可以了,如果A是empty的話,就把B的資料依序pop然後push進A中,在進行該操作,均攤$\ord{1}$</li>
<li>front:<br />如pop所述,把A的top當成是queue的front,如果A是empty再另做處理,$\ord{1}$</li>
<li>back:<br />和front相反,把B的top當成是queue的back,如果B是empty再另做處理,$\ord{1}$</li>
</ul>
以下為實作過程,以c++ vector代替stack:<br />
<script src="https://gist.github.com/jacky860226/00507a0e719a9de820d7be4e6e502537.js"></script>
<br />日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com1tag:blogger.com,1999:blog-610142514651484718.post-29295650534163611322017-10-18T09:07:00.000-07:002017-10-18T09:07:56.939-07:00[ Median-of-Medians Algorithm ] 中位數演算法這是一個可以在保證線性時間(c++ std::nth_element是隨機演算法)找出一個序列中第k大元素的演算法,網路上已經有不少教學,但是很多人都認為常數太大因此缺乏實作。<br />
<br />
教學文在此:<a href="http://tmt514-blog.logdown.com/posts/484313-divide-and-conquer-method-iii-find-the-median" target="_blank">http://tmt514-blog.logdown.com/posts/484313-divide-and-conquer-method-iii-find-the-median</a> <br />
<br />
其實我高中時就想要試著去時做看看,但是因為那時的程式能力太差的關係,做出來的東西一直有bug,後來去忙其他事情後就被我忘掉了。最近因為學長面試有被問到一樣的問題跑來問我,才慢慢想起來有一份沒寫完的code,於是今天抱著不管怎樣都要寫出來的精神把他寫完了:<br />
<script src="https://gist.github.com/jacky860226/ccea3b5d21a0fab7c695f546ab128bc6.js"></script>
<br />
<br />日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-41005207370529601682017-10-13T21:54:00.002-07:002017-10-13T21:55:28.812-07:00[ C++ std::sort python implement ] C++std::sort Python實作最近有一個很靠北的課需要用python寫一些C++很容易做到的東西。<br />
這次我們被要求寫一個quick sort,但是他要求的做法實在太糟糕了,於是我就參考了C++ std::sort來實做了一個quick sort(不包含heap sort的部分):<br />
<script src="https://gist.github.com/jacky860226/a91bb8bce0a174adb8da5812592bb849.js?file=quick_sort.py"></script><br />
日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-11254518737332037332017-09-16T02:28:00.000-07:002017-09-16T02:39:39.112-07:00[ inorder postorder construct tree ] 用中序、後序建樹保證$\ord{N}$的方法昨天我學長因為要面試,所以努力地刷leetcode的題目,寫到了一題:<br />
<ul>
<li><a href="https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/" target="_blank">106. Construct Binary Tree from Inorder and Postorder Traversal </a> </li>
</ul>
他雖然AC了但是用的方法不太好,因此跑來問我有沒有看起來很帥速度又快的方法。 <br />
<br />
因為網路上的code都用一些很慢的方法來建樹,很多都$\ord{N^2}$,雖然也有看似$\ord{N}$的方法,但是用到像是unordered_map之類常數很大也不保證複雜度是$\ord{1}$(codeforces會卡內建hash)。<br />
<br />
因為我查到的code都太糟糕了,因此我決定自己寫一個複雜度保證為$\ord{N}$又好寫的方法。<br />
<br />
首先是找$root$的部分,因為有給後序的關係很容易就是到是誰了,但是找左右子樹就會出問題。經過觀察,只需要在dfs的過程用stack紀錄一些特別點就可以好好地維護左右子樹。<br />
<br />
假設現在dfs在點$u$,stack紀錄的點就是從$root$到$u$的路徑所有點中,除了那些左小孩也在該路徑中的點之外的所有點,有點複雜看個圖會比較明白,紅色的點就是記錄在stack中的點。<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgTRlD2LcOJVxuCrKrEytqlPQ2aIm8OjPa09Fm15MIRXMmEJJF9bH8ic3hKGgDacIO-Pmk6KZXujnrh-41_vs0TReM_wvGcTA1PSaFnAI9EJ7YwDanIq6y4I-bGIEo4ZcSxsTEe9cUXCtet/s1600/1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="790" data-original-width="524" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgTRlD2LcOJVxuCrKrEytqlPQ2aIm8OjPa09Fm15MIRXMmEJJF9bH8ic3hKGgDacIO-Pmk6KZXujnrh-41_vs0TReM_wvGcTA1PSaFnAI9EJ7YwDanIq6y4I-bGIEo4ZcSxsTEe9cUXCtet/s320/1.png" width="212" /></a></div>
<br />
至於為什麼記錄這些點就可以在dfs時判斷現在是不是NULL的節點,以及如果給的是preorder的情況就交給讀者思考了<br />
以下附上程式碼:<br />
<script src="https://gist.github.com/jacky860226/dfc95b0f9c8e9242033ed6a8917768b3.js?file=construct_tree.cpp"></script>
<br />
<br />日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-85938418310030876272017-05-12T00:39:00.000-07:002017-05-12T00:41:20.049-07:00[ Source code beautifier / syntax highlighter ] 在網頁/blog中插入彩色程式碼先看看結果吧:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #272822; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #75715e;">#define x first</span>
<span style="color: #75715e;">#define y second</span>
<span style="color: #75715e;">#include<bits/stdc++.h></span>
<span style="color: #66d9ef;">using</span> <span style="color: #66d9ef;">namespace</span> <span style="color: #f8f8f2;">std;</span>
<span style="color: #75715e;">#define X(){\</span>
<span style="color: #75715e;"> sdfgsdfg;\</span>
<span style="color: #75715e;"> sdfgsdfg;\</span>
<span style="color: #75715e;">}</span>
<span style="color: #66d9ef;">int</span> <span style="color: #a6e22e;">main</span><span style="color: #f8f8f2;">(){</span>
<span style="color: #75715e;">//asdfasdfdfsdfghd\</span>
<span style="color: #75715e;"> asdfasdfasdf\</span>
<span style="color: #75715e;"> asdfasdfsdf</span>
<span style="color: #66d9ef;">wchar_t</span> <span style="color: #f8f8f2;">wc;</span>
<span style="color: #f8f8f2;">cout</span><span style="color: #f92672;"><<</span><span style="color: #e6db74;">"Jinkela"</span><span style="color: #f92672;"><<</span><span style="color: #e6db74;">'\n'</span><span style="color: #f8f8f2;">;</span>
<span style="color: #f8f8f2;">cout</span><span style="color: #f92672;"><<</span><span style="color: #f8f8f2;">R</span><span style="color: #e6db74;">"jinkela(</span>
<span style="color: #ae81ff;">7122</span><span style="color: #f8f8f2;">)jinkela</span><span style="color: #e6db74;">";</span>
<span style="color: #f8f8f2;">cout</span><span style="color: #f92672;"><<</span><span style="color: #e6db74;">L"adsfasdf"</span><span style="color: #f92672;"><<</span><span style="color: #f8f8f2;">endl;</span>
<span style="color: #66d9ef;">return</span> <span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">;</span>
<span style="color: #75715e;">/*</span>
<span style="color: #75715e;"> asdf</span>
<span style="color: #75715e;"> */</span>
<span style="color: #f8f8f2;">}</span>
</pre>
</td></tr>
</tbody></table>
</div>
這是使用<a href="http://hilite.me/" target="_blank">http://hilite.me/</a> Style=monokai的結果,個人覺得效果不錯,只是raw string和一些比較難實作的東西沒有支援而已,其他的都還算可以<br />
<br />
我已經把這個網址加到我的學習連結裡面了,<a href="http://hilite.me/">C/C++ syntax highlighter (Style選monokai)</a>那個。用法就是貼上程式碼,設定好語言和style,把產生的html貼在你想貼的位置,蠻簡單的<br />
<br />
我在blog中如果程式碼量比較少我覺得沒必要加入模板也會用這個方法來貼code 日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-27713125822095003412017-04-30T00:09:00.000-07:002017-04-30T00:45:06.353-07:00[ Steiner tree problem in graphs ] 斯坦納樹斯坦納樹問題是一個世界知名的NP-hard問題。在圖論上的斯坦納樹是對於一張無向圖$G=(V,E)$以及一個點集合$P \subseteq V$,通常會稱$P$集合為$terminal \; set$,對於每條邊$e=(u,v) \in E$,令$w(e)$表示它的權重。我們的目標是要從$G$的所有子圖中找出一棵生成樹$T=(V',E')$,使得$P \subseteq V'$且$\sum_{e \in E'} w(e)$最小。<br />
<br />
簡單來說就是在圖$G$上找一棵子樹,可以把$P$中的點連通起來,且邊權總和最小 <br />
<br />
如果我們枚舉所有子圖,對每個子圖做最小生成樹演算法,就一定可以找到斯坦納樹,但是複雜度是$\ord{(\abs E + \abs V log \abs V ) \times 2^{\abs V}}$,非常糟糕。<br />
<br />
如果$w(e)>0 ,e \in E$,且$\abs P \ll \abs V$,我們可以找到一個動態規劃的方法:<br />
令$dp[S][i]$表示以點$i$為根,以$S \subseteq P$為$terminal \; set$構造出來的斯坦納樹,這樣我們最後的答案就會是$dp[P][u \in P]$<br />
<br />
狀態轉移式可以寫成這樣<br />
<ul>
<li>$dp[S][i]=min(dp[T][j]+dp[S-T][j]+dis(i,j)\; : \; j \in V,T \subset S)$<br />$dis(i,j)$表示$i \sim j$的最短路徑</li>
</ul>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgk2kVKvMYgC8x-Vn1czl28orlP1v8B55NAG6gRybRQ3Ww6eK-y8AOixVZPQWge0FLbapvNVnU0zpkauUVJLws4W-IXfNanhvNCKDJDaJRxsbd90cEPno-CQOhR6B9O1P8DesN9C8PSJKL9/s1600/steiner_tree.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="315" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgk2kVKvMYgC8x-Vn1czl28orlP1v8B55NAG6gRybRQ3Ww6eK-y8AOixVZPQWge0FLbapvNVnU0zpkauUVJLws4W-IXfNanhvNCKDJDaJRxsbd90cEPno-CQOhR6B9O1P8DesN9C8PSJKL9/s320/steiner_tree.png" width="320" /> </a></div>
任兩點間的最短路徑可以用floyd在$\ord {\abs V^3}$預先算出來,狀態有$2^{\abs P}\times \abs V$個,狀態轉移為$\ord{\abs V \times 枚舉子集合的時間}$,因此總複雜度為$\ord{\abs V^3+2^{\abs P} \times \abs V^2 \times 枚舉子集合的時間 }$<br />
<br />
其中 $2^{\abs P} \times 枚舉子集合的時間$ 只是粗略的計算,實際上它是<br />
$$\sum_{i=1}^{\abs P} \binom{\abs P}{i} \times (2^i -1) \simeq \sum_{i=0}^{\abs P} \binom{\abs P}{i} \times 2^i = (1+2)^{\abs P} = 3^{\abs P}$$因此總複雜度可以表示為$\ord{V^3+3^{\abs P} \times \abs V^2}$,但是這其實還可以優化,令$H[j] = min(dp[T][j]+dp[S-T][j] \; : \;T \subset S)$<br />
則$dp[S][i]=min(H[j]+dis(i,j)\; : \;j \in \abs V)$<br />
$H$是可以被預先算出來的,因此總複雜度就降為$\ord{\abs V^3 + \abs V 3^{\abs P}+\abs V^2 2^{\abs P}}$<br />
以下附上程式碼:<br /><script src="https://gist.github.com/jacky860226/cf1a551c4ad9700ee2c80efffaa9f716.js?file=Steiner_tree_floyd.cpp"></script>
<br />
有的時候圖是稀疏圖,也就是$\ord V=\ord E$,這種時候用這種算法效率其實不是很好,我們可以在dp的過程才用一些單源最短路徑算法算出最短路徑,這樣複雜度可以變成$$\ord{\abs V 3^{\abs P}+ShortestPath(G) 2^{\abs P}}$$其中$ShortestPath(G)$是在圖$G$中計算最短路徑的時間,用dijkstra的話是$\ord{\abs E+\abs V log \abs V}$,這裡我用SPFA實作:<script src="https://gist.github.com/jacky860226/cf1a551c4ad9700ee2c80efffaa9f716.js?file=Steiner_tree_SPFA.cpp"></script><br />日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-2396766865774866712017-04-27T08:19:00.000-07:002017-04-28T01:13:00.256-07:00[ gcc Built-in Functions for binary ] gcc內建處理二進位函數以下介紹的函數都是非標準的函數,他只能在GCC底下使用,不過一般的比賽環境都是支援的,所以熟記起來可以增加寫位元運算的效率<br />
<br />
<br />
<ol>
<li>int __builtin_ffs (unsigned int x)<br />int __builtin_ffsl (unsigned long)<br />int __builtin_ffsll (unsigned long long)<br /><ul>
<li>返回右起第一個1的位置</li>
<li>Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.</li>
</ul>
</li>
<li>int __builtin_clz (unsigned int x)<br />int __builtin_clzl (unsigned long)<br />int __builtin_clzll (unsigned long long)<br /><ul>
<li>返回左起第一個1之前0的個數</li>
<li>Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.</li>
</ul>
</li>
<li>int __builtin_ctz (unsigned int x)<br />int __builtin_ctzl (unsigned long)<br />int __builtin_ctzll (unsigned long long)<br /><ul>
<li>返回右起第一個1之後的0的個數 </li>
<li>Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.</li>
</ul>
</li>
<li>int __builtin_popcount (unsigned int x)<br />int __builtin_popcountl (unsigned long)<br />int __builtin_popcountll (unsigned long long)<br /><ul>
<li>返回1的個數</li>
<li>Returns the number of 1-bits in x.</li>
</ul>
</li>
<li>int __builtin_parity (unsigned int x)<br />int __builtin_parityl (unsigned long)<br />int __builtin_parityll (unsigned long long)<br /><ul>
<li>返回1的個數的奇偶性(1的個數 mod 2的值)</li>
<li> Returns the parity of x, i.e. the number of 1-bits in x modulo 2. </li>
</ul>
</li>
</ol>
這種內建函數其實非常多,這邊有附上一個GCC內建函數的列表,有興趣的朋友可以參考<br />
<a href="https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html" target="_blank">https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html</a><br />
<br />
當你在GCC環境下,想直接用01寫二進位的東西,其實有簡單的方法:<br />
<ul>
<li> cout<<0b1010101;</li>
<li>cout<<0b1010101LL;</li>
</ul>
這樣你的編譯器應該會警告你說這是GCC內建的東西(C++14以後的版本會支援它),但是還是會正確執行,都是85,個人覺得蠻方便的<br />
<br />
如果你是用C++11,可以用stoi,stol,stoll,stoul,stoull等函數來把二進位字串轉成int,long,long long,unsigned long,unsigned long long等,可以設定他用二進位轉換,像是這樣:<br />
<ul>
<li>cout<<stoi("1010101",NULL,2);</li>
<li>cout<<stoll("1010101",NULL,2);</li>
</ul>
<br />
另外有些編譯器會在<algorithm>實作std::__lg(n)這個函數,他會回傳$\floor{log_2n}$的值,可以參考這個<br />
<a href="http://stackoverflow.com/questions/40434664/what-is-std-lg" target="_blank">http://stackoverflow.com/questions/40434664/what-is-std-lg</a>日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-6337476746708982002017-02-12T01:02:00.000-08:002017-02-12T07:07:31.254-08:00[ Amortized analysis - Potential method ] 平攤分析 - 勢能方法對於一個stack操作,pop和push都是$\ord{1}$的,這很好理解,現在定義了一個新的操作,pop_all,表示pop stack內的所有元素,顯然這是一個$\ord{N}$的操作。那我們進行一連串的push、pop、pop_all的複雜度上界是多少呢?<br />
<br />
根據big-O的特性,因為pop_all是$\ord{N}$的,我們把每個操作都當作$\ord{N}$來看,執行$N$次操作的總複雜度就會是$\ord{N^2}$。這沒有錯,但怎麼想都覺得怪怪的,怎麼可能一直執行pop_all呢?執行一次pop_all之後stack就沒有元素了耶!<br />
<br />
這三種操作不是平行的,而是互相影響的。換言之,你每次的push創造“機會”給pop和pop_all。pop和pop_all才能“消費”著這些機會,不存在無限制的消費。<br />
<br />
因此這個複雜度是高估的,那要究竟怎麼真正去計算$N$次操作的總複雜度呢?<br />
<br />
<h3>
勢能方法</h3>
對於一個資料結構$DS$,我們定義$\Phi(DS)$表示$DS$的“勢能”,而且要保證在任何情況下$\Phi(DS) \geq 0$。<br />
<br />
通常$\Phi(DS)$我們會定義他是$DS$的某個性質,像是元素個數啦,如果是二元樹的話可能是所有節點左子樹大小減右子樹大小的絕對值的總和啊、或是葉節點的個數啊...各種東西都可以當作是$DS$的勢能。<br />
<br />
那$\Phi(DS)$能用來幹甚麼?我們定義$\Phi_0$表示$DS$在還沒有進行任何操作時的勢能,假設有$N$個操作,第$i$個操作的時間花費為$t_i$,這個操作結束之後的勢能為$\Phi_i$,$i>0$,我們定義第$i$個操作的均攤時間$a_i=t_i+C(\Phi_i-\Phi_{i-1})$,這裡$C>0$是一個常數<br />
<br />
可以發現總均攤花費時間:<br />
$$<br />
\sum^{N}_{i=1}a_i=\sum^{N}_{i=1}(t_i+C(\Phi_i-\Phi_{i-1})) \\<br />
=(t_1+t_2+...+t_n)+C(-\Phi_0+(\Phi_1-\Phi_1)+(\Phi_2-\Phi_2)+...+(\Phi_{n-1}-\Phi_{n-1})+\Phi_n) \\<br />
=\sum^{N}_{i=1} t_i +C(\Phi_N-\Phi_0)<br />
$$<br />
最後得到:<br />
$$<br />
\sum^{N}_{i=1}t_i=\sum^{N}_{i=1}a_i-C(\Phi_N-\Phi_0)<br />
$$<br />
這個特性告訴我們,只要好好選擇$\Phi(DS)$函數,就可以在$\ord{\sum^{N}_{i=1}t_i}$很難直接求的情況下透過$\ord{\sum^{N}_{i=1}a_i-C(\Phi_N-\Phi_0)}$求出$\ord{\sum^{N}_{i=1}t_i}$。<br />
<br />
<h3>
證明範例</h3>
有了勢能方法,可以很輕鬆的用它來計算一些資料結構操作的均攤複雜度。<br />
<br />
以剛剛stack的例子來說,我們設定stack $S$它的勢能函數$\Phi(S)$為$S$的元素個數,可以確定$\Phi_0=0$且$\Phi(S) \geq 0$。<br />
<br />
我們設一次的push、一次的pop花費一單位的時間,並設常數$C=1$,在第$i$次操作:<br />
<ul>
<li>如果是push操作的話$t_i=1$,stack的元素個數增加$1$<br />因此$\Phi_i-\Phi_{i-1}=1$<br />$a_i=t_i+\Phi_i-\Phi_{i-1}=1+1=2$</li>
<li>如果是pop操作的話$t_i=1$,stack的元素個數減少$1$<br />因此$\Phi_i-\Phi_{i-1}=-1$<br />$a_i=t_i+\Phi_i-\Phi_{i-1}=1-1=0$</li>
<li> 如果是pop_all操作的話$t_i=n$,stack的元素個數減少$n$<br />因此$\Phi_i-\Phi_{i-1}=-n$<br />$a_i=t_i+\Phi_i-\Phi_{i-1}=n-n=0$</li>
</ul>
$a_i$的最大值是$2$,經過$N$次操作之後$\Phi_N-\Phi_0$的最小值為$0$<br />
可以知道:<br />
$$<br />
\ord{\sum^{N}_{i=0}t_i}=\ord{\sum^{N}_{i=1}a_i-(\Phi_N-\Phi_0)}=\ord{2N+0}=\ord{N}<br />
$$<br />
因此經過$N$次stack的任何有效操作之後,總花費的時間為$\ord{N}$,這才是我們滿意的結果。<br />
<br />
對了,通常來說$\Phi_0$都會是0,因此在大部分的情況下:<br />
$$<br />
\ord{\sum^{N}_{i=0}t_i}=\ord{\sum^{N}_{i=1}a_i}<br />
$$<br />
所以大部分的證明都會忽略掉$\Phi_N-\Phi_0$的部分日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-28997674977044911782017-02-07T08:48:00.001-08:002017-02-09T00:30:20.261-08:00[ Minimum Arborescence / zhu_liu ] 朱劉算法 - 最小樹形圖在有向圖中,給定一個點$r$作為生成樹的根,找出有向圖最小生成樹。<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiKILz4jmnUX4tnRtVPFfFKCWE15p-YH9RLvt84pS_fHb-FmY8tpNuTJXXN_Pl_trww3DCivedWFcPAgXadOGDjAoTezWCcbA4sQ_PAyj1ZFcjTRh6G2bYYofephtP5vUUWNH_PYNS-jajX/s1600/%25E7%25AF%2584%25E4%25BE%258B1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiKILz4jmnUX4tnRtVPFfFKCWE15p-YH9RLvt84pS_fHb-FmY8tpNuTJXXN_Pl_trww3DCivedWFcPAgXadOGDjAoTezWCcbA4sQ_PAyj1ZFcjTRh6G2bYYofephtP5vUUWNH_PYNS-jajX/s320/%25E7%25AF%2584%25E4%25BE%258B1.png" width="280" /></a></div>
<br />
首先我們要能保證從$r$能夠走到圖上的所有點,這樣生成樹才會存在,這很簡單,一次DFS即可,再來是把圖上的所有自環移除,因為一顆樹裡面很明顯是不會有自環的。<br />
<br />
之後就是算法的主要步驟了,可以先想一下,除了$r$以外的每一個點都有一條儘可能小的邊指向自己,最好的情況就是我們枚舉每一個點(除了根節點)並找到最小的一條指向這個點的邊,如果這些邊不構成有向環,就形成了一個所求的最小樹形圖。<br />
<br />
但是實際上會出現環啊,但是這些環一定是獨立的,為甚麼呢?因為只有$|V|-1$條邊啊,只有是一棵樹的時候才會是連通的狀態。換句話說,如果圖連通了,就一定是最小樹形圖。<br />
<br />
我們嘗試去換一些邊,使圖連通,在換的過程中我們總是選擇較小的邊,那麼得到的就是最小樹形圖。你可能會去枚舉一些邊把有向環拆掉,但是這樣的話可能會產生新的有向環,不是一個好做法。<br />
<br />
朱劉算法就不直接去換邊,它也不去拆掉環,而是在不增加邊的情況下讓圖連通,怎麼做呢?就是用一個新的點代替原來圖的一個環(也就是所謂的「縮點」,和強連通分量有點像),並且修改跟這個環裡的點有關的邊的權值。<br />
<br />
為何要修改邊的權重呢?當我們每更換一個點的入邊的時候我們就要去掉原來那個入邊,於是我們把這個點所有可能的入邊全部減少原來選取的那個入邊的權值,這樣每增加一條入邊無形中就刪去了原來那條邊。<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhMBtF-7-9OxfPXWx8A8eADw0q3RBhlbkmy6fQNTRQNbxEKyk_Jdid05J_iB-wVS5MT3jA0Ab_21JvhMtWFNG-F-sHXlTgSD2Hk2dSZRQHdtrnKBkdoESwOpkttPVMGjczWPt9fOo67Oq04/s1600/%25E7%25AF%2584%25E4%25BE%258B2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="259" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhMBtF-7-9OxfPXWx8A8eADw0q3RBhlbkmy6fQNTRQNbxEKyk_Jdid05J_iB-wVS5MT3jA0Ab_21JvhMtWFNG-F-sHXlTgSD2Hk2dSZRQHdtrnKBkdoESwOpkttPVMGjczWPt9fOo67Oq04/s320/%25E7%25AF%2584%25E4%25BE%258B2.png" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div style="text-align: center;">
上圖中紅色部分是要進行縮點的有向環</div>
<div style="text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiqHY_icT7VWePt9pb1cki5pxDtg5KauY5mJTBmCc6aRtQLfD7yVfbMJmUe-Jmr_-GR81DMpy_Ew_lLSKzV0m1xcHSdqp-XZNIRoFQcdk5fTlQGjHEDJz6ky1XyjdxouTu-_NkCom-K6HkI/s1600/%25E7%25AF%2584%25E4%25BE%258B3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="249" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiqHY_icT7VWePt9pb1cki5pxDtg5KauY5mJTBmCc6aRtQLfD7yVfbMJmUe-Jmr_-GR81DMpy_Ew_lLSKzV0m1xcHSdqp-XZNIRoFQcdk5fTlQGjHEDJz6ky1XyjdxouTu-_NkCom-K6HkI/s320/%25E7%25AF%2584%25E4%25BE%258B3.png" width="320" /></a></div>
<div style="text-align: center;">
每個環上的點所有可能的入邊全部減少原來選取的那個入邊的權值</div>
<div style="text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgm3tmYKPNRuKUX_94f3Uomk8fsC-W3kBKS_nM0tkkCYZry8uqHES7sDcE97rHfmcBmCMLYcpBhKfc1hpgSINVPx-BATv-bGP7k7PSUIn-vZLDvhsosO4JNnQ-rnkwVnEXJwaacr2jXGNkk/s1600/%25E7%25AF%2584%25E4%25BE%258B4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="158" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgm3tmYKPNRuKUX_94f3Uomk8fsC-W3kBKS_nM0tkkCYZry8uqHES7sDcE97rHfmcBmCMLYcpBhKfc1hpgSINVPx-BATv-bGP7k7PSUIn-vZLDvhsosO4JNnQ-rnkwVnEXJwaacr2jXGNkk/s320/%25E7%25AF%2584%25E4%25BE%258B4.png" width="320" /></a></div>
<div style="text-align: center;">
接著把環縮成一個點就可以了</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
假設我們想要把原來縮環之前3那條邊換成4那條邊,那我們換完的結果如下:</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiUymG6kyOmfbv0TrMVz9oYtxGiDTXrTyq1kmpyY742FwjVGfCWUSo2Mt5rPEw94zDapxOv9fgnT1GjpIfiajmnBj-8lHnXZFIXvn6l1N4BDz1rCuCK-OGPQ_3SAuN0cEHGvtVMXJLGYy_q/s1600/%25E7%25AF%2584%25E4%25BE%258B5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="259" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiUymG6kyOmfbv0TrMVz9oYtxGiDTXrTyq1kmpyY742FwjVGfCWUSo2Mt5rPEw94zDapxOv9fgnT1GjpIfiajmnBj-8lHnXZFIXvn6l1N4BDz1rCuCK-OGPQ_3SAuN0cEHGvtVMXJLGYy_q/s320/%25E7%25AF%2584%25E4%25BE%258B5.png" width="320" /></a></div>
可以發現修改邊權後,不需要把邊刪掉,直接去計算選取邊的權重和就會和換邊的結果一樣<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEikFfDy5InAEkKq-nRUMXresVdq268VWdCGUOnt_F7mQ7YAMvXbKgwlyQdY9121SVPTHK1Gj4YS6Mrx3e-t_KRRyCg7HHrg-KsJhebky-HfQP65N3Qmd037LPQpudjh7Otxl7yfTbia6Slp/s1600/%25E7%25AF%2584%25E4%25BE%258B6.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="249" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEikFfDy5InAEkKq-nRUMXresVdq268VWdCGUOnt_F7mQ7YAMvXbKgwlyQdY9121SVPTHK1Gj4YS6Mrx3e-t_KRRyCg7HHrg-KsJhebky-HfQP65N3Qmd037LPQpudjh7Otxl7yfTbia6Slp/s320/%25E7%25AF%2584%25E4%25BE%258B6.png" width="320" /></a></div>
朱劉算法主算法的過程就是:找最小入邊->判斷有沒有環(沒有環就退出,算法成功)->縮點,改權值,如此反覆,一般來說為了方便不會去記錄縮點後虛擬節點裡包含了那些點,如果需要找出最小樹形圖包含的邊,就必須要真的去記錄他。<br />
<br />
時間複雜度來說的話,用當時論文提出的實作方式,修改邊權的部分為$\ord{|E|}$,縮點最多執行$|V|-1$次,所以總複雜度是$\ord{|V|*|E|}$。<br />
我自己有想了一個$\ord{|E| \; log \; |E|}$的方法,需要用到一種可以合併和把裡面所有元素加上某個值 的heap,又因為每個點最多只會連出去$|V|-1$條邊,也就是heap裡面只有$|V|$個元素是有用的,所以可以在heap大小為$2|V|$時把後$|V|$個元素刪掉,用斐式堆可以做到$\ord{|E|+|V| \; log|V|}$。<br />
<br />
以下為$\ord{|V|*|E|}$的code:<br />
<script src="https://gist.github.com/jacky860226/2bfab8dc4ca6c8f5e34fcabbba50eec1.js?file=zhu_liu.cpp"></script>
接著是$\ord{|E| \; log^2|E|}$的code,使用啟發式合併(感謝59491、編譯器幫忙debug):<br />
<script src="https://gist.github.com/jacky860226/2bfab8dc4ca6c8f5e34fcabbba50eec1.js?file=zhu_liu_logMlogM.cpp"></script>
接著是$\ord{|E| \; log|E|}$的code,使用skew heap:<br />
<script src="https://gist.github.com/jacky860226/2bfab8dc4ca6c8f5e34fcabbba50eec1.js?file=zhu_liu_logM.cpp"></script>日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com1tag:blogger.com,1999:blog-610142514651484718.post-88549275757029963102016-12-07T06:28:00.000-08:002016-12-07T06:34:17.709-08:00[ 0-1 Fractional Programming Dinkelbach algorithm ] 0-1分數規劃【定義】<br />
<br />
給你兩個數組,$benefit[i]$表示選$i$的利潤、$cost[i]$表示選$i$的花費。<br />
如果選$i$,定義$x[i]=1$否則$x[i]=0$,通常題目會給你選擇的限制條件,像是必須是一顆生成樹之類的,這裡就把它忽略掉<br />
我們的目標是要求$\frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}$的最大值。<br />
<br />
【分析】 <br />
<br />
先不管最大化問題,令$\frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}=L$<br />
可以把式子改寫成$(\sum{benefit[i] \times x[i]})-L \times (\sum{cost[i] \times x[i]})=0$<br />
分離參數得到$\sum{(benefit[i]-L \times cost[i]) \times x[i]}=0$<br />
只要知道$L$,$(benefit[i]-L \times cost[i])$是直接可以求出來的,先記他為$d(i,L)$吧<br />
那可以設$f(L)=\sum{d(i,L) \times x[i]}$ <br />
<br />
我們的目標變成是要最大化$L$ <br />
那若存在一種$x$的選法使得$f(L)>0$能夠證明什麼呢? <br />
$f(L)>0 \to \frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}>L$那表示存在另一個$L$會比現在的$L$還要好<br />
那 $f(L)<0$?很明顯這種情況完全沒有意義,因為找不到這種$L$<br />
<br />
最佳的$L$會讓所有$x$的選法都$f(L)\leq0$,只要找到這樣的$L$就說明他是最佳解了<br />
也可以用類似的想法求最小化$L$,這裡就不贅述了。<br />
<br />
【解法】<br />
<br />
根據剛剛找出來的性質$f(L)$是單調性的,我們可以二分搜$L$,然後驗證是否存在一組解使得$f(L)>0$,這很簡單就不附code了。<br />
另一個有效率的算法是Dinkelbach,他跟二分搜不一樣的地方是他要去求解,在驗證解跟求解的複雜度一樣的時候Dinkelbach是會比較快的,但有時候求解的複雜度會比驗證解的複雜度還要高,因此要看情況使用<br />
以下附上虛擬碼:<br />
<script src="https://gist.github.com/jacky860226/e0905365f5dff00557d1cf4220b6ba28.js?file=Dinkelbach.cpp"></script>
<br />
常見的題型有:最優比率環、最優比率生成樹、最大密度子圖(有flow解)等
日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com2tag:blogger.com,1999:blog-610142514651484718.post-72370763318586676472016-12-06T07:56:00.000-08:002019-06-26T01:53:15.472-07:00[ dominator tree ] 有向圖的支配樹dominator tree,中文名稱叫支配樹<br />
給一張有向圖$G$,我們從其中一個點$r$出發到$y$的所有路徑中,一定會經過點$x$,就稱$x$是$y$的必經點;我們把距離$y$最近的必經點稱為最近必經點,記為$idom(y)$。<br />
支配樹上的有向邊$(u,v)$滿足$idom(v)=u$,那對於一個點$y$,$y$的所有必經點就會是支配樹上$r$到$y$路徑上的所有點。<br />
這個東西可以求有向圖的割點、橋(在每個邊加入虛擬點)等等。<br />
注意code裡的$idom$跟我定義的不一樣<br />
我是看<a href="https://github.com/Misaka233/algorithm/blob/master/%E6%9D%8E%E7%85%9C%E4%B8%9C%EF%BC%9A%E5%9B%BE%E8%BF%9E%E9%80%9A%E6%80%A7%E8%8B%A5%E5%B9%B2%E6%8B%93%E5%B1%95%E9%97%AE%E9%A2%98%E6%8E%A2%E8%AE%A8.pdf" target="_blank">這份講義</a>的偽代碼寫出來的:<br />
<br />
<script src="https://gist.github.com/jacky860226/f21f71e8a6347cf4447eb7eb846aec12.js?file=dominator_tree.cpp"></script>日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-87679126157508895142016-11-03T01:12:00.000-07:002016-11-03T22:11:45.095-07:00[ Pi algorithms - John Machin's formula ] 梅欽公式計算圓周率我們知道 <br />
$$\frac{\pi}{4}= \arctan 1$$<br />
而$\arctan(x)$的泰勒展開式長這樣<br />
$$\arctan(x)=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\frac{x^9}{9}- \cdots \; (x \leq 1)$$<br />
故可以求出<a href="https://zh.wikipedia.org/zh-tw/%CE%A0%E7%9A%84%E8%8E%B1%E5%B8%83%E5%B0%BC%E8%8C%A8%E5%85%AC%E5%BC%8F" target="_blank">莱布尼茨公式</a>如下:<br />
$$\frac{\pi}{4}= 1 \,-\, \frac{1}{3} \,+\, \frac{1}{5} \,-\, \frac{1}{7} \,+\, \frac{1}{9} \,-\, \cdots$$<br />
但是這用來計算$\pi$到小數點後指定位數是非常困難的,因此有了以下的<a href="https://zh.wikipedia.org/zh-tw/%E6%A2%85%E6%AC%BD%E9%A1%9E%E5%85%AC%E5%BC%8F" target="_blank">梅欽公式</a>:<br />
$$\frac{\pi}{4} = 4 \arctan \frac{1}{5} - \arctan \frac{1}{239}$$<br />
再用泰勒展開,可以得到:<br />
$$\pi=(\frac{16}{5} - \frac{16} {3*5^3} + \frac{16}{5 * 5^5} - \frac{16} {7 * 5^7} + \cdots) \\ - (\frac{4}{239} - \frac{4}{3 * 239^3} + \frac{4}{5 * 239^5} - \frac{4}{7 * 239^7} + \cdots)$$<br />
可以將這個公式整理為:<br />
$$\pi=\frac{\frac{16}{5} - \frac{4}{239}}{1} -\frac{\frac{16}{5^3} - \frac{4}{239^3}}{3} + \frac{\frac{16}{5^5} - \frac{4}{239^5}}{5} - \cdots$$<br />
如果我們要計算圓周率至10的負$L$次方,由於$\frac{16}{5^{2*n-1}} - \frac{4}{239^{2*n-1}}$中$\frac{16}{5^{2*n-1}}$比$\frac{4}{239^{2*n-1}}$來的大,具有決定性,所以表示至少必須計算至第n項:<br />
$$\frac{16}{(2*n-1)*5^{2*n-1}}=10^{-L}$$<br />
將上面的等式取log並經過化簡,我們可以求得(誤差什麼得先不管它):<br />
$$n =\frac{L}{2log_{10} 5} = \frac{L}{1.39794}$$<br />
這樣就可以計算$\pi$到小數點後第$L$位了<br />
<br />
這裡有其他可以快速算出圓周率的梅欽類公式<br />
<a href="http://jeux-et-mathematiques.davalan.org/calc/formulespi.pdf" target="_blank">http://jeux-et-mathematiques.davalan.org/calc/formulespi.pdf</a><br />
<br />日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-39761740838001752712016-10-28T05:47:00.000-07:002016-10-30T09:49:16.401-07:00[ Earley parser ] Earley語法解析器有一天蚯蚓跟我說CYK算法很慢,推薦了這個東西,所以我就把他寫出來了。<br />
他主要是先建構出類似於自動機的圖,有很多個狀態在跳來跳去,在我的實作裡有將其轉成語法樹的方法。<br />
這裡需要自己實作的有lexer,還有最後的語法一定要有一個gamma rule,gamma rule就是有一個$gamma \Longrightarrow S$,$S$是初始符號。<br />
首先是語法規則的部分:<br />
<script src="https://gist.github.com/jacky860226/e12f07f0aa522cef498434bb13b79a08.js?file=rule.cpp"></script>
<br />
這是分析器的本體,lexer的部分要自己去完成,lexer的結果會是parse的第二個參數,計算出來一些資料會存在table裡面<br />
以下為模板:<br />
<script src="https://gist.github.com/jacky860226/e12f07f0aa522cef498434bb13b79a08.js?file=parser.cpp"></script>
<br />
最後是構造語法樹的部分,因為div是一顆左兄弟右兒子的樹,所以要將她轉換成正常的語法樹,還要去記錄曖昧文法的部分:<br />
<script src="https://gist.github.com/jacky860226/e12f07f0aa522cef498434bb13b79a08.js?file=build_tree.cpp"></script>
<br />日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-5781945508621993312016-10-11T08:42:00.000-07:002016-10-27T20:39:39.783-07:00[ Cocke-Younger-Kasami algorithm ] CYK算法它是一個用來判定任意給定的字符串是否屬於某一個上下文無關文法的算法,還可以順便構造出二元語法樹和判斷是否有曖昧文法(Ambiguous Grammar)。對於一個任意給定的上下文無關文法,都可以使用CYK算法來計算上述問題,所以它是一個幾乎萬能的算法,但首先要將該文法轉換成<a href="https://zh.wikipedia.org/wiki/%E4%B9%94%E5%A7%86%E6%96%AF%E5%9F%BA%E8%8C%83%E5%BC%8F" target="_blank">喬姆斯基範式</a>(CNF)。<br />
這個算法主要是利用動態規劃的思想,給一個有$n$個字符的字符串s,和$R$條語法規則,則他的計算複雜度為$\ord{n^3R}$,空間複雜度為$\ord{n^2R}$。類似於optimal binary search tree的算法,對於每個s[l,r]我們去計算s[l,k]和s[k+1,r]能符合的所有規則。<br />
<br />
我們用2016 NCPC的題目當例子<br />
這裡給一個簡單的範例,給你一個語法規則如下 :<br />
$<br />
A \Longrightarrow AAAAAAA \qquad 20 \\<br />
A \Longrightarrow AA \qquad 15 \\<br />
A \Longrightarrow a \qquad 5<br />
$<br />
如果看不懂的,他大約的意思如下:<br />
一個合法字串$A$可以是七個合法字串$A$所組成,也可以是兩個合法字串$A$所組成,也可以是小寫字母$a$所組成。<br />
每個規則都給他一個權重,表示經過這個規則的轉換會有這些花費,我們會給一個目標字串,要找出把整個字串轉換成$A$的最小花費,例如給定字串$aaaaaaaa$,他的最小花費就是75。<br />
這裡舉另一個例子:<br />
$<br />
A \Longrightarrow BA \qquad 10 \\<br />
A \Longrightarrow bcd \qquad 5 \\<br />
B \Longrightarrow c \qquad 4<br />
$<br />
給定字串$ccbcd$,他的最小花費就是33。<br />
當然也會發生無法轉換的情況,這個時候叫要輸出$NIR$ 。<br />
<br />
首先必須要把規則轉成喬姆斯基範式,這裡我以數字當作規則的名稱,當y=-1時表示這個cnf是s->x的規則,否則是s->xy的規則。<br />
<script src="https://gist.github.com/jacky860226/8988df3c6f1bdb79f826726214467e00.js?file=make_cnf.cpp"></script>
接著就可以跑我們的演算法啦:<br />
<script src="https://gist.github.com/jacky860226/8988df3c6f1bdb79f826726214467e00.js?file=CYK.cpp"></script>
當然它也可以用來判斷是不是有曖昧語法(ambiguous),只要做一些小修改就行了
日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-30640993941269300812016-10-03T04:51:00.000-07:002016-10-03T04:51:58.589-07:00[ cantor expansion ] 康托展开給一個$0 \sim n-1$共$n$個數字的全排列,求他是排名第幾的全排列;給一個名次,求全排列。這東西可以有效的減少hash_table的大小。<br />以下附上code:<br />
<script src="https://gist.github.com/jacky860226/6fadb185b834b5ab6b949b1d5ca29153.js?file=cantor_expansion.cpp"></script><br />
使用前記得要呼叫init();
日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-5578312085795355512016-10-01T20:18:00.000-07:002017-05-29T23:39:54.966-07:00[ closest pair of points ] 平面上歐基里德距離最近點對用分治法寫的,複雜度$\ord{n\log^2 n}$:<br />
<script src="https://gist.github.com/jacky860226/fcb498df1f3938fd2f12b4f78a30ff96.js?file=closest_pair_of_points.cpp"></script>
日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0tag:blogger.com,1999:blog-610142514651484718.post-68237226191856833572016-08-05T18:26:00.001-07:002016-08-05T18:26:18.412-07:00[ tree centroid ] 樹重心一棵無向樹\(T=(V,E)\),定義:<br />
\(w_v(u)\)為點\(u\)的權重,\(u \in V\)<br />
\(w_e(e)\)為邊\(e\)的權重,\(e \in E\)<br />
\(d(u,v)\)為\(u\)到\(v\)路徑的權重和,\(u,v \in V\)<br />
<br />
重心的定義是:<br />
以這個點為根,那麼所有的子樹(不算整個樹自身)的大小都不超過整個樹大小的一半<br />
即為最大的子樹最小的點 <br />
<br />
廣義的樹的重心:<br />
無向樹\(T=(V,E)\)滿足<br />
\(w_v(u)≧0, \; \forall u \in V \)<br />
\(w_e(e)>0, \; \forall e \in E \)<br />
設<br />
\(c(u)=\sum_{v \in V}d(u,v)*w_v(v)\)<br />
則樹重心 \(tree \; centroid=u \; | \; min(\{c(u):u \in V\})\)<br />
<br />
在 <br />
\(w_v(u)=1, \; \forall u \in V \)<br />
\(w_e(e)=1, \; \forall e \in E \)<br />
的情況下,就是一般的樹重心<br />
<br />
性質: <br />
<ol>
<li>把兩個樹通過一條邊相連得到一個新的樹,那麼新的樹的重心在連接原來兩個樹的重心的路徑上。</li>
<li>把一個樹添加或刪除一個葉子,那麼它的重心最多只移動一條邊的距離。</li>
</ol>
用途:<br />
樹分治、動態求樹重心等 <br />
<br />
可以利用DFS找出最大的子樹最小的點,即為樹重心 <br />
樹重心求法(用vector存無向樹):<br />
<script src="https://gist.github.com/jacky860226/1b2c7fa794c34c5a2f55313ac9656fb7.js?file=tree_centroid.cpp"></script>
日月卦長http://www.blogger.com/profile/15332849545715365500noreply@blogger.com0