# 2/16 第一堂社課 --- ## 課程介紹 ---- ## 算法班？ ~~資訊之芽~~ 資料結構與演算法 範圍大概能應付 APCS ---- #THE 偷  ---- ## 這學期會教的 - 基礎資料結構 - 基礎演算法 - 動態規劃 - 圖論 ---- ## 基礎資結 - stack - queue - linked list ---- ## 基礎演算法 - 排序與搜尋 - 貪心 - 分治 ---- ## 動態規劃 - 就是基礎 DP - 現在聽不懂也沒差（？ ---- ## 圖論 - 圖與樹 - 圖的遍歷 - 最短路 - 拓撲排序 ---- ~~以上這些東西不保證都會教~~ ---- C++ 語法的部分請參考 [上學期課程](https://hackmd.io/@harrisyu/hsnucrc1121) [前國手 blog](https://emanlaicepsa.github.io/2020/10/21/0-index/) ---- 有用的算法資源 [資訊之芽算法班](https://sprout.tw/algo2023) ~~各校校隊培訓~~ --- ## 資料結構與演算法 ---- 資料結構：有效儲存資料的結構 演算法：解決問題的方法 ---- 一個好的程式 = 好的資料結構 + 好的演算法 ---- 一個題目 = 題敘 + 輸入 + 輸出  ---- 我們要做的就是把輸入轉換成他想要的輸出 用**好的程式**解決！ --- ## 線上評測系統（OJ） 寫題目的地方 ---- ## [ZeroJudge](https://zerojudge.tw/) - 題目很多 - ~~水題很多~~ - 題目品質越來越差（？ - ~~沒事可以去這裡刷題~~ ---- ## [TIOJ](https://tioj.ck.tp.edu.tw/) - 建中的 OJ - 題目品質較高，難度較高 - 沒事來這裡刷題 - ~~可以享受很多 TLE 和 MLE~~ ---- ## [Sprout OJ](https://neoj.sprout.tw/) - 資訊之芽的 OJ - 大多是基礎題和基礎應用題 - 滿值得寫的 ---- ## [CSES](https://cses.fi/problemset/list/) - 一大堆裸題 - 學競程必備階段 - 非常值得寫 --- ## 前綴和 ---- 一個長度 $N$ 的序列 $A$ 前綴：$A_1\sim A_k, k\ge 1$ 後綴：$A_k\sim A_N, k\le N$ ---- 例序列 $\{1, 2, 3, 4, 5, 6\}$ $\{1\}$ 是一個前綴 $\{1, 2, 3\}$ 是一個前綴 $\{1, 4\}$ 不是一個前綴 ---- [靜態區間和](https://cses.fi/problemset/task/1646/) 給定一個長度 $n$ 的序列 $A$ 有 $q$ 筆詢問 每次詢問 $[l, r]$ 的總和 即 $\displaystyle\sum_{i=l}^{r}{A_i}$ ---- 怎麼做？ ---- 一個一個加？ $l$ 和 $r$ 的範圍是 $1\sim n$ $O(nq)$ 太慢了 ---- 我們可以維護前綴和 $S_i=\displaystyle\sum_{k=1}^{i}{A_k}$ ---- 想一想要求的是什麼 $\displaystyle\sum_{i=l}^{r}{A_i}$ $=\displaystyle\sum_{i=1}^{r}{A_i}-\displaystyle\sum_{i=1}^{l-1}{A_i}$ $=S_r-S_{l-1}$ ---- 預處理前綴和 $O(n)$ 每次詢問 $O(1)$ 時間複雜度為 $O(n+q)$ ---- ```cpp= #include<bits/stdc++.h> using namespace std; int n, q; long long pre[200005]; int main(){ cin >> n >> q; for(int i=1; i<=n; i++){ cin >> pre[i]; pre[i]+=pre[i-1]; // 預處理前綴和 } for(int i=0, a, b; i<q; i++){ cin >> a >> b; cout << pre[b]-pre[a-1] << '\n'; // 每筆詢問的區間 } } ``` ---- 練習：[二維前綴和](https://cses.fi/problemset/task/1652) 好用的資源：[USACO Prefix Sum](https://usaco.guide/silver/prefix-sums?lang=cpp) --- ## 差分 ---- [差分練習](https://zerojudge.tw/ShowProblem?problemid=e340) 差分陣列 $d_i=a_i-a_{i-1}$ 意思就是第 $i$ 個數和前一個差了多少 ---- 差分可以做什麼 ---- ### 例題 給定一個長度 $n$ 的陣列 $a$ 有 $q$ 筆操作 每次操作會讓 $a_l\sim a_r$ 都加上 $v$ 最後請輸出操作後的陣列 $a$ ---- 用到剛剛的差分陣列 讓 $d_l$ 加上 $v$ $d_{r+1}$ 減掉 $v$ 就相當於 $[l, r]$ 區間整個加上 $v$ 最後再按照前綴和的方法加回去就是最後的陣列了 ---- ```cpp= #include<bits/stdc++.h> using namespace std; int n, q; long long arr[200005], d[200005]; int main(){ cin >> n >> q; for(int i=1; i<=n; i++){ cin >> arr[i]; d[i]=arr[i]-arr[i-1]; // 預處理差分陣列 } for(int i=0, l, r, v; i<q; i++){ cin >> l >> r >> v; d[l]+=v; d[r+1]-=v; // 區間加值 } for(int i=1; i<=n; i++){ d[i]+=d[i-1]; // 像前綴和的方法還原 cout << d[i] << ' '; } } ```