# competition **Repository Path**: SentencesHuang/competition ## Basic Information - **Project Name**: competition - **Description**: C++ Competition Code - **Primary Language**: Unknown - **License**: MIT - **Default Branch**: main - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2022-09-01 - **Last Updated**: 2022-10-21 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README #+STARTUP: overview, indent #+OPTIONS: txt:t * TODO 一些記錄 ** Coding 計劃 - [ ] Note Info * 遞歸 #+BEGIN_SRC emacs-lisp ;; (message "Hello World!") (defun fact(n) (cond ((= 0 n) 1) (t (* (fact (- n 1)) n)))) (defun fib(n) (cond ((<= n 1) n) (t (+ (fib (- n 1)) (fib (- n 2)))))) ;; (fact 4) ;; (fib 3) #+END_SRC * 貪心 #+BEGIN_QUOTE 有 n 項工作，每項工作分別在 s_{i} 時間開始， 在 t_{i} 時間結束。對於每項工作，你都可以選擇參加與否。如果選擇了參加，那麽自始至終都必須全程參與。此外，參與工作的時間段不能重叠。（即使是開始的瞬間和結束的瞬間的重叠也是不允許的）。 #+END_QUOTE **在可選的工作中，每次都選取結束時間最早的工作** #+BEGIN_SRC cpp enum { MAX_N = 100000 }; int N, S[MAX_N], T[MAX_N]; std::pair itv[MAX_N]; { for (int i = 0; i < N; ++i) { itv[i].first = T[i]; itv[i].second = S[i]; } std::sort(itv, itv + N); int ans = 0, t = 0; for (int i = 0; i < N; ++i) { if (t < itv[i].second) { ++ans; t = itv[i].first; }} printf("%d\n", ans); } #+END_SRC ** 字典序最小問題 #+BEGIN_QUOTE 給定長度為 N 的字符串 S， 要構造一個長度為 N 的字符串 T。起初，T 是一個空串，隨後反復進行下列任意操作。 - 從 S 的頭部刪除一個字符，加到 T 的尾部。 - 從 S 的尾部刪除一個字符，加到 T 的尾部。 目的就是要構造字典序盡可能小的字符串 T。 #+END_QUOTE 從字典序的性質上看，無論 T 的末尾有多大，只要前面部分的較小就可以。所以我們可以試一下 貪心算法： __不斷取 S 的開頭和結尾中較小的一個字符放到 T 的末尾__ - 按照字典序比較 S 和將 S 反轉后的字符串 S'。 - 如果 S 較小， 就從 S 的開頭取出一個文字，追加到 T 的末尾。 - 如果 S' 較小， 就從 S' 的開頭取出一個文字，追加到 T 的末尾。 #+BEGIN_SRC cpp int N = 0; char S[MAX_N + 1]; void solve() { int a = 0, b = N - 1; while (a <= b) { bool left = false; for (int i = 0; a + i <= b; ++i) { if (S[a + i] < S[b - i]) { left = true; break; } else if (S[a + i] > S[b - i]) { left = false; break; } } if (left) putchar(S[a++]); else putchar(S[b--]); } putchar('\n'); } #+END_SRC ** Saruman's Army #+BEGIN_QUOTE 直綫上有 N 個點。點 i 的位置是 X_{i}。從這 N 個點中選取若干個，給它們加上標記。對每一個點，其距離為 R 以内的區域裏必須有帶有標記的點（自己本身帶有標記的點，可以認爲與其距離為 0 的地方有一個帶有標記的點）。在滿足這個條件的情況下，希望能為盡可能少的點i俺家標記。請問至少要有多少點被加上標記？ #+END_QUOTE 我們從最左邊開始考慮。對於這個點，到距其 R 以内的區域内必須要有帶有標記的點。（此點位於最左邊，所以顯然）帶有標記的這個點一定在此點右側（包含這個點自身）。 於是，究竟要給哪個點加上標記。答案應該是從最左邊的點開始，距離為 R 以内的最遠的點。因爲更左的區域沒有覆蓋的意義，所以應該京可能覆蓋更靠右的點。 加上了第一個標記后，剩下的部分也用同樣的辦法處理。對於添加了符號的點右側相距超過 R 的下一個點，采用同樣的方法找到其有側 R 距離以内最遠的點添加標記。在所有的點都被覆蓋之前不斷重複如下動作。 #+BEGIN_SRC cpp int N, R, X[MAX_N]; { std::sort(X, X + N); int i = 0, ans = 0; while ( i < N ) { int s = X[i++]; // s 是沒有被覆蓋的最左的點的位置 while (i < N && X[i] <= s + R) ++i; // 一直向右前進直到距 s 的距離大於 R 的點 int p = X[i - 1]; // p 是新加上標記的點的位置 while (i < N && X[i] <= p + R) ++i; // 一直向右前進直到距 p 的距離大於 R 的點 ++ans; } printf("%d\n", ans); } #+END_SRC ** Fence Repair #+BEGIN_QUOTE 農夫爲了修理柵欄，要將一塊很長的木板切割成 N 快。準備切成的木板的長度為 L_{1}、L_{2}、... 、L_{N}，未切割前木板的長度恰好為切割后模板長度的總和。每次切斷模板時，需要的開銷為這塊木板的長度。請求出按照目標要求將模板切割完最小的開銷是多少？ #+END_QUOTE 通過二叉樹的方式描述相關的切割。這裏樹中每個葉子節點就對應了切割出的一塊塊木板。葉子節點的深度就對應了爲了得到對應木板所需的切割次數，開銷的合計就是各葉子節點的 **木板的長度 * 節點的深度** 的總和。此時的最佳切割方法首先應該具有如下性質 最短的板與次短的板的節點應當是兄弟節點。 切割方式： (L1 + L2), L3, L4, ..., LN L: sort() #+BEGIN_SRC cpp int N, L[MAX_N]; { long long ans {0}; whlie (1 < N) { int mii1 = 0, mii2 = 1; if (L[mii1] > L[mii2]) std::swap(mii1, mii2); for (int i = 0; i < N; ++i) { if (L[i] < L[mii1]) { mii2 = mii1; mii1 = i; } else if (L[i] < L[mii2]) { mii2 = i; } } int t = L[mii1] + L[mii2]; ans += t; if (N - 1 == mii1) std::swap(mii1, mii2); L[mii1] = t; L[mii2] = L[N - 1]; --N; } printf("%lld\n", ans); } #+END_SRC * 動態規劃 ** 記憶化搜索和動態規劃 *** 01 背包問題 #+BEGIN_QUOTE 有 n 個重量和價值分別為 w_{i}，v_{i} 的物品。從這些物品中挑選出縂重量不超過 W 的物品，求所有挑選方案中價值總和的最大值 #+END_QUOTE rec(0, w) = max { rec(1, w), rec(1, W - w[0]) + v[i] } #+BEGIN_SRC cpp int n, W, w[MAX_N], v[MAX_N]; int rec(int i, int j) { int res; if (i == n) { res = 0; } else if (j < w[i]) { res = rec(i + 1, j); } else { res = std::max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]); } return res; } { printf("%d\n", rec(0, w)); } #+END_SRC #+BEGIN_SRC cpp int dp[MAX_N + 1][MAX_W + 1]; int rec(itn i, int j) { if (dp[i][j] >= 0 ) { return dp[i][j]; } int res; if (i == n) { res = 0; } else if (j < w[i]) { rec = rec(i + 1, j); } else { res = std::mac(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]); } return dp[i][j] = res; } #+END_SRC **我們仔細研究一下前面的算法利用到的記憶化數組。記 dp[i][j] 為根據 rec 的定義， 從第 i 個物品開始挑選總重小於 j 時， 總價值的最大值。於是有如下遞推式** $$dp[n][j] = 0$$ $$ dp[i][j] = \begin{cases} dp[i + 1][j] & (j < w[i]) \\ max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]) & (other) \end{cases} $$ **需要注意，因爲全局數組的内容會被初始化為 0，所以前面的源代碼中并沒有顯式地將初項 設置爲 0 進行複製，不過當一次運行要處理多組輸入數據時，必須要進行初始化。 #+BEGIN_SRC cpp int dp[MAX_N + 1][MAX_W + 1]; { for (int i = n - 1; i >= 0; --i) { for (int j = 0; j <= W; ++j) { if (j < w[i]) { dp[i][j] = dp[i + 1][j]; } else { dp[i][j] = std::max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]); } } } printf("%d\n", dp[0][W]); } #+END_SRC **** 窮竭搜索 這題的另外一個遞歸式子 #+BEGIN_SRC cpp int rec(int i, int j, int sum) { int res; if (i == n) { res = sum; } else if (j < w[i]) { res = rec (i + 1, j, sum); } else { res = max(rec(i + 1, j, sum), rec(i + 1, j - w[i], sum + v[i])); } return res; } #+END_SRC *** 最長公共子序列問題 #+BEGIN_QUOTE 給定兩個字符串 s_{i} (i = 1, 2, ..., n) 和 t_{i} (i = 1, 2, ..., n)。求出這兩個字符串最長的公共子序列的長度。字符串 s_{i} (i = 1, 2, ..., n) 的子序列指可以表示爲 S_{i_{j}} (j = 1, 2, ..., m; i_{j} < i_{j + 1}) 的序列 #+END_QUOTE $$ dp[i + 1][j + 1] =$$ $$ dp[i + 1][j + 1] = \begin{cases} max(dp[i][j] + 1, dp[i][j + 1], dp[i + 1][j]) & (s_{i + 1} = t_{j + 1}) \\ max(dp[i][j + 1], dp[i + 1][j]) & (other) \end{cases} $$ #+BEGIN_SRC cpp int n, m, dp[MAX_N + 1][MAX_M + 1]; char s[MAX_N], t[MAX_M]; { for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (s[i] == t[j]) { dp[i + 1][j + 1] = dp[i][j] + 1; } else { dp[i + 1][j + 1] = std::max(dp[i][j + 1], dp[i + 1][j]); } } } printf("%d\n", dp[n][m]); } #+END_SRC *** 完全背包問題 #+BEGIN_QUOTE 有 n 種重量和價值分別為 w_{i}, v_{i}的物品。從這些物品中挑選總重量不超過 W 的物品，求出挑選物品價值總和的最大值。在這裏，每種物品可以挑選任意多件。 #+END_QUOTE #+BEGIN_SRC cpp int dp[MAX_N + 1][MAX_W + 1]; { for (int i = 0; i < n; ++i) { for (int j = 0; j <= W; ++j) { for (int k = 0; k * w[i] <= j; ++j) { dp[i + 1][j] = std::max(dp[i + 1][j] , dp[i][j - k * w[i]] + k * v[i]); } } } printf("%d\n", dp[n][w]); } #+END_SRC * 關於一些筆記 ** Topic: 棧内存和堆内存 #+BEGIN_QUOTE 調用函數時，主調的函數所擁有的局部變量等信息需要存儲在特定的内存區域。這個區域被稱作棧内存區。另一方面利用`new`或者`malloc`進行分配的内存區域被稱爲堆内存。 #+END_QUOTE 棧内存在程序啓動時被統一分配，此後不能再擴大。由於這一區域有上限，所以函數的遞歸深度也有上限。雖然與函數中定義的局部變量的數目有關，不過一般情況下`C`和`C++`中進行上萬次的遞歸是可以的。 全局變量被保存在堆内存區。通常不推薦使用全局變量，但是在程序設計競賽中，由於函數通常不是那麽多，并且常常會有多個函數訪問同一個數組，因此利用全局變量就很方便。此外，有時必須要申請巨大的數組，與放置在棧内存上相比，將其放在堆内存上可以減少棧空間溢出的危險。 ** Topic: 貪心算法的證明 結束（以下問題）時間越早之後可選的工作也就越多。這是該算法能夠正確處理問題的一個直觀解釋。但是，這不能算是嚴格意義上的證明。可以通過下面的方法來證明 - 與其他選擇方案相比，該算法的選擇方案在選取了相同數量的更早開始的工作時，其最終結束時間不會比其他方案的更晚。 - 所以，不存在選取更多工作的選擇方案。 ** Topic: Huffman 編碼 ** 使用 memset 進行初始化 **雖然 memset 按照 1 字節為單位對内存進行填充， -1 的每一位二進制位都是1，所以可以像 0 一樣用 memset 進行初始化。 通過使用 memset 可以快速地對高維數組等進行初始化，到那時需要注意無法初始化成 1 之類的數值。 ** 各種各樣的DP