Yaoの程式小窩

【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++】競程筆記（對答案二分搜） 程式碼範例參考：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++ 解題筆記（前兩題） 此筆記僅供個人學習用途，內容僅供參考。 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++ 解題筆記（前兩題） 此筆記僅供個人學習用途，內容僅供參考。 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++ 解題筆記（前兩題） 此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=o711 題目說明： 該水杯可以被視為上下兩段直立長方體所組成： 下半段：底面積 $w1 \times w1$ ，高 $h1$ 。 上半段：底面積 $w2 \times w2$ ，高 $h2$ 。 倒水時： 水先填滿下半段，接著填上半段。 每次倒入的體積 $v$ ，轉換為水位高度上升量（根據在哪一段來決定用哪段的底面積去除體積，得到水位高度）。 解題思路： 先計算兩段的容量（下、上）。 記錄目前水位高度。 模擬每一次倒入： 判斷水還在下半段還是已經進入上半段。 根據當前段的底面積換算水位上升高度。 水滿之後不再上升。 記錄每次倒水所產生的「水位上升高度」，並取最大值輸出。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657...

【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++】競程筆記（一維掃描線） 程式碼範例參考：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-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() 等 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 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++】競程筆記（前綴和、差分 習題練習） 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++】競程筆記（前綴和、差分） 程式碼範例參考：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++】競程筆記（遞迴） 程式碼範例參考：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） 程式碼範例參考：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++ 解題筆記（前兩題） 本篇筆記紀錄個人解題過程，內容僅供參考。 等紅綠燈：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); ...