Yaoの程式小窩

【C++】競程筆記（對答案二分搜） 程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 例題：https://zerojudge.tw/ShowProblem?problemid=h084 暴力解：直接窮舉所有可能高度的 x，並且看海報寬度，遍歷木板高度選可以貼的地方，但是這樣時間複雜度會是 O(n2)O(n^2)O(n2) ，木板高度可能高達 10910^9109 。 具體程式碼寫法： 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(); i...

【APCS】2024年1月實作題 C++ 解題筆記（前兩題） 此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=m931 題目說明： 有 nnn 個角色，分別都有攻擊力（ aia_iai​ ）跟防禦力（ did_idi​ ）。 能力值 = ai2+di2a_{i}^{2} + d_{i}^{2}ai2​+di2​ 。 輸出第二大的能力值的角色的攻擊力跟防禦力。 解題思路： 建立三個 vector：a, d, state，分別存每個角色的攻擊力、防禦力、能力值。 由於要求第二大，再加上預設排序函式都是升序，要降序就用反向迭代器 rbegin() 跟 rend()。 因為測資沒很大，直接遍歷找 (a[i]*a[i] + d[i]*d[i]) == state[1]。 cout 並 break，後面再找就沒意思。 1234567891011121314151617181920212223242526272829303132#include <iostream>#include <ve...

【APCS】2024年6月實作題 C++ 解題筆記（前兩題） 此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=o076 題目說明： nnn 棟高樓，樓高為 hnh_nhn​ ，會從某棟高樓上向右滑翔，要找到一組遞減序列，使序列長度達最長。 解題思路： 開一個 vector h，並多一個元素，做邊界檢查。 令這個邊界是 h 的上限最大值+1（題目的 h 是 1≤h≤10001 \leq h \leq 10001≤h≤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 nam...

【APCS】2024年10月實作題 C++ 解題筆記（前兩題） 此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=o711 題目說明： 該水杯可以被視為上下兩段直立長方體所組成： 下半段：底面積 w1×w1w1 \times w1w1×w1 ，高 h1h1h1 。 上半段：底面積 w2×w2w2 \times w2w2×w2 ，高 h2h2h2 。 倒水時： 水先填滿下半段，接著填上半段。 每次倒入的體積 vvv ，轉換為水位高度上升量（根據在哪一段來決定用哪段的底面積去除體積，得到水位高度）。 解題思路： 先計算兩段的容量（下、上）。 記錄目前水位高度。 模擬每一次倒入： 判斷水還在下半段還是已經進入上半段。 根據當前段的底面積換算水位上升高度。 水滿之後不再上升。 記錄每次倒水所產生的「水位上升高度」，並取最大值輸出。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464...

【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) { c...

【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，意為來源。 str...

【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() 的執行效率遠高於前者，因為在底層進行實作，接近硬體層面。 其基本語法如下： p...

【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 內容： 給定一個長度為 nnn 的整數序列 AAA ，請回答 qqq 筆詢問。每筆詢問會問其中一段連續區間的總和為何。 輸入說明： 輸入的第一行有一個整數 nnn ( 1≤n≤2000001 \leq n \leq 2000001≤n≤200000 )，代表 AAA 序列的長度。 第二行有 nnn 個整數以空白分隔，依序表示 AAA 序列中的數字，其中數字的絕對值不會超過 10910^{9}109 。 第三行有一個整數 qqq ( 1≤q≤2000001 \leq q \leq 2000001≤q≤200000 )，代表詢問的數量。 接下來有 qqq 行，每行有兩個個數字 l,rl, rl,r ，表示詢問為序列 AAA 中第 lll 個數字到第 rrr 個數字的總和。 輸出說明： 輸出 qqq 行，每行有一個整數表示該次詢問的答案。 ::: 123456789101...

【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][L, R][L,R] 的總和，可於 O(1)O(1)O(1) 時間內完成，但在準備前綴和序列的時間複雜度是 O(n)O(n)O(n) 。 12345678910111213141516171819202122#include <iostream>#include <vector>using na...

【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 ...

【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;} 輸出： 1...

【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); ...

PixAI 一個免費的二次元 AI 生圖網站，使用教學與模型推薦 哈囉大家好我是 LukeTseng，今天來介紹一個免費的生圖網站叫 PixAI，他的命名神似知名的插畫交流網站 Pixiv（眾多老濕機們的平台，讚讚der），也當然，他在二次元生圖的部分十分優秀，接下來就讓我帶各位來看這個網站。 為什麼要用 PixAI？ AI 生圖雲端運算，不用本地端執行生圖程式 免費 功能齊全且細項多雜 能產二次元香圖，讚讚 PixAI 註冊 先前往：https://pixai.art/zh 這個網站現在支援中文了，之前是不支援的，如果你的介面仍顯示英文的話，可如下圖進行操作。 找到以下紅框處的圖標，就可以更改語言： 若要進行登入或註冊就按下登入： 這邊提供了多種的登入方式，若是第一次進這網站沒有註冊的話，就按下面的「使用者註冊」： 註冊完後，會跳出以下訊息告知你領取每日積分： 每日登入會拿到 10000 積分，若積分沒有使用完畢的話，會自動累積至先前獲得的點數，不用擔心會被吃掉。 另外 PixAI 也有提供手機 App，針對安卓及蘋果平台都有支援： Google Play（A...