Dijkstra 模板 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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 #pragma GCC target ("avx") #pragma GCC optimize (... Read more 12 Jul 2017 - 2 minute read
梯度下降法 解法 使用梯度下降法。 先定義目標函式：給一平面上座標，輸出該座標與平面上最遠點的距離平方。 我們的任務是將其最小化。 梯度下降： 先隨便選一點，作為起點，向 +x, +y 方向分別跨一小步， 再評估向 +x, +y 移動的目標函式，是否有進步？有則將起點往正向更新位置，否則往反向更新位置。 簡單來說，就是利用 x, y 方向的偏微分，往負的梯度方向前進，就能夠帶我們前往更深的地方（使得目標函式的輸出最小化）。 也就是說， 將 x, y 往 f(x,y) 較低的位置更新。 另外兩種解法有隨機增量、三分搜，會陸續在以後更新。 傳送門 HDU3007 梯度下降法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1... Read more 11 Jul 2017 - 5 minute read
基礎幾何模板 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 67 68 69 70 71 72 73 74 #include <cmath> #include <complex> #include <valarray> #include <functional> // not seperate *.h and... Read more 11 Jul 2017 - 2 minute read
線段樹模板 支援區間查詢、修改。 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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 #include... Read more 11 Jul 2017 - 2 minute read
Max flow 模板 Dinic’s algorithm 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 struct NODE { NODE(int to, int cap, int rev) : to(to), cap(cap), rev(rev) {} int to, cap, rev; }; typedef vector< NODE... Read more 11 Jul 2017 - 1 minute read