Yaoの程式小窩

【C++】競程筆記（數學&程式設計） 程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 質數（prime numbers）與因數（factor） 因數定義：「 $y$ 是 $x$ 的因數代表 $x$ 除以 $y$ 為整數」。 在程式設計上則以 x % y == 0 表示。 123456// from NTUCPC Guidefor (int y = 1; y <= x; y++) { if (x % y == 0) { // y 是 x 的因數 }} 這樣 for 迴圈的遍歷方式，時間複雜度為 $O(x)$ ，因為有 x 個元素要判斷。 而在我們正常尋找因數的方法，如下： $12 = 1 \times 12 = 2 \times 6 = 3 \times 4 = 4 \times 3 = 6 \times 2 = 12 \times 1$ 可以發現，當因數 $>3$ 時，後面的因數與前面完全一致，我們到 $3$ 的時候就不會繼續找因數了。 為了要優化上面的代碼，所以可以透過這...

【C++】競程筆記（搜尋演算法、習題練習） 程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 線性搜尋法（linear search） 時間複雜度為 $O(N)$ ，就是用 for 迴圈遍歷得出的結果，如下： 1234567891011121314151617#include <iostream>#include <vector>using namespace std;int main(){ vector <int> a = {2,1,7,2,4,3,0,11,3,4,5,5,6,7,100,92,41,27,14}; for (int i=0;i<a.size();i++){ if (a[i] == 100){ cout << i; break; } } return 0;} 以上程式碼透過遍歷尋找 100 這個元素...

【C++】競程筆記（枚舉習題練習） https://zerojudge.tw/ShowProblem?problemid=c435 123456789101112131415161718192021222324#include <bits/stdc++.h>using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } int max_left = a[0]; int ans = INT_MIN; // INT_MIN 是 int 資料型態的最小值 -2^31 for (int j = 1; j < n; j++) { ans = ma...

【C++】競程筆記（枚舉） 程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 枚舉就是窮舉法，把所有東西都列出來。 字典序（Lexicographic order） 字典序，就是依照字典中出現的先後順序進行排序。 主要是用來比較和已排序序列（特別是字串）的規則，按照類似於字典中單字排列的方式進行運算。 字典序是一種排序方法，其核心思想是透過比較兩個序列的元素，從第一個元素開始，逐步向後，直到找到第一個不同的元素，然後根據這個元素的順序決定兩個序列的先後。 如果一個序列是另一個序列的前綴，則較短的序列排在前面。這種排序方式與我們在字典中查找單字的順序類似，因此被稱為「字典序」。 比較開頭字元 像是 “apple” 和 “banana”： 第一個字元：‘a’ vs ‘b’ ‘a’ 在字母表中排在 ‘b’ 之前，因此 “apple” < “banana”。 若前面字元都相同，則遍歷找兩字串中字元不同處去比較 像是 “apple” 和 “apricot”： 前兩個字元相同：‘a’ = ‘a’, ‘p’ = ‘p’ 第三個字元：‘p’ vs ‘r’ ‘p’...

【Python】競程相關模組、函數、方法等整理 - part 2 因為最近又要比賽了，所以趕緊做一篇整理複習一下，然後備註一下：這是個人筆記。 優化技巧 避免全域變數 就跟 C / C++ 的做法一樣，建立一個主函數。另外在 Python 中全域變數會害程式變慢。 格式： 12345def main(): print('Hello World')if __name__ == '__main__': main() 列表初始化（生成式與不用生成式） 12[None] * 100[None for _ in range(100)] 建議用 [None] * 100，速度較快。 二維陣列形式： 12# faster[[None] * N for _ in range(N)] for 迴圈遍歷優化 1234567# for i in range(len(A)) -> slowerfor i in range(len(A)): A[i]# for a in A -> fasterfor a in A: a 用下...

【個人筆記】C++ ZeroJudge 基礎題庫解題(純練習) - part 3 a020：https://zerojudge.tw/ShowProblem?problemid=a020 難度：★☆☆☆☆ 流程控制。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include <iostream>#include <string>using namespace std;int main() { // 映射表，索引0對應A（10），1對應B（11），依此類推 int mapping[26] = { 10, 11, 12, 13, 14, 15, 16, 17, 34, 18, ...

【Python】競程相關模組、函數、方法等整理 - part 1 因為最近又要比賽了，所以趕緊做一篇整理複習一下，然後備註一下：這是個人筆記。 IO優化 輸入優化 使用前引入模組：import sys 或 from sys import stdin，這樣方法就不用多打 sys。 12from sys import stdinline = stdin.readline() 若讀到 EOF 會回傳空字串。 建議搭配 strip() 函數使用： 12from sys import stdinline = stdin.readline().strip() stdin.readline()：每次讀取一行資料，直到 \n 為止。由於回傳的字串通常包含 \n，若不需要，用 strip() 去除。 stdin.readlines()：一次讀完 stdin，會回傳 list。 stdin.read()：讀取整個輸入流的所有資料，直到 EOF。適合一次性讀取大量資料。 以下使用迭代的方式處理 stdin 檔： 123from sys import stdinfor line in stdin:...

【Uva 題庫解題】C++ 個人解題筆記 - part1 https://zerojudge.tw/ShowProblem?problemid=a135 題目原文：https://cpe.mcu.edu.tw/cpe/problemPdf/12250.pdf 單字翻譯： prominent (adj.) 突出的；著名的；卓越的 figure (vt.) 表示 (在此題當作表示之意) European (adj.) 歐洲的；歐洲人的 (n.) 歐洲人 (此題當作形容詞用) equivalent (adj.) 相同的；相等的 (n.) 等於；等同 assume (v.) 假設；冒充、假裝；承擔、擔任 (此題為假設之意) uppercase (adj.) 大寫的 terminate (v.) 使終止；限定；終止、結束 quote (v.) 引用；放在引號內；估計 (n.) 引號 (此題當作引號之意) 2024/12/10 CPE 第一題。 123456789101112131415161718192021222324252627#include <iostream>...

【C++】競程筆記（algorithm 習題練習） 習題取自：NTUCPC Guide 此為個人解題過程，純粹紀錄。 https://tioj.ck.tp.edu.tw/problems/1287 一行測資輸入程式碼寫法： 12345for (int i=0;i<n;i++){ int x; cin >> x; num.push_back(x);} 宣告變數 x 放 for 裡面，然後讓 cin 去讀，在 push_back() 給 vector。 123456789101112131415161718192021222324252627282930313233#include <iostream>#include <vector>#include <algorithm>using namespace std;int main(){ int n; while (cin >> n){ vector <int> num...

【C++】競程筆記（algorithm標頭檔） 分析效率 123456789void bubble_sort(int arr[], int n) { // arr: 要排序的陣列，n: 陣列大小 for (int i = 0; i < n - 1; ++i) // n 次運算 for (int j = 0; j < n - i - 1; ++j) // (n - 1) + (n - 2) + ... + 1 = n * (n - 1) / 2 次運算 if (arr[j] > arr[j + 1]) { // n * (n - 1) / 2 次運算 int tmp = arr[j]; // 至多 n * (n - 1) / 2 次運算 arr[j] = arr[j + 1]; // 至多 n * (n - 1) / 2 次運算 ...

【C++】競程筆記（基礎題型） 程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 萬用標頭檔 #include <bits/stdc++.h> 有些OJ不給用要特別注意，能用就用，其他函式庫名稱還是要背一下。還有因為他抓的函式庫比較多的原因，所以執行會變得有點慢，但基本上不影響。 基本輸出輸入優化（提升速度用） ios::sync_with_stdio(false)（關閉與C同步的關鍵函式） cin.tie(nullptr)（關閉 flush 機制，若代碼有用到 endl，這條就沒屁用了，要注意） endl 建議用 \n 跳脫字元取代。 T 筆測資題型 12345int t;cin >> t;while (t--) { // do something} while() 迴圈，括號裡面如果是 0（false），就停止迴圈。以 t 遞減至 0，是比較聰明且簡潔的做法。 此題目會要求輸入 T 個測資，並使用迴圈執行 T 次讀取。 EOF 處理 1234int n;while (cin >> n) ...

【C++ 筆記】this pointer - part 21 很感謝你點進來這篇文章。 你好，我並不是什麼 C++、程式語言的專家，所以本文若有些錯誤麻煩請各位鞭大力一點，我極需各位的指正及指導！！本系列文章的性質主要以詼諧的口吻，一派輕鬆的態度自學程式語言，如果你喜歡，麻煩留言說聲文章讚讚吧！ this 指針（this pointer） 在 C++ OOP 中，每當呼叫非靜態成員函數時，編譯器會傳遞一種特殊的指標，稱為 “this” 指標。 它特殊的點就在於：它是隱形的。也就是說我們平常在設計 class 的時候，並不會看見 this pointer。 :::success this pointer 指向當前呼叫該函數的物件實例，讓程式可以在成員函數內部存取該物件的成員變數與其他成員函式。 ::: :::success 在 C++ 中，每個物件都能透過 this 指標來存取自己的位址。 ::: :::info Friend Function 沒有 this pointer，因為 Friend 不是類的成員，只有成員函數才有 this 指針。 ::: this pointer 是...

【C++ 筆記】內嵌函數（inline function） - part 20 很感謝你點進來這篇文章。 你好，我並不是什麼 C++、程式語言的專家，所以本文若有些錯誤麻煩請各位鞭大力一點，我極需各位的指正及指導！！本系列文章的性質主要以詼諧的口吻，一派輕鬆的態度自學程式語言，如果你喜歡，麻煩留言說聲文章讚讚吧！ 內嵌函數（inline function） 內嵌函數或稱內聯函數。 在 C++，內嵌函數（inline function）是一種特殊的函數。 此函數需要用關鍵字 inline 於欲使用之函數名前方，使 compiler 將函數呼叫替換為函數的本體代碼，而非如普通函數要透過函數呼叫機制（如：跳轉到函數地址並回傳）。 這種方式可減少函數呼叫的開銷（如：stack 的 push、pop 操作），從而提高程式執行效率。 :::info 以下擷取至菜鳥教程的原理解釋： C++ 內聯函數通常與類別一起使用。如果一個函數是內聯的，那麼在編譯時，編譯器會把函數的程式碼副本放置在每個呼叫該函數的地方。 對內聯函數進行任何修改，都需要重新編譯函數的所有客戶端，因為編譯器需要重新更換一...

【C++ 筆記】Friend Classes & Functions - part 19 很感謝你點進來這篇文章。 你好，我並不是什麼 C++、程式語言的專家，所以本文若有些錯誤麻煩請各位鞭大力一點，我極需各位的指正及指導！！本系列文章的性質主要以詼諧的口吻，一派輕鬆的態度自學程式語言，如果你喜歡，麻煩留言說聲文章讚讚吧！ Friend Class Friend Class 可以直接存取其他 class 的 private、protected 成員，只要當這個 class 被宣告為 friend。 因為 private、protected 成員不能直接存取，所以可以用 friend 的方式指定某 class 為好友 class，這在某些時候會變得很好用，如常見的 Data Structure：Linked-list。 宣告一個 friend class 格式如下： 1friend class class_name; // declared in the base class 以下是個範例： 12345678910111213141516171819202122232425...

【個人筆記】C++ ZeroJudge 基礎題庫解題(純練習) - part 2 a015.：https://zerojudge.tw/ShowProblem?problemid=a004 難度：★★★☆☆ 二維陣列、巢狀迴圈應用。 123456789101112131415161718192021222324#include <iostream>#include <vector>using namespace std;int main() { int rows, cols; while (cin >> rows >> cols) { vector<vector<int>> matrix(rows, vector<int>(cols)); for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { ...