[Discretize Relabeling] 離散化器

離散化是演算法競賽常用的操作，在各種實際問題上也能看到其應用。最基本的情況，是對於n個可排序的元素，製造一個map使得它們可以和自己的名次一一對應，但通常的應用中這n個元素確定之後就不太會有增減的動作，因此可以存到vector中排序去除重複的部分，搜索的部分就用二分搜尋來取代。

[ Cyclic Longest Common Subsequence ] 環狀最長共同子序列

相信會看我發的文的人應該多少都知道LCS(最長共同子序列)是什麼吧？對於這樣的問題很早以前就有人提出$\ord{nm}$的方法了。
現在如果將問題中的字串改成頭尾相接環狀的字串，我們稱其最長共同子序列為CLCS，例如：

設A,B為頭尾相接環狀字串

A = "aabaa" , B = "aaabb"

CLCS(A,B) = "aaab"

像這樣的問題要怎麼解呢？剛好codeforces上面就有一題：http://codeforces.com/gym/100203/problem/B

為了解決這一題，查閱了不少奇怪的文章，最後給我找到了這篇論文：Solving Cyclic Longest Common Subsequence in Quadratic Time

對於CLCS提出了$\ord{nm}$的演算法，在這裡附上該演算法的實作：

作法大致上是將b字串變成原來的兩倍，然後做一般的LCS，但在過程中要注意更新答案的順序。接著修改DP來源表格，每次將來源表格的第一個row刪掉(reRoot函數)，然後計算當前的答案。

當我AC這一題後，我看到了一個非常驚人的作法，也是用DP複雜度是$\ord{nm}$，但是我目前還無法完全理解為何這樣是可行的，而且這樣的做法我也不知道如何回溯找出一組解，只能知道CLCS的長度，希望路過的大大們能提供想法：

[ 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 pop就可以了，如果A是empty的話，就把B的資料依序pop然後push進A中，在進行該操作，均攤$\ord{1}$
• front:
  如pop所述，把A的top當成是queue的front，如果A是empty再另做處理，$\ord{1}$
• back:
  和front相反，把B的top當成是queue的back，如果B是empty再另做處理，$\ord{1}$

以下為實作過程，以c++ vector代替stack：

[ 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，後來去忙其他事情後就被我忘掉了。最近因為學長面試有被問到一樣的問題跑來問我，才慢慢想起來有一份沒寫完的code，於是今天抱著不管怎樣都要寫出來的精神把他寫完了：

[ 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 wc; cout<<"Jinkela"<<'\n'; cout<<R"jinkela( 7122)jinkela"; cout<<L"adsfasdf"<<endl; return 0; /* asdf */ }

這是使用http://hilite.me/ Style=monokai的結果，個人覺得效果不錯，只是raw string和一些比較難實作的東西沒有支援而已，其他的都還算可以

我已經把這個網址加到我的學習連結裡面了，C/C++ syntax highlighter (Style選monokai)那個。用法就是貼上程式碼，設定好語言和style，把產生的html貼在你想貼的位置，蠻簡單的

我在blog中如果程式碼量比較少我覺得沒必要加入模板也會用這個方法來貼code

[ Maze generation-Randomized Kruskal's algorithm ] 迷宮生成-隨機Kruskal算法

說得通俗點，就是"隨機拆牆"。
一開始假設所有牆都在，也就是圖的每個點都不連通。如果當前不滿足“任意兩個格子間都有唯一路徑”，那麼就隨機選擇一堵牆，要求牆兩端的格子不連通，即它們對應的兩個頂點在兩個不同的連通分量。把這堵牆拆掉，即在後牆兩端的格子對應的頂點間建立一條邊。重複作下去，直到所有的點都在同一個連通分量裡面。
會發現這就是隨機合併點的Kruskal演算法，需要用到並查集

範例生成圖:
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
＃　　　＃　　　　　　　＃　　　＃　　　　　　　＃
＃＃＃　＃　＃　＃　＃＃＃　＃＃＃＃＃＃＃　＃＃＃
＃　　　　　＃　＃　　　＃　　　＃　＃　　　　　＃
＃＃＃＃＃＃＃＃＃　＃＃＃　＃　＃　＃＃＃＃＃　＃
＃　　　　　　　＃　＃　　　＃　　　＃　　　　　＃
＃＃＃　＃＃＃　＃　＃　＃　＃＃＃　＃＃＃　＃＃＃
＃　　　＃　　　＃　　　＃　　　＃　　　　　　　＃
＃＃＃　＃　＃＃＃＃＃　＃＃＃　＃＃＃＃＃　＃＃＃
＃　　　＃　　　　　　　＃　＃　　　　　＃　＃　＃
＃＃＃＃＃＃＃　＃　＃＃＃　＃　＃＃＃＃＃＃＃　＃
＃　　　＃　＃　＃　　　＃　　　　　　　＃　＃　＃
＃　＃＃＃　＃＃＃　＃＃＃　＃　＃＃＃＃＃　＃　＃
＃　＃　　　　　＃　＃　　　＃　＃　＃　＃　＃　＃
＃　＃　＃＃＃　＃　＃＃＃　＃＃＃　＃　＃　＃　＃
＃　＃　＃　　　　　＃　　　＃　　　　　　　　　＃
＃　＃　＃＃＃　＃＃＃＃＃＃＃＃＃　＃　＃＃＃＃＃
＃　　　＃　　　＃　＃　＃　　　　　＃　　　＃　＃
＃＃＃＃＃＃＃　＃　＃　＃　＃　＃＃＃　＃＃＃　＃
＃　　　　　＃　　　　　　　＃　　　＃　　　　　＃
＃　＃　＃＃＃＃＃　＃＃＃＃＃＃＃＃＃　＃　＃＃＃
＃　＃　　　　　　　　　　　　　　　＃　＃　　　＃
＃＃＃　＃　＃　＃＃＃　＃　＃＃＃＃＃＃＃　＃＃＃
＃　　　＃　＃　　　＃　＃　　　＃　　　　　　　＃
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃

code(n,m必須是奇數):

[ Karatsuba Multiply ] 大數模板乘法Karatsuba法

複雜度大約是\(\ord{N^{log3}}\)，約為\(\ord{N^{1.5}}\)比一般直式乘法還快，附上連結:
Karatsuba算法

附模板，配合大數模板使用:

[ print itself ] 印出自己的code

一個會輸出自己的code:

可以看一下輸出:http://codepad.org/ZFGeRjkn

英文字母大小寫轉換特殊做法

假設有一個題目是這樣的:
        給定一串英文字母，請將大寫的部分轉成小寫，小寫的部分轉成大寫並輸出

一般我們會用if或是三元運算子做判斷，但是這太麻煩了
經過觀察發現，摁合一個小寫字母ascii與其對應的大寫字母ascii相差皆為32，
而其二進位編碼剛好允許透過 xor 32的方式進行轉換，但是32這個數字不好記，又可以發現ascii 32='空白'，而以下的code就可以將大小寫互換:

1 2 3 4 5 6 7 8

#include<stdio.h> char s[1000005]; int main(){ scanf("%s",s); for(int i=0;s[i];++i)putchar(s[i]^' ');puts(""); for(int i=0;s[i];++i)putchar(s[i]^32);puts(""); return 0; }

兩種寫法會有相同的效果

[ Big Interger ] 大數模板

今天在家裡寫了一整天的大數，好不容易加減乘除都有了，但是乘法的部分FFT還不會寫所以先用做基本的n^2乘法(聽說有一個奇怪的方法叫做Karatsuba演算法也能做大數乘法，還蠻快的)

定義一個大數:
bigN a;//定義大數

以下是大數模板:

在函式中傳入使用者自定函式的方法(C++ Functor 仿函式)

一般來說在函式中傳入使用者自定函式通常會用函數指標
但是C++ template提供了一個較為便利的函數參數，以物件的方式傳入
可支援一般函數或利用重載()運算子所定義的物件
詳情請看代碼:

CODE轉HTML

CodeToHtml這套軟體，可以很輕鬆的將code轉成HTML語法，本站所有的code都是由他轉換的。
下載

HTML Encoder

http://www.opinionatedgeek.com/DotNet/Tools/HTMLEncode/Encode.aspx
http://formatmysourcecode.blogspot.tw/
透過這個網站
可以讓你的code轉換成符合HTML的格式
就可以貼在網站上瞜!!!