並查集 (Union Find, Disjoin Set… ) 傳送門 POJ1703 程式碼 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_STRL 2048 #define... Read more 24 May 2017 - 1 minute read
折半 + 二分搜尋 傳送門 POJ3977 解題想法 題目的 N 範圍 <= 35 ，若要窮舉全部情況，一定 TLE (種狀態) ， 觀察題目，其實可以切一半，折半分兩邊做，得到兩邊各自所有 subset 的總和，這樣就可以得到左右兩邊的解。之後再利用左右兩邊求得的 subset 總和，求出跨越兩邊的 subset 總和，得到跨越左右兩邊的解，這可以用排序 + 二分搜完成： 固定一個值，二分艘另外一邊與該值取負數最相近的值，兩者相加取絕對值，不斷更新最佳解，這樣複雜度大概到 也就是 就可以在時間限制內求解了。 程式碼 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26... Read more 19 May 2017 - 2 minute read
Rolling Hash 模板 想想我們是怎麼將字串轉成十進位數字，都是一樣的道理。 字串轉 Hash（基本款） 1 2 3 4 5 6 7 8 9 10 11 12 13 typedef unsigned long long int UT; char str[STRL], pat[STRL]; const UT hsaBase = 37, MOD1d7=1000000007; UT hsaPow, hsaS, hsaP; UT gethash(char *S, int len) { UT h=0; for(int i=0; i!=len; ++i ) { h = (h * hsaBase ) % MOD1d7; h = (h ... Read more 18 May 2017 - 2 minute read
Union Find 模板 用 par 紀錄樹上節點的 parent 是誰，用 rank 來優化樹高。 程式碼: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int par[MAXN], rank[MAXN]; void Initialize(){ int i=((N+1)<<1); while(i--){ par[i]=i; rank[i]=1; } } int Find(int foo){ return foo==par[foo]?foo:(par[foo]=Find(par[foo])); } char Same(int foo, i... Read more 18 May 2017 - less than 1 minute read
Flipping 傳送門 POJ3279 將題目消化一下 給一個 2D 陣列，裡面的元素有黑或白兩種顏色，如果在某一點將元素反轉（黑->白; 白->黑），那麼除了本身會反轉，上下左右相鄰的元素都會反轉。問使得所有元素都變成白色的最少操作次數且字典序最小的解。 若無解，輸出”IMPOSSIBLE”。 解題想法 因為反轉相同區間 偶數 次，都會轉回原先的狀態。[1] 並且反轉後的結果與選擇反轉位置的順序無關。（例如：照 1,2,3 順序翻和 2,1,3 順序翻是一樣的）。 所以我們可以由上到下、左到右做，先前拜訪的元素都會是翻成白色的。 令 i, j 分別代表元素在 i-th row, j-th column 。 一個簡單的策略，對於位置 i,j 的元素，如... Read more 12 May 2017 - 2 minute read