有哪些令人拍案叫絕的演算法？

Python2

C++, FFT

--------------------------------------------2016.11.21----------------------------------
感謝知友給的RP。noip好像沒掛太慘。

莫隊演算法也是令人拍案叫絕的演算法呢…………有時間的時候來寫一寫吧。

隨便聊幾個，有大有小，玩過OI的人可能都聽說過，一笑而過就好。

1. 很多稱得上「拍案叫絕」的演算法都涉及到巧妙的模型/問題轉換，把看似毫不想乾的兩個領域聯繫起來。曾經有這麼一個OI題：你在製作一個遊戲，關卡設計員幫你設計了很多個（n個）關卡，每個關卡有各自的難度（1-m的整數）和精彩度（1-m的整數），假如最終的遊戲要求從中挑選若干個遊戲組成一個序列，每關的難度和精彩度都分別不小於上一關。如果n很大但m相對較小，最多可以做多少關？
================劇透====================
m較小是問題的突破口，另一個突破口是如果有兩關(ai, bi) == (aj, bj)，那麼兩關一定是要麼都選，要麼都不選想清楚這一點之後，準備一張m*m的表，其中x_ij表示難度為i，精彩度為j的關卡有多少個。然後呢？
就是那個經典的動態規劃問題了：從左上角走到右下角，路徑最大值是多少？

2. 對隨機化演算法的利用也是非常巧妙的，最經典的比如Miller-Rabin Test等。下面也是某個OI題：給出n*n矩陣A, B, C，判斷是否有A*B=C?
================劇透====================
直接採用矩陣乘法的話，即使是Strassen演算法也需要O(n^2.84)的時間，雖然還有更好的分治演算法但實現難度變得越來越大，而且常數也變得越來越大。
官方給出的答案是：隨機生成若干個n*1向量X，計算A(BX) = CX是否成立。注意到這樣的測試只需要O(n^2)的時間。只要任何一個X沒有通過測試，A*B就不等於C。否則，在大量測試之後，我們可以非常確信A*B=C的概率極高。

3. 我做過幾年圖形學和計算幾何，為了追求高效，通用和誤差低，有很多非常實用的小技巧，其中很多我認為已經超越了技巧的範疇，值得稱其為一個演算法。相信很多人都聽說過John Carmack的神奇的開平方演算法了，再舉一個：
圖形學一個基礎核心的問題是：如何判斷給定直線和給定多邊形相交。一個簡化版的問題是：給定平面上一個三角形ABC和平面上的一個點X，判斷X與ABC的關係（內部/外部/邊上/頂點？）
================劇透====================
注意到任何嘗試求解點與某條邊關係的演算法，都難以避免地會遇到大量除0，重合，平行等一系列特殊情況。應用最廣泛的演算法，說起來很簡單：計算三角形XAB, XBC, XCA的2倍有向面積，然後：
(1) 三個同號：X在其內部；
(2) 兩個同號，另一個異號：X在其外部；
(3) 一個為0，兩個不為0且同號：X在三角形邊上；
(4) 一個為0，兩個不為0且異號：X在三角形某條邊的延長線上；
(5) 兩個為0：X在三角形頂點上；
(6) 三個為0：三角形ABC是退化的。
如果更詳細的分析三個有相面積哪個為正哪個為負，還可以得到更多細節比如X在哪條邊上，在三條直線劃分的哪個區域里，等等。有向面積的計算方法是：
(x1, y1), (x2, y2), (x3, y3)圍成的三角形的2倍有向面積為x1y2+x2y3+x3y1-y1x2-y2x3-y3x1。
這個演算法的好處在於：除了最後一步給出結論，中間計算不需要任何if-else。只用乘法和加減法，儘可能減小了誤差。

思考題：用2和3中的思想，分別解決下列問題：給定平面上不自交的封閉多邊形（可能為凹）和平面上的一個點，判斷點是否在多邊形內。

4. 並查集的Union-Find演算法看起來並沒有什麼拍案叫絕的地方，無非是查找祖先的時候順便做一下路徑壓縮。可是這個大巧無工的小優化，極大地改善了演算法的均攤複雜度。
（大致介紹一下就是，如何設計一個數據結構，使其支持如下三種操作：插入一個包含單獨一個新元素的集合，將兩個元素所在的集合合併，以及查詢兩個元素是否在同一個集合中。該數據結構在Kruskal等一系列重要演算法中有應用。）
這個演算法真正拍案叫絕的地方在於複雜度分析，自1964年路徑壓縮發明之後十幾年之內竟然沒有人能準確的分析出每個操作的均攤複雜度。直到1973年才由Hopcroft和Ullman給出第一個有意義的複雜度：O(log*n)，其中log*的意思是：至少需要多少層log，才能使log(log(log(....log(n)...))) &< 0。這個證明已經很複雜了，有興趣的朋友可以參見https://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find

到了1975年，Tarjan證明了一個更好的複雜度上界：O(alpha(n))，其中alpha(n)是Ackermann函數的反函數。這個alpha(n)有多小呢？對於我們現在所能處理的數據規模，這個數不會超過4。我甚至大膽揣測，在我的有生之年，我們不需要這個數等於5的情形……

寫一個簡單，嚴格來說不算演算法的例子
初中數學老師最開始講到歐幾里得的幾何原本時提到的
因為覺得極度巧妙和簡單而終生難忘

問題就是，怎麼證明等腰三角形兩底角相等(不允許做輔助線)
----------------------------------------------------------------------------------

刷leetcode時碰到的，題目為Single Number | LeetCode OJ和Single Number III | LeetCode OJ。

這個題目是說，有一個n個元素的數組，除了一個元素只出現一次外，其他元素都出現兩次，讓你找出這個只出現一次的元素是幾，要求時間複雜度為O(n)且不再開闢新的內存空間。
——————————答案分割線—————————

解法是將所有元素做異或運算，即a[1] XOR a[2] XOR a[3] XOR…XOR a[n]，所得的結果就是那個只出現一次的數字，時間複雜度為O(n)。

當時看了答案後就一拍腦瓜，感嘆這個技巧真不錯。然而直到我遇見了這道題的進階版，當時真是恍然大悟拍案叫絕。

進階版:有一個n個元素的數組，除了兩個數只出現一次外，其餘元素都出現兩次，讓你找出這兩個只出現一次的數分別是幾，要求時間複雜度為O(n)且再開闢的內存空間固定(與n無關)。
——————————答案分割線————————

首先，仿照前面的演算法，把所有元素異或，得到的結果就是那兩個只出現一次的元素異或的結果。

然後，重點來了，因為這兩個只出現一次的元素一定是不相同的，所以這兩個元素的二進位形式肯定至少有某一位是不同的，即一個為0，另一個為1，找到這一位。

可以根據前面異或得到的數字找到這一位，怎麼找呢？稍加分析就可以知道，異或得到這個數字二進位形式中任意一個為1的位都是我們要找的那一位，找到這一位就可以了(這很容易)。

想了半天好像沒啥特別驚艷的，最近的一個覺得很好的應該是google的那個jump一致性hash演算法吧，利用了偽隨機數列的均勻性和同seed的一致性

今天突然想起小時候學演算法看到的一個段子，說有一個老太拿了一個漁網，跟程序員出了道題，說這個漁網縱橫交錯，看成一個地圖，從左下到右上最短路徑是什麼呢，程序員說用dijkstra，老太微微一笑，說兩手捏住起點終點拉伸，拉直的這條線就是了
現實中解決問題，有時候物理碾壓數學：）

說一個簡單並在生活中經常用到的，那就是經典的「二分法」。

有這麼一個例子，同學A的自行車鎖在宿舍樓下，第二天發現被盜了，無奈只能去學校保安科調出監控攝像頭，但是那一天的監控視頻有24個小時的時長，為了找到自行車被偷的那個時刻，同學A還真打算把長達24小時的視頻一分一秒的看下去。

這時候聰明的同學可能會想到快進了，間隔若干分鐘快進一次。但是，我對A說，你不知道二分法么，從整個視頻的中間第12h開始，如果那個時刻自行車不在了，那麼被偷的時刻在[0,12]區間內，如果自行車還在，那麼被偷的時刻在[12-24]區間內，接著再進行二分直到找到為止。比如，被偷的時刻在第15h，那麼二分查找次數是12-18-15，只需要少數次查找，便可以立刻最大限度地縮小查找範圍。平均時間複雜度為logn。

自從學了演算法之後，Leetcode見的多了，各種演算法接觸的多了，我的內心對於神奇演算法基本已經毫無波動。

講一個雖然幼稚，但是在小學時候，也曾經驚艷過我的演算法。題目：甲乙兩個人相向而行，相距L，出發同時甲的狗也出發在甲乙之間往返。已知甲，乙，狗速度分別為A，B，C且有 C&>A&>B。
求兩人相遇時狗跑過的距離。

在小時候我怎麼都做不出來，因為算出來 我列出了一個無數項求和的式子。在當時的我根本求不出來。

結果當我問了我爹後= =我爹直接就寫下了答案

===我是奧術（劃掉）奧數的分割線===
答案：
L/(A+B)*C。
演算法：
先求出甲乙相遇時間，再乘以狗的速度=。=

當時這個演算法震撼了我幼小的心靈，原來同樣問題換個演算法複雜度會下降這麼多！

===我是高數的分割線===

後來當接觸到收斂概念的時候。

第一反應就是：

媽的，小時候寫的那個無限級數是收斂的，其實能算出來!

有奧數童年的小伙們求贊~(≧▽≦)/~

雞兔同籠 抬腿法
26個腳8個頭，雞兔同籠
現在不排方程上軍訓教官：
1，2，3所有雞和兔子抬一條腿！
26-8=18條腿站著
1，2，3所有雞兔再抬一條腿！
18-8=10，雞全掉地上了，剩的腿都是兔子的，一共10/2 5隻，三隻雞5隻兔子
5×4+3×2 = 26腿，切題。

一道看起來很恐怖的題：如何對n個短整型數據進行排序，要求時間複雜度為O(n)，空間複雜度為O(1)。

～～～～～～～答案分界線～～～～～～～～

一個短整型表示範圍為-32768～+32767，設定一個數組int count[655356]並全初始化為0，則所需空間與n無關，為O(1)。掃描一遍待排序列A[n]，count[A[i]+32768]++ ；再掃描一遍count[],當count[i]&>0時，將count[i]個
(i-32768)輸入到A[n]中。總的時間複雜度為O(n)。

看了一個小演算法，被深深的震撼了，原來編程中被我們認為理所當然應該這樣做的東西，實際上還有很多優化的空間。
在一個文件中有很多行這樣的數據
134|32|35|2|43234|......|12"
"
25|5|286|16|58|......|614"
"
8731|8|98|22|4823|......|62"
"
......
......代表還有很多列，很多行，我的實驗里一共15列，600萬行
需求是求所有第二列數字的和，在這個例子里是32+5+8=45

1.最簡單的方法就是用C++中的getline讀一行數據，然後逐個字元判斷，如果是第二個』|『，就把第一個和第二個『|』中間的數字取出來就可以了，然後處理下一行。
這種方法時間是：0.8秒

2.第1種方法用getline，它幫我們讀取文件的時候，實際上是要逐個字元比較"
"的，才能取出來這一行，然後我們查找"|"的時候，又遍歷了一下這一行的其中一部分。實際上我們只要遍歷一次就可以了，於是可以用mmap函數把整個文件映射進內存，然後逐個字元判斷是"|"還是"
"來取得我們想要的結果。
這種方法時間是：0.65秒

//char *current = 文件初始位置, safeLimit是文件結尾（有些細節就先不處理了）
while (current&(current);
//單獨拿出來一個字元看，1000,0000，實際上是8個這樣的
constexpr uint64_t highBits=0x8080808080808080ull;
//0111,1111
constexpr uint64_t lowBits=~highBits;
//0000,1010，這個是"
"（Ascii碼）
constexpr uint64_t pattern=0x0A0A0A0A0A0A0A0Aull;
//這塊有點神奇，你自己用一個例子試一下
uint64_t lowChars=(~block)highBits;
uint64_t found0A=~((((blocklowBits)^pattern)+lowBits)highBits);
uint64_t match=found0AlowChars;
//如果match是1000,0000，就說明遇到"
"了
//如果這8個位元組里沒有"
"，直接進入下8個位元組
if (!match) {
current+=8;
continue;
}
//把match的位元組前後交換一下位置
match=__builtin_bswap64(match);
//找到了"
"，current直接移動到下一行
current+=(__builtin_clzll(match)/8);
}


說一個在某競賽書第一單元看到的，交換 A 和 B 的最簡單的做法：

scanf("%d %d",a,b);
printf("%d %d",b,a);


媽的好機智！

這個確實不能叫演算法，不過真的很拍案叫絕啊哈哈哈