Peienwu's Blog

上課內容

並查集 Disjoint Set

目標：快速判斷兩個元素是否同屬一個集合
功能：詢問元素隸屬的集合、合併兩個集合，在圖論中，集合通常表示連通快，並查集可以查詢任兩點是否連通。在實作MST的時候，當我們要檢查兩個點連接成的邊是否會跟其他已經加入的邊形成環，就會使用並查集幫助我們判斷！
複雜度：非常優秀，可以說是O(1)

上課內容

首先是影片的重點整理，主題是DP優化：

DP優化

• 矩陣快速冪優化
  • 費氏數列：O(n)->O(logN)
  • DC
  • 把很大的n做矩陣快速冪降到logN
    閱讀全文 »

這兩週真是風風雨雨，首先第一週是段考週，所以有很多時間拿去惡補段考。第二週則是疫情關係要在家裡線上上課，結果進度就辣了一大截…趕快追QQ！

上課內容

一堆的背包問題（真的很多種耶）

01背包問題
無限背包問題

• 先固定背包數量看價值跟先固定價值看背包數量可以互換

  閱讀全文 »

上課內容

• 使用DP時機：

  • 最優解問題
  • 計數問題
  • 重複子問題

• DP 使用過程

  • 定義狀態
  • 狀態轉移
  • 找到一個會AC的作法，再慢慢優化

上課內容

分治法，一開始講了三個證明遞迴複雜度的方法：

1. 取代法：
   三步驟：Guess, Verify, Solve
   靠經驗假設，並驗證（加一些常數之類的）
2. 遞迴樹法
   不太嚴謹，提供猜答案想法，最後用取代法驗證
   畫出遞迴樹
3. 主定理（Master Theorem）
   比較f(n) 和 n^(logba)的關係
   大於等於小於有三個複雜度
   閱讀全文 »

這一週主題是Greedy，其實貪心法的題目要難可以到很難，有點像一個抽象的想法，需要透過反覆的實作與練習（顯然我缺乏），來更容易的想到題目的解法！

上課內容

影片的內容主要是在證明greedy 的正確性，超複雜的數學證明（又是數學證明！）
原本以為上課會延續證明的內容，沒想到完全沒有講到證明的內容，都是在講解例題（也不錯，有很多題需要慢慢理解）
所以列了上課講過的例題，一定要搞懂！

上課內容

這一週的主題是枚舉(enumeration)，內容主要環繞二分搜、三分搜、DFS剪枝這些部分。
這一週的內容算是相對輕鬆，解數獨的部分也是蠻有趣的！

前兩次上課還沒來得及補齊，先來紀錄一下第三週的內容

上課內容

這一週的主題是基礎圖論、淹水問題(BFS)還有Heap!把這幾個單元排在一起真的是負擔很重QQ

第一次上課，原本想說會輕鬆的度過一個禮拜
沒想到直接用單調隊列當作開場，讓第一個星期圍繞著stack 與queue的資結世界中
但也很慶幸的，在第一週終於學會用很節簡的程式碼寫單調隊列
第二週的內容則是複雜度分析
P 與NP 問題真讓人一頭是大，雖然在競程中對於較複雜的複雜度問題很少派上用場
不過還是蠻有趣的，只要證明P=NP就可以很多錢了！

tioj-1354 池塘裡的青蛙

題序
這是一個排列組合的數學題目，透過動態規劃紀錄小問題的答案