[程式] codeforces 166C: Median

[題意] 給兩個正整數 n (n <= 500) 跟 x (x <= 100,000)，並且再給你一串含有 n 個數字的陣列 A，問如果要讓 A 經過排序後的中位數是 x 的話最少要往 A 裡面加入幾個數字？

[程式] Heavy Light Decomposition (重輕分解；樹鍊剖分)

Heavy Light Decomposition 台灣這邊的翻譯是直譯，所以是叫 "重輕分解"；而中國那邊是採意譯，所以叫 "樹鍊剖分"。這與其說是一種資料結構，倒不如說是一種概念，其基本概念是把一棵樹 (tree) 拆成數條一維陣列，如此一來在這棵樹上的所有查詢 (query)抑或是更新 (update) 都可以在對數時間內完成。詳細的概念可以參考這篇，演算法筆記上的這篇上有列出時間複雜度。

[隨筆] 這是一篇關於棋靈王誕生的故事

研替進成功嶺 12 天的時間裡，其實大多數時間都是在聽演講。演講這回事兒呢，主題跟講者的技巧只要一個稍差就會挺無聊的。想當然爾，這 12 天的時間裡其實絕大部份時間都是挺無聊要想辦法找事情打發時間這樣。說是這樣說，成功嶺裡手邊能拿到的材料也只有紙跟筆，能用這兩項材料做出甚麼事情打發時間就考驗創意 & 記憶力了。這次進成功嶺就在這樣的環境中親眼見證了同袍被長官封為棋靈王的瞬間。

是的，這是一篇關於棋靈王誕生的故事。

[程式] 不用除法的最大公因數 (GCD)

有不少數論 (Number Theory) 的計算中都會用到找兩個正整數的最大公因數 (greatest common divisor, GCD)，而最基本常用找最大公因數的方法中就是利用輾轉相除法 (Euclidean algorithm)，如下

$gcd(x, y) = gcd(y, x - q \times y)$

其中 q 為任意整數，下面的這段程式實作出輾轉相除法的概念：

int gcd(int x, int y)
{
 while ((x %= y) && (y %= x)) ;
 return (x + y);
}

然而，在現在處理器中求餘數的運算時間相較於基本的加減法以及位元運算 (bitwise operation) 是慢很多的，因此 Knuth 的 TAOCP (The Art of Computer Programming) 中的第 4.5.2 節就有提到其實曾經有人提出了另一種方法，僅僅使用位元運算以及加減法來找最大公因數。

[程式] 最近共同祖先 (Lowest Common Ancestor - LCA)

LCA 算是 tree 滿容易用上的一項特性，原因在於找出任意兩點 u, v 的 LCA 後 (假設是 w)，通常問題可以拆解為：

• (u -> w) + (v -> w): 這樣的兩條路徑各自求解後合併

LCA 的找法可以參考演算法筆記中的 Jump Pointer Algorithm，他的基本概念就是對每個 node 的前 1、2、4、8 ... (2^n) 倍的祖先，如此一來，假設要知道一個 node 的前 5 代祖先是誰，只要知道他的前一代祖先的前四代祖先是誰就可以了。(簡單來說，看成用二進位表示法就知道這種儲存方式可以得知任意一個點的任意一代的祖先囉)

透過這種方法，對任意 2 點 u, v，我們可以知道最後的共同的祖先必然是 root，從上往下追蹤直到出現分歧為止，這就是最近的共同祖先拉。

[程式] Segment Tree (線段樹)

Segment Tree 是個用空間來交換時間的資料結構，特別適合用在搜尋次數極為龐大的時候。其所需的額外空間約為既有資料的兩倍 (空間複雜度是 O(N)!)，時間複雜度則為 O(log(N))。

[筆記] Codeforces 920E: Connected Components?

[題意] 給一個有 n 個點的 undirected simple graph，並且告訴你這個 graph 中有 m 條邊被拿掉了，問有幾個 connected components？並且把 connected component 的大小由小到大印出來。

[程式] 排容原理實作 (inclusion-exclusion principle implementation)

由於先前這一篇會用到排容原理，因此就花了點時間研究排容原理要怎麼實作比較好。不過這玩意兒因為只是個原則，實作方法會根據要處理的問題有些許差別，這邊的實作針對的是以下的問題：

給定兩個正整數 $n$ 跟 $x$，要找出有多少正整數 $y$ 使得 $y < n \ \& \ gcd(y, x) = 1$，其中 $gcd$ 代表最大公因數

[筆記] Codeforces 920G: List Of Integers

[題意] 給定任意正整數 p, 則 L 是一串與 p 互質的序列 L(p) = {y | gcd(y, p) = 1}，且 L 是由小到大排序的 (gcd 就是最大公因數)。再給任一正整數 x，求 L 中比 x 大的第 k 個數值。

[隨筆] 第一場博士論文口試 (校內口試)

歷經各種狀況後，原定計畫是去年 9 月就能口試，結果各種投稿不順利就一路的延到現在終於可以口試了，算一算差了大約快半年 Orz 在這期間還發現系上對於博士口試還非常囉嗦，各種資格審查 & 行政文件要跑...雖然正式的口試還沒開始，不過就先記錄一下今天的前哨戰：校內口試吧