Profile cover photo
Profile photo
黃兆源
神功門門人
神功門門人
About
Posts

Post has attachment
[ Implement Queue using Stacks ] 用堆疊實作佇列
一般在C++ STL中queue都是用deque實作的,而deque用和vector類似的倍增法來實作(稍微多了一些操作導致常數有點大但是每次操作時間較為平均),雖然夠用但有些時候這不是一個好選擇。 大二資料結構期中考時,考了一題叫你用stack實作queue的方法,我那時候想了一下想了一個超帥的作法,需要用到兩個stack,我把它成為stack A和B。 push: push時直接把資料push進B中,$\ord{1}$ pop: 這是個問題,我們把A的top當成是queue的front,所以直接把A po...

Post has attachment
[ Median-of-Medians Algorithm ] 中位數演算法
這是一個可以在保證線性時間(c++ std::nth_element是隨機演算法)找出一個序列中第k大元素的演算法,網路上已經有不少教學,但是很多人都認為常數太大因此缺乏實作。 教學文在此: http://tmt514-blog.logdown.com/posts/484313-divide-and-conquer-method-iii-find-the-median 其實我高中時就想要試著去時做看看,但是因為那時的程式能力太差的關係,做出來的東西一直有bug,後來去忙其他事情後就被我忘掉了。最近因為學長面試...

Post has attachment
[ C++ std::sort python implement ] C++std::sort Python實作
最近有一個很靠北的課需要用python寫一些C++很容易做到的東西。 這次我們被要求寫一個quick sort,但是他要求的做法實在太糟糕了,於是我就參考了C++ std::sort來實做了一個quick sort(不包含heap sort的部分):

Post has attachment
[ inorder postorder construct tree ] 用中序、後序建樹
昨天學長因為要面試,所以努力地刷leetcode的題目,寫到了一題: 106. Construct Binary Tree from Inorder and Postorder Traversal    他雖然AC了但是用的方法不太好,因此跑來問我有沒有看起來很帥速度又快的方法。 因為網路上的code都用一些很慢的方法來建樹,很多都$\ord{N^2}$,雖然也有看似$\ord{N}$的方法,但是用到像是unordered_map之類常數很大也不保證複雜度是$\ord{1}$(codeforces會卡內建ha...

Post has attachment
[ Source code beautifier / syntax highlighter ] 在網頁/blog中插入彩色程式碼
先看看結果吧: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 #define x first #define y second #include<bits/stdc++.h> using namespace std; #define X(){\ sdfgsdfg;\ sdfgsdfg;\ } int main (){ //asdfasdfdfsdfghd\ asdfasdfasdf\ asdfasdfsdf wchar_t w...

Post has attachment
[ Steiner tree problem in graphs ] 斯坦納樹
斯坦納樹問題是一個世界知名的NP-complete問題。在圖論上的斯坦納樹是對於一張無向圖$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)$最小。 簡單來說就是在圖$G$上找一棵子樹,可以把$P$中的點連通起來,且邊權總...

Post has attachment
[ gcc Built-in Functions for binary ] gcc內建處理二進位函數
以下介紹的函數都是非標準的函數,他只能在GCC底下使用,不過一般的比賽環境都是支援的,所以熟記起來可以增加寫位元運算的效率 int __builtin_ffs (unsigned int x) int __builtin_ffsl (unsigned long) int __builtin_ffsll (unsigned long long) 返回右起第一個1的位置 Returns one plus the index of the least significant 1-bit of x, or if x ...

Post has attachment
[ glibc Built-in Functions for binary ] glibc內建處理二進位函數
以下介紹的函數都是非標準的函數,他只能在GNU底下使用,不過一般的比賽環境都是支援的,所以熟記起來可以增加寫位元運算的效率 int __builtin_ffs (unsigned int x) int __builtin_ffsl (unsigned long) int __builtin_ffsll (unsigned long long) 返回右起第一個1的位置 Returns one plus the index of the least significant 1-bit of x, or if x ...

Post has attachment
[ Amortized analysis - Potential method ] 平攤分析 - 勢能方法
對於一個stack操作,pop和push都是$\ord{1}$的,這很好理解,現在定義了一個新的操作,pop_all,表示pop stack內的所有元素,顯然這是一個$\ord{N}$的操作。那我們進行一連串的push、pop、pop_all的複雜度上界是多少呢? 根據big-O的特性,因為pop_all是$\ord{N}$的,我們把每個操作都當作$\ord{N}$來看,執行$N$次操作的總複雜度就會是$\ord{N^2}$。這沒有錯,但怎麼想都覺得怪怪的,怎麼可能一直執行pop_all呢?執行一次pop_a...

Post has attachment
[ Minimum Arborescence / zhu_liu ] 朱劉算法 - 最小樹形圖
在有向圖中,給定一個點$r$作為生成樹的根,找出有向圖最小生成樹。 首先我們要能保證從$r$能夠走到圖上的所有點,這樣生成樹才會存在,這很簡單,一次DFS即可,再來是把圖上的所有自環移除,因為一顆樹裡面很明顯是不會有自環的。 之後就是算法的主要步驟了,可以先想一下,除了$r$以外的每一個點都有一條儘可能小的邊指向自己,最好的情況就是我們枚舉每一個點(除了根節點)並找到最小的一條指向這個點的邊,如果這些邊不構成有向環,就形成了一個所求的最小樹形圖。 但是實際上會出現環啊,但是這些環一定是獨立的,為甚麼呢?因為只...
Wait while more posts are being loaded