Yaoの程式小窩

【C++】競程筆記（背包問題） 題目範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 最後更新時間： 什麼是背包問題 背包問題（Knapsack Problem）是一種組合最佳化的 NP-Complete 問題，有著多種變形，其中最基礎的是「0/1 背包問題」。 在 DP 裡面，背包問題是最經典且常見的題型之一。 01 背包問題 Problem Source：https://oj.ntucpc.org/problems/801 所謂 0 1 就是物品可拿或不拿。 題目敘述： 有 $N$ 個物品編號 $1 \sim N$ ，第 $i$ 個物品的重量和價值分別是 $w_i$ 和 $v_i$ 。學姐打算從這 $N$ 個物品選其中一些帶走，但她只有大小為 $W$ 的背包，也就是說她選擇的物品總重不能超過 $W$ 。請問背包能容納的物品的總價值最大是多少？ 如果直接定義 $dp[i]$ 是前 $i$ 個物品的最大總價值，是不實際的，因為還要考慮到 $W$ 重量的因素。 因此用到二維 DP 觀念：$dp[i][j]$ 為前 $i$ 個物品且背包當前容量限制為 $j$ 時，能獲得...

【考試向】資料結構筆記（鏈結串列） 歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～ 最後更新日期： 單向鏈結串列（Singly Linked list） 一般的陣列會在連續的記憶體空間中儲存資料。 鏈結串列可將資料儲存在不連續（non-contiguous）的記憶體空間中。 連續的壞處： 在中間插入需要將後面的元素各移動一格。 做刪除操作也要將後面元素往前補上去。 而在鏈結串列只需要改變指標指向就可以做到插入、刪除的操作。 在存取元素方面，陣列只需 $O(1)$ ，因為有 index，而鏈結串列需要 $O(n)$ ，因為要從頭一個一個找。 陣列 v.s. 鏈結串列 陣列（Array） 鏈結串列（Linked-list） 記憶體空間 連續 不連續 大小 固定 動態 插入/刪除操作 慢（要移動後面的所有資料） 快（只需改變指標指向） 讀取資料 $O(1)$ $O(n)$ 組成的基本要素 鏈結串列由數個節點（node）組成，一個節點又由...

【考試向】資料結構筆記（堆疊、佇列、環狀佇列、後序表示式） 歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～ 最後更新時間： 堆疊（Stack） 特性：後進先出（LIFO：Last In First Out） 資料只能在頂端（Top）做堆入（Push），跟移除（Pop）。 Image Source：Stack Data Structure and Implementation in Python, Java and C/C++ 應用： Ctrl + Z 復原功能 函式呼叫 括號匹配 DFS（Depth First Search：深度優先搜尋） 時間複雜度： 堆入（Push）： $O(1)$ 移除（Pop）： $O(1)$ 優點： 記憶體管理高效：資料只在頂端操作，記憶體配置連續可預測。在系統層級（如 Call Stack），比堆積（Heap）快很多。 存取速度快（$O(1)$）：無論堆疊有多大，Push 跟 Pop 的時間複雜度永遠是 $O(1)$ 。 防資...

【C++】競程筆記（多維 DP、LCS 最長共同子序列 習題練習） 練習題目參考自：NTUCPC Guide，此筆記僅為個人學習用途。 823 . RGB Problem Source：https://oj.ntucpc.org/problems/823 先定義三種顏色的代號以及對分數的貢獻（權重）： 紅色（$j=0$）：權重為 $-v_i$（題目要求扣掉紅色數字總和）。 綠色（$j=1$）：權重為 $+v_i$（題目要求加上綠色數字總和）。 藍色（$j=2$）：權重為 $0$（藍色不影響分數）。 最後再來定義狀態：定義 $dp[i][j]$ 為考慮到第 $i$ 個數字，且將第 $i$ 個數字塗上顏色 $j$ 時，目前所能獲得的最大價值。 $i : 1 \le i \le N$ $j : 0 \le j \le 2$ （分別代表紅、綠、藍） 求 DP 轉移式： 題目限制「相鄰的數字必須標上不同的顏色」，要計算第 $i$ 個數字塗某個顏色時，第 $i-1$ 個數字必須是另外兩種顏色之一，最終解答是從中選取較大者，再加上當前顏色的權重。 對第 $i$ 個數字 ($i >...

【C++】競程筆記（多維 DP、LCS 最長共同子序列） 題目範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 什麼是多維的 DP? 一開始入門 DP 所寫的全都是一維的 DP，例如在爬樓梯問題， $dp[i]$ 就表示成到達第 $i$ 階的方法數。 而當中只有一個變數，叫做 $i$ ，故稱為一維 DP。 多維的 DP 就是有多個變數的 DP，一個變數不足以清楚描述當前的子問題，需要兩個或更多的變數來鎖定狀態。 例如： 走迷宮需要 $x, y$ 座標兩個變數來表示 $dp[x][y]$ LCS（Longest Common Subsequence：最長共同子序列）需要字串 A 的位置 $i$ 和字串 B 的位置 $j$ 表示 $dp[i][j]$ 背包問題：需要物品編號 $i$ 和剩餘重量 $w$ 表示 $dp[i][w]$ Vacation Problem Source：https://atcoder.jp/contests/dp/tasks/dp_c 狀態定義：不能只紀錄 $dp[i]$ 代表第 $i$ 天的最大快樂值，因為要知道第 $i$ 天到底做了什麼活動...

【Pytorch 深度學習筆記】模型驗證與過擬合以及 Autograd 的細節 哈囉大家好我是 LukeTseng，感謝您點進本篇筆記，該篇筆記主要配合讀本 《Deep Learning with pytorch》 進行學習，另外透過網路資料作為輔助。本系列筆記是我本人奠基深度學習基礎知識的開始，若文章有誤煩請各位指正，謝謝！ 本篇為 《Deep Learning with pytorch》 這本書 5.5.3 Training, validation, and overfitting 及 5.5.4 Autograd nits and switching it off 的相關筆記。 模型驗證（validation） 在訓練模型時，最重要的目標是讓模型不僅能記住所給定的訓練資料，還能對沒見過的資料泛化（Generalization）。而最壞的情況是遇到過擬合。 :::info 泛化（Generalization）指的是模型在訓練時從資料中學到「可重複使用的規律」，因此面對沒看過的新資料（同類型、但不是訓練集裡的樣本）也能做出合理的預測，而不是只有把訓練資料背起來而已。 ::: 因...

【Pytorch 深度學習筆記】Autograd 自動微分機制與 Optimizers 優化器 哈囉大家好我是 LukeTseng，感謝您點進本篇筆記，該篇筆記主要配合讀本 《Deep Learning with pytorch》 進行學習，另外透過網路資料作為輔助。本系列筆記是我本人奠基深度學習基礎知識的開始，若文章有誤煩請各位指正，謝謝！ 本篇為 《Deep Learning with pytorch》 這本書 5.5 PyTorch’s autograd: Backpropagating all things 的相關筆記。 什麼是 Autograd 在機器學習中，需要計算損失函數對參數（權重 $w$ 和偏差 $b$ ）的導數，以便更新參數。 雖然可以手動推導並解析運算式，但如果今天是擁有數百萬個參數的深層模型呢？總不可能一個一個手動去算吧，因此 PyTorch 提供一個機制叫做 Autograd。 只要給定一個前向運算式（無論多麼複雜），PyTorch 都能自動提供該運算式對其輸入參數的梯度。 使用 Autograd 先前溫度計例子定義的模型函數、損失函數如下（Code...

【Pytorch 深度學習筆記】機器如何學習 哈囉大家好我是 LukeTseng，感謝您點進本篇筆記，該篇筆記主要配合讀本 《Deep Learning with pytorch》 進行學習，另外透過網路資料作為輔助。本系列筆記是我本人奠基深度學習基礎知識的開始，若文章有誤煩請各位指正，謝謝！ 本篇為 《Deep Learning with pytorch》 這本書第五章 The mechanics of learning 的相關筆記。 學習僅是參數估計（Learning is just parameter estimation） 在書中的章節 5.2，所想表達的是：所謂學習，在 ML / DL 中，從機制上看就是在參數估計，用資料去把模型裡未知的參數調到最合理，讓模型對新資料也能預測得準。 在書中把學習描述成一個反覆迭代的流程。 給模型一批輸入資料、模型用目前參數算出輸出（Forward）、再把輸出跟正確答案（Ground Truth）相比得到誤差，接著用誤差去決定參數該往哪個方向更新（Backward），重複到誤差夠小為止。 在這邊最重要的觀念是模型不是靠人手寫規則學會，而是...

【C++ 筆記】列舉（Enumeration） - part 34 很感謝你點進來這篇文章。 你好，我並不是什麼 C++、程式語言的專家，所以本文若有些錯誤麻煩請各位鞭大力一點，我極需各位的指正及指導！！本系列文章的性質主要以詼諧的口吻，一派輕鬆的態度自學程式語言，如果你喜歡，麻煩留言說聲文章讚讚吧！ Introduction 列舉（Enumeration），簡稱 Enum，是 C++ 中的一種使用者自定義資料型態（User-Defined Type）。可用於定義一組命名的整數常數，這些常數通常用來表示狀態、選項或模式。 Enum 有助於為整數值賦予有意義的名稱，以提升程式碼的可讀性與可維護性。 主要適用於我們對某項有少量可能數值（如方向、星期幾等）時。 使用 Enum 的情境大致上有以下這三種（可能更多，只是舉例而已）： 方向：東、西、南、北 遊戲狀態：選單中、遊戲中、暫停、遊戲結束 星期幾：週一到週日 定義 enum 與建立一個 enum 在 C++98/03 舊標準中，用關鍵字 enum 來定義一個 enum，被稱為「非強型別列舉」或「傳統列舉」。 基本語法： 12...

【C++】競程筆記（DP：狀態跟轉移） 題目範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 非線性遞迴題型 481 . [Tutorial] 別離太遠 續 Problem Source：https://oj.ntucpc.org/problems/481 這題要求的不是方法數，而是「最大值」。 這題的上一題已經知道要怎麼求方法數了，結果就是一個費氏數列，而這次要求的是讓每個人的能力值總和到最大，那該怎麼求呢？ 遞迴式長得差不多，先定義 base case： $a_1, n = 1$ $a_1 + a_2, n = 2$ 剩下的情況可以寫成 $max(f(n - 1), f(n - 2)) + a_n$ ，因為要最大化能力值，所以從第 n 個的前兩位（編號差不能超過 2）挑出最大的那個。 範例程式碼： 1234567891011121314151617181920212223#include <bits/stdc++.h>using namespace std;using ll = long long;int main(){ int N...

【C++】競程筆記：字串處理 本筆記僅個人學習用途，斟酌參考。 額…我發現我的字串處理實在是太爛了，所以做這篇來挽救一下我的字串題目。 String 宣告方式 有四種： 1234string s1; // 空字串 ""string s2 = "Hello"; // 初始化為 "Hello"string s3(s2); // 複製 s2 -> "Hello"string s4(5, 'A'); // 重複字元 -> "AAAAA" s1 什麼都沒寫，僅宣告的話就是空字串。 s2 賦值 "Hello" 字串，則表示 s2 初始化為 "Hello"。 s3(s2) 括號 s2 寫法就是 s3 複製 s2 的 "Hello"。 s4(5, 'A')，前面是次數，後面是字元，表示重複 5 次 'A'。 輸入方式 輸入字串的方式有一行一行讀跟整...

自動機理論（DFA） 歡迎你點進本篇文章～本篇主要針對計概上課內容做筆記，若你對文章感興趣的話，不妨按下愛心或追蹤我！感謝你的觀看～ 什麼是 DFA 確定有限狀態自動機（Deterministic Finite Automata, DFA）是一種能夠實現狀態轉移的自動機（automaton），屬於計算理論中的基礎模型。 Wikipedia 其中狀態（State）指的是機器在執行過程中的一個特定情況或條件，例如一個電燈開關他的狀態，有可能是開著的狀態，或是關著的狀態。 而所謂的轉移（transfer）就是狀態可能從原本是 ON 的狀態變成 OFF 狀態的過程，或是相反過來，OFF 變成 ON 這個狀態的過程。 狀態（State） 狀態可以分成三種： 起始狀態（Start State）：機器開始時的初始狀態，通常用符號 $q_0$ 或 $s$ 去表示。 接受狀態（Accept State）：也稱最終狀態，就是在當機器讀完所有輸入後停在該狀態時，就表示接受該輸入字串。 一般狀態（States）：其他的中間狀態，負責處理輸入過程的各種情況。 起始狀態的圖長以下這樣，會先有一個箭頭...

【Uva 題庫解題】C++ 個人解題筆記 - part5 本次題庫擷取自 CPE 2025/12/09 歷屆考題。 1. Uva 10079 - Pizza Cutting PDF Source：https://onlinejudge.org/external/100/10079.pdf Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1020 Zerojudge：https://zerojudge.tw/ShowProblem?problemid=c024 解題思路： 先從最小情況 base case N = 0 開始推算起： N = 0：表示不切，輸出 1 塊。 N = 1：切 1 刀，輸出 2 塊。 N = 2：切 2 刀，且第 2 刀要跟第 1 刀相交才能切最多塊，輸出 2 + 2 = 4 塊。 N = 3：切 3 刀，第 3 刀要跟前 2 刀相交才能切最多塊，輸出 4 + 3 ...

隨機存取協議：Pure ALOHA、CSMA Hello Guys, I’m LukeTseng. 本篇將來介紹什麼是 Pure ALOHA、CSMA、CSMA/CD 等等，這些都是運作在 Data link layer 上面的。若本篇文章有誤，歡迎各位指正，若你也喜歡這篇文章，不妨按下愛心跟追蹤我的個人頁面吧！ 另外本篇文章主要針對上課內容製作筆記，斟酌參考～ 什麼是隨機存取協議（Random Access Protocols：RAPs）？ 這是計算機網路中的資料鏈結層（Data Link Layer）的 MAC 子層中非常重要的一類機制。因此這篇所有的協議像是 Pure ALOHA、Slotted ALOHA、CSMA、CSMA/CD、CSMA/CA 全都是在 Data link layer 上運作的。 隨機存取的相對是循序存取，循序存取的最佳例子就是錄音帶，如果要在第一首歌切到第四首歌，必須要先切第二首、第三首，慢慢切才能切到第四首歌。而隨機存取相反，就可以隨便切，想切就切，所以才會有 RAM（Random-access memory）隨機存取記憶體。 為什麼需要 RAPs...

Switching（交換技術） Hello Guys, I’m LukeTseng. 本篇將來介紹什麼是路由器，若本篇文章有誤，歡迎各位指正，若你也喜歡這篇文章，不妨按下愛心跟追蹤我的個人頁面吧！ 另外本篇文章主要針對上課內容製作筆記，斟酌參考～ 簡介（Introduction） 交換技術（Switching）是指兩個節點透過網路中繼站進行資料傳輸的方式，主要目的是將資料正確且快速地從發送端（Sender）傳送到接收端（Receiver）。在網路通訊中，由於存在數種甚至數千萬種可能的傳輸路徑，交換技術就是為了管理這些傳輸路徑而制定的方法。 其中呢，網路中繼站是指在資料從發送端傳送到接收端的路徑上，負責接收、處理並轉發資料的中間節點設備。這個網路中繼站也有可能是以下這些設備： 路由器（Router） 交換器（Switch） 中繼器（Repeater） 集線器（Hub） 以傳統上來說，Switching 會分成兩種方法： Circuit switching（電路交換） Packet switching（封包交換） Circuit switching Image Sour...