Edoc Zec

本題為 Brute Force 可以迅速解題。 題目給予一些二維座標，求是否所有點左右對稱。 看似簡單，但需要注意以下幾點，不然很容易拖掉 Debug 時間。 1.   scanf 讀取輸入的時候，遇到自定義的 struct，不必遲疑，直接把 “&” 寫在前面：           scanf("%d %d", &a[i].x, &a[i].y); 2.   取 x 最大值和最小值，相加當作中點，不需要除以 2，避免出現浮點數問題。 3.   x_min 和 x_max 取完，要馬上回歸初始值。x_min 初始值要是很大的值，x_max 初始值是很小的值。 4.   要考慮座標有可能落在對稱線上，for 迴圈掃過所有點，某一點自己也可以跟自己取中點來做判斷。 完整程式碼： // This code is created by EdocZec on 2020/01/25 #include <bits/stdc++.h> #define _for(i,a,b) for(int i=(a); i<(b); ++i) // this has been verified and can work correctly. #define _dbg(arr,n) _for(i,0,n){cout << " [Debug] arr[" << i << "] = " << (arr)[i] << endl;} // this has been verified and can work correctly. using namespace std; struct point { int x; int y; }; point a[4000]; int main(int argc, char** argv) { int case_num; scanf("%d", &case_num); _for(i,0,case_num) ...

Kiddie Pool 問題簡化如下： n 個水龍頭 1...n，每個水龍頭出水速度 Ri，各自水溫為 Ci 。今要混合成溫度 X 且體積 V 的水，求最小時間？ 題目給的溫度公式，跟質心公式一樣。所以目標溫度 X，可以平移到數線 0 的位置。也就是每個水龍頭溫度都改為 X-Ci，目標改為配出溫度 0 度的水，方便計算。 考慮某個水龍頭開的時間最久，開啟時間為 t 秒，則得知其他的水龍頭最多也只能開啟 t 秒，不能再多。現在的目標為 t 需最小。 因此本題化簡為：假設最終答案就是 t 秒，每個水龍頭假設都先開啟 t 秒，各自裝入各自的水杯，然後計算有哪些水杯內的水是多餘的，需要倒掉。倒掉後的每杯水體積總和要逼近目標的體積 V，總和超過或小於 V，就要調整 t 的大小，直到體積總和等於 V 為止。 解上述第 3 點的問題，可以想像成有一蹺蹺板，上面放著 n 杯水。每杯水重量為 Ri × t。每杯水跟支點距離 abs(X-Ci)。為了維持平衡，必須將多餘的水從某幾杯中倒出，微調到蹺蹺板平衡時，所有水杯總重量總和需逼近 V。 利用貪婪演算法，從靠近支點處往遠離支點處走訪每個水杯，並累計力矩的值，左右兩邊一定會至少有一邊走訪到盡頭，此時若有一邊的力矩比較多，將力矩多的那邊當前走訪到的水杯，透過倒掉水的方式使左右平衡。 調整到支點左右力矩相等時，檢查水的體積總和是否符合要求，如果總體積太小，就拉高 t 值，否則降低 t 值。t 值的逼近，用 Binary Search 逼近法。 本題要十分注意的地方是 IMPOSSIBLE 的判斷。如果蹺蹺板支點沒有任何物品，且支點左邊全空或右邊全空，就是 IMPOSSIBLE 的情況。如果支點有物品，或者支點左右都有物品，此時 t 已經快要趨近極大，就代表 IMPOSSIBLE。 核心程式碼如下： 其中 left/right 代表支點左右的力矩，v_max 為當前 t 值下，力矩平衡的最大體積，center 是用來判斷支點有沒有物品。binary search 的 iteration 共 1000 次。 // binary search double low = 0, high = 1e20; for(int it = 0; it < 1000;...

原題目簡述如下： 以 m x n 大小的 grid 代表一張地圖，現今要在此地圖內探勘，找出油田。某一區塊如果標示 "@" 代表有油，"*" 代表沒有油。 "@" 相鄰的區域的聯集，可視為一個油田。（所謂相鄰，除了上下左右，斜向的相鄰也算進去） 求任意地圖中，油田的個數。 例如輸入的測資為： *    *   *    *  @ *   @  @  *  @ *   @   *   *  @ @ @  @   * @ @ @   *   *  @ 則油田個數為 2。 想法 採用典型的倒水演算法（Flood Fill），走訪 "@" 出現的區域，從此往下倒水，倒過水的區域標上 id，因此透過 id 的編號，可以得知油田的個數。 實作 先實作倒水演算法的子函式： void floodfill(vector<vector<char> >& map,                vector<vector<int>  >& id_table,                int row, int col, int id) {    if(row < 0 || (row >= map.size()) )   return;    if(col < 0 || (col >= map[0].size())) return;    if(map[row][col] != '@' || id_table[row][col] > 0) return;    id_table[row][col] = id;   ...

最近對線性代數應用感興趣，開始研究線性代數運算的底層程式實作。 先從矩陣乘積開始。 在此用 C++ 做矩陣與向量的乘積。 我們定義以下的矩陣 Class： template <class T, size_t, size_t j> class mtx { public: mtx(){} ~mtx(){} inline T& operator()(size_t i, size_t j) { return arr_[i][j]; } void info() { cout << endl; for(size_t i = 0; i < ROWS; i++) { for(size_t j = 0; j < COLS; j++) cout << " " << arr_[i][j]; cout << endl; } cout << endl; } private: T arr_[ROWS][COLS]; }; 接著我們就可以使用此 Class 來做矩陣與向量乘積： mtx a; mtx x; mtx b; a(0, 0) = 2; a(0, 1) = 1; a(1, 0) = 3; a(1, 1) = 5; a(2, 0) = 4; a(2, 1) = 7; x(0, 0) = 10; x(1, 0) = 12; // matrix mul: for(size_t r = 0; r < 3; r++) b(r, 0) = 0; for(size_t i = 0; i < 3; i+...