林燈盃 APCS 課程資料彙整

進階班

2020

資料 : https://vjudge.net/article/2291

class1

錄影檔 : Math 20210714 - 朱偉哲,黃允謙 標籤 : GCD, Binary EXP, Prime, Modulo, Matrix

class2

錄影檔 : Shortest Path 20210707 - 朱偉哲,黃允謙 標籤 : Floyd-Warshall, Bellman-Ford, SPFA, Dijkstra

class3

錄影檔 : Heap,minimun spanning tree-20210630-朱偉哲,黃允謙 標籤 : disjoint set union, minimun spanning tree , kruscal, prim

class4

錄影檔 : 動態規劃-20210623-黃允謙

參考資料 :

• https://www.itread01.com/content/1542940564.html

• http://www2.lssh.tp.edu.tw/~hlf/class-1/lang-c/DP.pdf

class5

錄影檔 : graph-1(20210616) 標籤 : 定義graph,dfs, bfs

dfs, bfs實作code : https://pastebin.com/eNx4Wzrt

class6

錄影檔 : graph-2(20210616) 標籤 : BFS實作,二分圖,拓樸topology

class7

錄影檔 : tree (20210609)

2021

class1

課程主題：基礎複習

課程大綱：

• C/C++

• CP knowledge

• CP Techniques

• Complexity

• Compiler

• Competition

課程簡報 : https://hackmd.io/@Ccucumber12/BknmnNK0d#/

8/2基礎複習上課紀錄檔 : https://drive.google.com/file/d/12NAAXZHwj5ema73kuB1OZTvJBHdLRWa8/view?usp=sharing

class2

課程主題：常見技巧

課程大綱：

• Binary Exponentiation

• Prefix Sum

• Discretize

• Enumeration

• Backtracking

• Binary Search

• Divide & Conquer

• Sorting

課程簡報 : https://hackmd.io/@Ccucumber12/SJ9lswGkK#/

題目練習：

• pA(enumeration)

• pB(binary search)

• pC(ternary search)

• pD(prefix sum)

• pE(可以回朔法的枚舉題目)

• pF(離散化)

• pG(快速冪)

• pH(prefix sum + discretize)

• pI(樹上兩點距離)

• pJ(enumeration量杯問題)

Scoreboard : https://docs.google.com/spreadsheets/d/10yJ5KIb7Hs6rqPigLnCAJ8nQVyKcLD2TSiZMR_IUYPo/edit?usp=sharing

8/3 上課記錄檔 : https://drive.google.com/file/d/17Qq8Jxtj5PBXommZihXRDvY2KWDF2O4b/view?usp=sharing

class3

課程主題：基礎資料結構

課程大綱：

• binary heap

• DSU

• sparse table

• monotonic queue

• Fenwick tree

• segment tree

課程簡報：https://hackmd.io/@Ccucumber12/SkuTo_S1Y#/

題目練習：

• pA(monotonic queue算裸題)

• pB(RMQ模板題)

• pC(DSU裸題)

• pD(heap)

• pE(heap2)

• pF(二維BIT (Fenwick tree))

• pG(二維前綴合)

• pH(sparse table)

Scoreboard: https://docs.google.com/spreadsheets/d/10yJ5KIb7Hs6rqPigLnCAJ8nQVyKcLD2TSiZMR_IUYPo/edit?usp=sharing

8/6 上課記錄檔 : https://drive.google.com/file/d/1IR-wLdn-0EIq8cLPwABd44UvH6kNZ4_9/view?usp=sharing

class4

課程主題：樹論

課程大綱：

• centroid

• diameter

• LCA

• euler tour technique

課程簡報：https://hackmd.io/@Ccucumber12/Hk5-jRi1t#/

題目練習：

• pA(樹重心模板題)

• pB(樹重心變化題(只有一點點))

• pC(樹直徑裸題)

• pD(最小直徑樹)

• pE(LCA模板題)

• pF(LCA)

• pG(Euler tour tree)

Scoreboard: https://docs.google.com/spreadsheets/d/10yJ5KIb7Hs6rqPigLnCAJ8nQVyKcLD2TSiZMR_IUYPo/edit?usp=sharing

8/9 上課記錄檔 : https://drive.google.com/file/d/1x2imnPaK_gEH1wGY5wvEQ2JQQM6iujyS/view?usp=sharing

課外補充-重輕鍊剖分模板題 : https://www.luogu.com.cn/problem/P3384 有興趣的同學可以挑戰看看

class5

課程主題：圖論

課程大綱：

• shortest path

• MST

• topological sort

• components

課程簡報：https://hackmd.io/@Ccucumber12/BJGKlTRkt#/

題目練習：

• pA(topological sort)

• pB(單源最短路加一條邊變化題)

• pC(MST模板題)

• pD(全點對)

• pE(單源最短路(無負環)

• pF(負環判斷)

• pG(topological sort)

• pH(Connected Component)

• pI(最小環)

改為進階資料結構範圍可以自己練習看看

• pJ(SCC (strongly connected components))

Scoreboard: https://docs.google.com/spreadsheets/d/10yJ5KIb7Hs6rqPigLnCAJ8nQVyKcLD2TSiZMR_IUYPo/edit?usp=sharing

8/10上課紀錄檔 : https://drive.google.com/file/d/1IPCAl3b6vK3kHeEAEC8Jjuxg29GqM7K5/view?usp=sharing

class6

課程主題：數學

課程大綱：

• number theory

• modular

• combinatorics

• matrix

課程簡報：https://hackmd.io/@Ccucumber12/Hy8nj-fxt#/

題目練習：

• pA(number theory(difficulty : 800))

• pB(number theory(difficulty : 1600))

• pC(combinatorics(difficulty : 1000))

• pD(combinatorics(difficulty : 1600))

• pE(矩陣快速冪-費氏數列)

• pF(MOD簡單計算1)

• pG(一次同餘方程)

• pH(中國剩餘定理)

• pI(擴展歐幾里得算法(extgcd) 變化題)

Scoreboard: https://docs.google.com/spreadsheets/d/10yJ5KIb7Hs6rqPigLnCAJ8nQVyKcLD2TSiZMR_IUYPo/edit?usp=sharing

8/13上課紀錄檔 :https://drive.google.com/file/d/1rcqV_EMpk598piYq_cL1J2qsWm3KpfKx/view?usp=sharing

補充-歐拉函數例題 : https://tioj.ck.tp.edu.tw/problems/1875

class7

課程主題：進階資料結構

課程大綱：

• Segment Trees

• Lazy Propagation

• Sweeping Line

• Dynamic Segment Tree

• 2D Segment Tree

• Persistent Segment Tree

• Treap

課程簡報：https://hackmd.io/@Ccucumber12/B1PqClBlY#/

題目練習：

• pA(區間第K小?大? 持久化線段樹)

• pB(矩形總和面積 線段樹應用掃描線)

• pC(二維線段樹模板)

• pD(動態開點線段樹模板)

• pE(線段樹lazytag模板)

• pF(Treap)

• pG(Treap2)

• pH(Leftist Tree)

• pI(線段樹解區間和)

Scoreboard: https://docs.google.com/spreadsheets/d/10yJ5KIb7Hs6rqPigLnCAJ8nQVyKcLD2TSiZMR_IUYPo/edit?usp=sharing

8/16 上課紀錄檔 : https://drive.google.com/file/d/1CaLX6KxSzqejAZvrPF1rvas3-xrT8d7Y/view?usp=sharing

class8

課程主題：動態規劃

課程大綱：

• Knapsack

• 滾動陣列

• 狀態壓縮

• Sum-over-Subset

• Optimization

課程簡報：https://hackmd.io/@Ccucumber12/Bk6lLyuxF#/

題目練習：

• pA(01背包模板)

• pB(無限背包模板)

• pC(多重背包模板)

• pD(狀態壓縮dp)

• pE(狀態壓縮dp2)

• pF(SOSDP 優化)

• pG(單調對列優化)

• pH(Divide & Conquer dp)

Scoreboard: https://docs.google.com/spreadsheets/d/10yJ5KIb7Hs6rqPigLnCAJ8nQVyKcLD2TSiZMR_IUYPo/edit?usp=sharing

8/17 上課記錄檔 : https://drive.google.com/file/d/1F_k99tZWO9JpgzhBk3BS7-xgVpqIj8bi/view?usp=sharing

class9

課程主題：進階圖論

課程大綱：

• DFS Tree

• Biconnected Component

• Strongly Connected Components

• 2-SAT

• Maximum Bipartite Matching

課程簡報：https://hackmd.io/@Ccucumber12/HylySg2xF#/

題目練習：

• pA(Tarjan+dfs)

• pB(2-sat(difficulty : 1500))

• pC(2-sat(difficulty : 2600))

• pD(maximum bipartite matching)

Scoreboard: https://docs.google.com/spreadsheets/d/10yJ5KIb7Hs6rqPigLnCAJ8nQVyKcLD2TSiZMR_IUYPo/edit?usp=sharing

8/20 上課記錄檔 : https://drive.google.com/file/d/1uvNpM2vX922x6ap-RGx-HX1vFn4bsSPE/view?usp=sharing

class10

課程主題：字串

課程大綱：

• Trie

• KMP

• Z-algorithm

• Rolling hash

課程簡報：https://hackmd.io/@Ccucumber12/rkDAFuAxt#/

題目練習：

• pA(trie)

• pB(KMP)

• pC(Z-algorithm)

• pD(rolling hash)

Scoreboard: https://docs.google.com/spreadsheets/d/10yJ5KIb7Hs6rqPigLnCAJ8nQVyKcLD2TSiZMR_IUYPo/edit?usp=sharing

8/24 上課記錄檔 : https://drive.google.com/file/d/1UIX8nq9gX8DzEKtzOz7jK8EhAE4N_4tI/view?usp=sharing

class11

課程主題：計算幾何

課程大綱：

• 2D-Vector

• Segments

• Sort by Angle

• Convex Hull

• Duality of Points and Lines

課程簡報：https://hackmd.io/@Ccucumber12/BJeOhtzbF#/

題目練習：

• pA(線段相交)

• pB(凸包)

• pC(極角排序)

• pD(凸包面積)

Scoreboard: https://docs.google.com/spreadsheets/d/10yJ5KIb7Hs6rqPigLnCAJ8nQVyKcLD2TSiZMR_IUYPo/edit?usp=sharing

上課補充 對偶性質 : https://codeforces.com/problemset/problem/678/F

class 12 暑期賽

網址：https://codeforces.com/contestInvitation/6a6c3b9df3771afb48ea99da4ad55157a62e5a85

規則：https://drive.google.com/file/d/1YBU9dm8a2Eo6KLuvcVkUyBM0BUcK3QQm/view?usp=sharing

題解：https://hackmd.io/@Ccucumber12/r1Y0jcd-K

題解影片：https://drive.google.com/file/d/1PAGR3wDwvfarfsASTpr_x47e8UsYeFmE/view?usp=sharing

2022

class1

主題：競程入門

講義：https://hackmd.io/@Ccucumber12/B1_ZAUPpc

class2

主題:常用技巧

講義 : https://hackmd.io/pfu2Tz5JRkusQr2cGX7e_A?view

class3

主題:樹論

講義 : https://hackmd.io/4WgTERPXTDqbkx0_lSi-sw

class4

主題：圖論

講義：https://hackmd.io/@Ccucumber12/ryKM3BXA9

class5

主題：動態規劃

講義：https://hackmd.io/@Ccucumber12/Hkzl59uA9

class6

主題：線段樹

講義：https://hackmd.io/@Ccucumber12/Bk5A5tnCq

class7

主題：數學

講義：https://hackmd.io/@Ccucumber12/rycdcCWJo

class8

主題：綜合應用（線段樹進階、DP 優化）

講義：https://hackmd.io/@Ccucumber12/Bk4dRhryi

銜接班

2021

資料 : https://hackmd.io/@110ldadpre/

講師編的講義 : https://hackmd.io/@Distinguished/HJCZMKM8t

卓越盃 : https://hackmd.io/@110ldadpre/r1GT2WtaY/%2FHfSOpfGBQeqy3GoNKFv8aQ

上課紀錄檔 :

• 1/24

• 1/25

• 1/26

• 5/26

上課簡報 :

1.基本技巧

• 簡報 http://gg.gg/xcy2n

1.2 其他基本技巧

• 簡報 https://hackmd.io/@mtmatt/HJE4RGay5

2.排序與二分搜

• 泡沫排序、選擇排序簡報

• C++內建排序函式的應用

• 二分搜補充資料

3.基本STL

• 簡報

4.圖論

• 簡報

n.動態規劃

• 簡報

競賽用參考資料整理 :

• 從零開始的演算法競賽教學(由國際資訊奧林匹亞銀牌的電神所編撰)

• 成大競賽用講義(我是沒用過不過尚哲推薦應該還不錯)

• 基礎練習題單(經過過濾後的優良題目)

• 練習題的題解們(宜中學長嘔心瀝血製作的)

• 基礎複習影片(半小時複習C++基礎語法)

• VScode安裝教學

• 尚未完成的宜中講義

• 不知道哪裡來的講義(大概率建中的)

• 英文書

2022

資料 : HOJ