# 競賽程式 一大根 - 基礎篇
> 為何要學競賽程式呢? 不就給照抄寫一寫就好了嗎? 未來資工系不是都會被AI取代嗎?

資訊工程，既然稱為工程類，就不會只是單純的學語法學怎麼寫。如同文學不是盲目的背誦古文與排列文字，資訊工程也不是跟從。資訊工程，不僅是教你怎麼解決問題，而是教你怎麼解決「不好的解決方案」。這，就是AI永遠做不到的，也是為何資訊工程不沒落。反而，在所有科技加速發展的世代下，資訊工程更重要

的確，我們在做題時都會思考：「這什麼垃圾題目，未來又用不到。」**不唬爛，用不到**。但我們練題目，學觀念的重點不是：「這個問題現實中會不會出現」，而是<font color="#519ccd">「我可以從這個問題得到什麼問題外的收穫」</font>。這也是為什麼競賽程式，雖然應用少，還是有很多值得學習的。

好啦廢話說完了，好好去練題吧，不然你會像我一樣卡標了。

> ### ❗❗❗ 使用方法
> 先看筆記內容、再上網看資源、最後在看習題。
> 提示模擬了看題目應有的思維丶思緒。看習題時，要翻提示前，先思考自己是否窮舉一切，再翻提示慢慢思考。卡住一律從第一個提示開始。建議閱讀題解前看完所有提示。
> 底下筆記觀念標題皆為連結可自行翻閱學習。

## 目錄

### Level 0 觀念

:::success
### [時間複雜度 Time Complexity](https://hackmd.io/@Winterrlund/Time_Complexity)
競賽程式主要考點
優化衡量原則
:::
:::success
### [STL標準模板庫 STL Tools](https://hackmd.io/@Winterrlund/STL_Basics)
通常應該自學，但考量到自己自學時去學了競程用不到的，還是大致條列最重要的幾個資結與妙妙工具。
:::

### Level 1 觀念
:::info
### [二分搜 Binary Search](https://hackmd.io/@Winterrlund/Binary_Search)
最基礎排除並優化法則
:::

:::info
### [陣列運算 Array Mathematics](https://hackmd.io/@Winterrlund/Array_Math)
陣列上的基礎微積分: 前綴和與差分陣列
總和與變化的資訊
:::

### APCS 習題題解
:::success
### [APCS 習題題解](https://hackmd.io/@Winterrlund/APCS_Problem_List)
有缺的題目、想學的題目、或不懂的地方請盡量問~
:::

## 常用資訊

### APCS 大學程式設計先修檢測
> https://apcs.csie.ntnu.edu.tw

#### 時程
請隨時追蹤、盡早報名。

#### 成績說明
請自行翻閱歷年個人最低錄取標準比對自己。目標一律拿4/5+5，不要像我一樣被卡標。5+5真的不難。

#### 題目範圍
高級觀念仍然建立於中高級觀念。
同時，很多模稜兩可的範圍，底下提供較完整的版本，對打程式競賽有幫助的較簡單觀念。

- **Level 0 STL Library 筆記內容**
- 函式 (function)、**遞迴 (recursion)**
- **二分搜尋 (binary search)**、**深度/廣度優先搜尋 (depth/breadth first search, D/BFS)**
- **動態規劃 (dynamic programming, 玄學)**
- **枚舉 (enumeration)**
- **樹狀圖 (tree)**、*生成樹 (spanning tree)*、LCA (lowest common ancestor)
- **圖 (graph)**、最短路 (*Dijkstra*, Floyd-Warshall, Bellman-Ford)
- **元位運算、表示法 (bit operations, representation)**
- 雙指標 (two pointers)、滑動窗戶 (sliding windows)
- *分治法 (divide and conquer)*
- 貪心法則與證明 (greedy method)
- *線段數 (segment tree)*、BIT (fenwick tree)、差分 (difference array)

### TOI 台灣資奧選訓營初選

> https://tpmso.org/toi/

有空就去玩，不要偷懶。注意參加標準。

### 教學資源
**USACO Guide 美國資奧選訓營初選資源**
https://usaco.guide/dashboard
習題很多，教學資源多，部分吻合台灣初選範圍。

**CP Algorithms**
https://cp-algorithms.com/index.html
理論性強，內容廣泛。部分含程式碼示範。

**OI Wiki**
https://oi-wiki.org
上面的但簡體中文版。

**雜七雜八**
- https://www.w3schools.com/cpp/default.asp C++教學
- https://cppreference.com C++語料庫
- https://discord.gg/RnhATqeMtd APCS模擬測驗 Discord

### 習題資源
**CSES Problem Set**
https://cses.fi/problemset/

**AtCoder Contests**
https://atcoder.jp/home

**CodeForces Contests**
https://codeforces.com

**TIOJ 建中解題**
https://tioj.infor.org

**Luogu 洛谷**
https://www.luogu.com.cn

**Zerojudge**
https://zerojudge.tw