【C++】競程筆記（資料結構：Binary Tree）
【C++】競程筆記（資料結構：Binary Tree） 程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 簡介 樹（Tree）在電腦科學領域是一個由「節點」（Node）和「邊」所組成的圖形，如圖： Image Source：https://www.geeksforgeeks.org/dsa/binary-tree-data-structure/ 基本術語 節點（Node）： 如 1、2、3、4 等這些數字被圓圈包起來的就是一個節點。 根節點（Root）： 指的是最上層的節點，沒有父節點，如 1 就是根節點 Root。 子節點（Child）： 位於某節點之下的直接後繼節點，如 1 底下的 2 跟 3 都是 1 的子節點；2 底下的 4 跟 5 都是 2 的子節點。 父節點（Parent）： 反之，父節點為子節點的上層節點。1 是 2 跟 3 的父節點，2 是 4 跟 5 的父節點。 葉節點（Leaf）： 沒有任何子節點的節點。如 8, 5, 9, 10 都沒有子節點，所以稱為葉節點。 深度（Depth）： 根節點的深度定義為 0...
【C++ 筆記】基礎排序（氣泡、選擇、插入排序法）
【C++ 筆記】基礎排序（氣泡、選擇、插入排序法） 本筆記僅供個人學習用途，內容斟酌參考。 1.Bubble Sort 原理：兩兩相鄰比較，大的往後推，重複進行多輪直到完成排序。 1234567891011void bubbleSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; ++i) { // 內層進行兩兩相鄰元素比較與交換 for (int j = 0; j < n - 1 - i; ++j) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } }} 時間複雜度： 最佳情況： $O(n)$ （若資料已排序，可加入 flag 判斷是否有交換，避免多餘比較） 平均情況： $...
【APCS】2023年1月實作題 C++ 解題筆記（前兩題）
【APCS】2023年1月實作題 C++ 解題筆記（前兩題） 此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=j605 題目說明： 有 $K$ 個提交紀錄，第 $i$ 個提交紀錄有兩整數 $t_i, s_i$ ，分別為上傳時間跟提交分數，若第 $i$ 次的提交結果為嚴重錯誤，則 $s_i = -1$ 。 計算總分公式：提交紀錄最高分 $-$ 總提交次數 $-$ 總嚴重次數 $\times 2$。 若總分算出來 $< 0$ ，則計為 $0$ 。 輸出一行，總分和第一次最高分的時間點。 解題思路： 宣告兩變數 ans, sum_s，分別用來計算總分跟總嚴重錯誤次數 輸入的時候就可以先判斷是否有 s[i] == -1 的情形。 max_element(s.begin(), s.end()); 計算值最大的元素，但記得這回傳結果會是迭代器，要加上 * 解參考運算子（Dereference）。 用 find(s.begin(), s.end(), max_score); 跟 distance 去算第...
【APCS】2023年6月實作題 C++ 解題筆記（前兩題）
【APCS】2023年6月實作題 C++ 解題筆記（前兩題） 此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=k731 題目說明： 給定一個如數學座標一樣的二維平面（y 正為北, x 正為東），起始位置於 $(0, 0)$ 。輸入給 $n$ 個座標，必須按照這些點的順序移動，題目保證只會垂直或水平方向移動，不會斜向移動。且第一個點保證一定是 x 軸正的位置(初始方向向右)。 請輸出這條路徑中，左轉、右轉、迴轉的個數分別為多少。 解題思路： 定義方向： 0：東。 1：北。 2：西。 3：南。 計算方向： 根據相鄰兩點的座標變化，去判斷移動方向。如：若 x 不變，y 增加，則方向為北（1）；若 x 增加，y 不變，則方向為東（0）。 判斷轉向： 每點 $p_i$ （ $i$ 從 $1$ 到 $n-1$ ），分別計算兩個方向： 進入方向 d1：從 $P_{i-1}$ 到 $P_i$ 。 離開方向 d2：從 $Pi$ 到 $P_{i+1}$ 。 判斷 d1, d2 變化量 dir： ...
怎麼背 ASCII Code？（APCS 觀念題）
怎麼背 ASCII Code？（APCS 觀念題） 以下是一個 ASCII Code 表。 圖片來源：https://shihyu.github.io/books/apas01.html ASCII 碼的取值範圍為 0 ~ 127，可用 7 個 bit 來表示一個字元。 那這東西怎麼背呢？其實只要找「開頭」就好，因為你也知道後面都是連續的，稍微數一下就可以推算出來。 比如十進位數字，只要找 0 的 ASCII Code = 48 即可，要找 7 的 ASCII code 的話就是 48 + 7 = 55。 接下來是英文字母，要記得他還分大小寫，同樣的，只要找開頭 A 跟 a 的 ASCII code 即可，如： A 的 ASCII code = 65。 a 的 ASCII code = 97。 那之後的英文字母，我相信大部分人應該都有背過 a-z 吧，之後數看在開頭的第幾位就可以了。 另外可以發現大小寫之間的 ascii code 的差值是 32，所以你只要記住大寫或小寫全部的 ascii code，即可用 32 去推算大小寫。 如：我知道 C 的 ASCII code 是...
【APCS】2023年10月實作題 C++ 解題筆記（第一題）
【APCS】2023年10月實作題 C++ 解題筆記（第一題） 此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=m370 題目說明： n 個位置上有食物，有一隻老鼠剛開始位於位置 x，覓食時只能往左或往右一個方向，試問找出最大能吃多少食物，並且最後一次吃食物停下的位置。 解題思路： 建立 vector <int> f(n + 1)，並把 x 丟進去 f 裡面，順序不重要，丟進去就好。 輸入完所有的 f 後，再進行排序。 使用 auto it = find(f.begin(), f.end(), x); 找出 x 的索引值。 計算從 x 到最小索引值跟最大索引值的距離，取 max() 得出最多能吃多少食物。 最後透過 f[0] 跟 f.back() 分別取得最後的位置。 範例程式碼： 1234567891011121314151617181920212223242526#include <bits/stdc++.h>using namespace std;int main(...
【C++】競程筆記（對答案二分搜）
【C++】競程筆記（對答案二分搜） 程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 例題：https://zerojudge.tw/ShowProblem?problemid=h084 暴力解：直接窮舉所有可能高度的 x，並且看海報寬度，遍歷木板高度選可以貼的地方，但是這樣時間複雜度會是 $O(n^2)$ ，木板高度可能高達 $10^9$ 。 具體程式碼寫法： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657// 暴力破解法.cpp#include <bits/stdc++.h>using namespace std;bool canPlacePosters(const vector<int>& h, const vector<int>& w, int x) { int n = h.size(); int k = w.size...
【APCS】2024年1月實作題 C++ 解題筆記（前兩題）
【APCS】2024年1月實作題 C++ 解題筆記（前兩題） 此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=m931 題目說明： 有 $n$ 個角色，分別都有攻擊力（ $a_i$ ）跟防禦力（ $d_i$ ）。 能力值 = $a_{i}^{2} + d_{i}^{2}$ 。 輸出第二大的能力值的角色的攻擊力跟防禦力。 解題思路： 建立三個 vector：a, d, state，分別存每個角色的攻擊力、防禦力、能力值。 由於要求第二大，再加上預設排序函式都是升序，要降序就用反向迭代器 rbegin() 跟 rend()。 因為測資沒很大，直接遍歷找 (a[i]*a[i] + d[i]*d[i]) == state[1]。 cout 並 break，後面再找就沒意思。 1234567891011121314151617181920212223242526272829303132#include <iostream>#include <vector>#include <...
【APCS】2024年6月實作題 C++ 解題筆記（前兩題）
【APCS】2024年6月實作題 C++ 解題筆記（前兩題） 此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=o076 題目說明： $n$ 棟高樓，樓高為 $h_n$ ，會從某棟高樓上向右滑翔，要找到一組遞減序列，使序列長度達最長。 解題思路： 開一個 vector h，並多一個元素，做邊界檢查。 令這個邊界是 h 的上限最大值+1（題目的 h 是 $1 \leq h \leq 1000$ ），所以 h[n] = 1001。 設兩個變數 maxLen 紀錄序列最大長度，len 紀錄目前長度。 迴圈+判斷 h[i] > h[i+1]，達成條件就 len++，否則更新最大長度 maxLen = max(maxLen, len + 1)，並重置 len = 0。 1234567891011121314151617181920212223242526#include <iostream>#include <vector>using namespace std;int mai...
【APCS】2024年10月實作題 C++ 解題筆記（前兩題）
【APCS】2024年10月實作題 C++ 解題筆記（前兩題） 此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=o711 題目說明： 該水杯可以被視為上下兩段直立長方體所組成： 下半段：底面積 $w1 \times w1$ ，高 $h1$ 。 上半段：底面積 $w2 \times w2$ ，高 $h2$ 。 倒水時： 水先填滿下半段，接著填上半段。 每次倒入的體積 $v$ ，轉換為水位高度上升量（根據在哪一段來決定用哪段的底面積去除體積，得到水位高度）。 解題思路： 先計算兩段的容量（下、上）。 記錄目前水位高度。 模擬每一次倒入： 判斷水還在下半段還是已經進入上半段。 根據當前段的底面積換算水位上升高度。 水滿之後不再上升。 記錄每次倒水所產生的「水位上升高度」，並取最大值輸出。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657...
【C++】競程筆記（雙指標）
【C++】競程筆記（雙指標） 程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 雙指標（Two-Pointer） 雙指標是一種常用於陣列或字串處理的技巧。 顧名思義，雙指標是指同時使用兩個指標（指向資料結構的索引）來遍歷或操作資料。 這種技巧可以減少時間複雜度，能避免掉多重迴圈，常被用在排序陣列或雙向搜尋的情況上。 常見的指標移動方式有： 一個從頭開始、另一個從尾開始（雙向靠攏） 一個快指標、另一個慢指標（追趕法） 同時向同一方向移動但控制條件不同 有一個更快理解什麼是雙指標的例子： 假設有個已經排序好的序列：arr = [1, 3, 4, 5, 7, 10, 11]。 我們希望能找出兩個數的和是 14。 則雙指標的初始狀態：left → 1 3 4 5 7 10 11 ← right 首先走第一遍初始狀態：arr[left] + arr[right] = 12，值太小，需要移動左邊的指標，叫他往右，讓值變大一點。 所以第二遍：arr[left+1] + arr[right] = 14，剛好就找到 14 了。 ...
【C++】競程筆記（一維掃描線）
【C++】競程筆記（一維掃描線） 程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 數線問題 例題（APCS 2016 年 3 月第三題）：https://zerojudge.tw/ShowProblem?problemid=b966 測資加強版：https://zerojudge.tw/ShowProblem?problemid=f855 12345678910111213141516171819202122232425262728293031323334353637#include <bits/stdc++.h>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<pair<int, int>> seg(N); for (int i = 0; i < N; ++i) { cin...
【C++ 筆記】C++ 與 C style string
【C++ 筆記】C++ 與 C style string C-style string 先從老祖宗 C 語言講起好了。 C-style string 就是字元陣列所組成的，最後結尾用 null（\0）表示字串結束。 如： 1char a[] = "Hello"; // 等於 char a[] = {'H', 'e', 'l', 'l', 'o', '\0'}; 這種字元陣列需要搭配 <cstring> 標頭檔引入 C 語言版本的字串函式庫。 裡面常見的操作如下： 函式名 功能 strlen(s) 回傳字串長度（不含 \0） strcpy(dst, src) 字串複製 strcmp(s1, s2) 字串比較（回傳 0 相同，非 0 不同） strcat(dst, src) 字串串接 dst 就是 destination，意為目的地；src 就是 source，意為來源。 strcp...
【C++筆記】一些輸入函數 cin, getline(), cin.get() 等
【C++筆記】一些輸入函數 cin, getline(), cin.get() 等 cin 這大家都知道，這是 C++ 的標準輸入物件，屬於 istream 類別。 基本語法不外乎就是透過鍵盤輸入將資料存入某個變數。 12int a;cin >> a; 那其特性如下： 以空白（空格、Tab 縮排、換行）為分隔符號。 自動忽略前導空白字元（如輸入：1 2 3 4 5，每個數字間的空格都會忽略，並依序存入變數） 無法讀取含有空白字元的字串，如下範例： 1234string name;cin >> name;// 輸入 John Doe// name 只會得到 "John" 這是 cin 的缺點，要讀入完整的字串，則需要 getline()。 printf() / scanf() 雖然本文講輸入函數，但想說既然 C 有的東西，C++ 當然也繼承下去，就順便講一講 printf()。 相對於 cin / cout 來說，printf() / scanf() 的執行效率遠高於前者，因為在底層進行實作，接近硬體層面。 其基本語法如下： prin...
【Uva 題庫解題】C++ 個人解題筆記 - part2
【Uva 題庫解題】C++ 個人解題筆記 - part2 11461 SquareNumbers：https://cpe.mcu.edu.tw/cpe/problemPdf/11461.pdf 2025/03/25 CPE 第一題。 Zerojudge 翻譯版：https://zerojudge.tw/ShowProblem?problemid=d186 單字： inclusive (adj.)：（價格或數量）包括一切的、包括首尾兩天（或兩個數字）的、（團體或組織）可以包容各種人的。 denote (v.)：表示，代表。 1234567891011121314151617181920212223#include <bits/stdc++.h>using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int a, b; while (cin >> a >> b){ if (a ==...
