【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 ==...
【C++】競程筆記(前綴和、差分 習題練習)
【C++】競程筆記(前綴和、差分 習題練習) Zerojudge e346. 區間和練習:https://zerojudge.tw/ShowProblem?problemid=e346 :::info 內容: 給定一個長度為 $n$ 的整數序列 $A$ ,請回答 $q$ 筆詢問。每筆詢問會問其中一段連續區間的總和為何。 輸入說明: 輸入的第一行有一個整數 $n$ ( $1 \leq n \leq 200000$ ),代表 $A$ 序列的長度。 第二行有 $n$ 個整數以空白分隔,依序表示 $A$ 序列中的數字,其中數字的絕對值不會超過 $10^{9}$ 。 第三行有一個整數 $q$ ( $1 \leq q \leq 200000$ ),代表詢問的數量。 接下來有 $q$ 行,每行有兩個個數字 $l, r$ ,表示詢問為序列 $A$ 中第 $l$ 個數字到第 $r$ 個數字的總和。 輸出說明: 輸出 $q$ 行,每行有一個整數表示該次詢問的答案。 ::: 1234567891011121314151617181920212223242526#include <b...
【C++】競程筆記(前綴和、差分)
【C++】競程筆記(前綴和、差分) 程式碼範例參考:NTUCPC Guide,此筆記僅為個人學習用途。 前綴和(Prefix-sum) 要快速計算某區間的和,會用到前綴和。 Image Source:https://osgoodgunawan.medium.com/prefix-sum-80d531154b95 依照上圖,A 為原始序列,P 為前綴和序列,則前綴和用程式寫就是: 完整一點: 1234vector<int> P(n + 1, 0); // P[0] = 0for (int i = 0; i < n; ++i) { P[i + 1] = P[i] + A[i];} 我們可以利用前綴和計算區間 $[L, R]$ 的總和,可於 $O(1)$ 時間內完成,但在準備前綴和序列的時間複雜度是 $O(n)$ 。 12345678910111213141516171819202122#include <iostream>#include <vector>using namespace std;int main()...
【C++】競程筆記(遞迴)
【C++】競程筆記(遞迴) 程式碼範例參考:NTUCPC Guide,此筆記僅為個人學習用途。 遞迴(Recursion) 遞迴是函式的定義方式,這個函式透過呼叫自身來解決一個問題,並依賴於一個或多個終止條件來避免無限呼叫。 簡單來說,遞迴就是一個函式呼叫他自己本身,使得程式碼不斷地被執行,直到達成某個終止條件才會停止。 如: 123int func(int a){ func(a);} 設計遞迴程式有兩個重點: 設定終止條件:避免進入無窮遞迴。 遞迴規則:將原問題簡化並以相同邏輯遞迴呼叫自身。 應用 Fibonacci Number (Leetcode):https://leetcode.com/problems/fibonacci-number/ 123456789class Solution {public: int fib(int n) { if (n == 0 || n == 1){ return n; } return fib...
【C++】競程筆記(實作技巧:Range-based for loop、Structured binding)
【C++】競程筆記(實作技巧:Range-based for loop、Structured binding) 程式碼範例參考:NTUCPC Guide,此筆記僅為個人學習用途。 Range-based for loop 這個可以提供更簡潔的遍歷寫法,如下例子: 1234vector <int> v = {1,2,3,4,5,6,7,8,9};for (int i : v){ cout << i << endl;} 若要對 i 進行修改,需要加上 &,如:int& i。 字串陷阱 12345678910#include <bits/stdc++.h>using namespace std;int main(){ for (char c : "abc"){ cout << c << "*\n"; } return 0;} 輸出: 1234...
【APCS】2025年1月實作題 C++ 解題筆記(前兩題)
【APCS】2025年1月實作題 C++ 解題筆記(前兩題) 本篇筆記紀錄個人解題過程,內容僅供參考。 等紅綠燈:https://zerojudge.tw/ShowProblem?problemid=q181 tag : 資料處理 1234567891011121314151617181920#include <bits/stdc++.h>using namespace std;int main(){ int a, b; cin >> a >> b; int n; cin >> n; int sum; for (int i = 0; i < n; i++){ int wait_time = 0; cin >> wait_time; if (wait_time % (a+b) >= a){ sum += abs((wait_time % (a+b) - b) - a); ...




