###### tags: `選修`
# APCS(大學程式設計先修檢測)程式實作(V1)
:::success
### 零、評量、學習歷程
:::
### 1. 評量方式
+ 上課基本練習(遲交期限：1週) **50%**
+ 期中上機考 **20%**
- 上學期時間：三、迴圈教完後一週。
- 下學期時間：第 9 次上課。
- 上機考時網路會斷線，沒有任何參考資料，請每個單元至少完成 5 題作業，熟練基本語法。
- 不要考前才寫作業，初學程式會有很多錯誤，要花時間除錯。請自我要求每週至少寫 2 題作業，上機考才會比較保險。
+ 期末上機考 **20%**
- 上學期時間：六、函式教完後一週或倒數第 2 週。
- 下學期時間：倒數第 2 週。
+ 解題報告 **10%**
- 想高分或上機考考差的同學請保握機會。
- 不會的可以去參考網路上的程式碼、解法，同學也可以互相討論，而且是鼓勵的。不論如何，都要在了解解法後，不看別人的程式碼，自己親自寫一遍。
- 中午電腦教室除考前 1 週外有開放時間，沒電腦、沒網路做作業的同學請善加利用。
- 繳交期限：
* 最後一週上課前 1 天。接近期末考，最慢在期中上機考後就要開始動工。
- 分數：
* 每一題 10 分，上限 120 分(12題)。
* ~~每個單元至多可放 2 題~~
* 普通班一~六1題，之後每子單元1題
* 117四開始，每個子單元1題
* 不可以都寫同一單元的題目
* 題號劃掉的太簡單了，只是用來增加信心，不能放入解題報告。
- 報告格式：
* 第1頁為解題目錄(單元、題號、題目、頁碼)。
* 每題的子標題為
(1) 單元、題號、題目、題目簡述
(2) 解題動態、評分結果截圖
(3) 解題思路
(4) 程式碼
(5) 反思(遇到的錯誤、修正的地方、更好的方法…)
(6) 錯誤程式碼
- 檢核方式：
* 有交解題報告者，最後一週會請你在沒有網路的狀態下重寫一題當做檢核(題目由老師挑選)，寫不出來作業直接作廢不算分，請務必自行思考完成。
* 不要為了分數直接複製貼上別人的程式碼，那是無意義的行為，檢核時你就會現出原形，就不用做這種白工了。
- 可整合上課內容後完成課程學習成果，上傳至學習歷程檔案平台。請儘量挑選一開始有錯，然後修正的題目，將修正的想法寫出來更能顯示出反思的能力。
+ 本課程的目標為考APCS檢定，請多寫作業多練習，才有機會考到3級以上。
### 2. [TOI推廣計畫-線上練習賽](https://tpmso.org/toi/index.php/reg/)
+ 成績計算：分數/100直接加在總成績。
+ 上學期10、11、12月，下學期3、4、5月，最後一週。
+ 星期一08:00 ～ 星期五20:00。90分鐘。
+ [證書](https://drive.google.com/open?id=1DcgDKn1R33kOPc_HazdIyQDgyYxSCPlZ)
### 3. [APCS](https://apcs.csie.ntnu.edu.tw/)
+ 實作級分*2，直接加在總成績。
+ 3級分免上機考，上機考成績為100。
+ 4級分以上者，一切皆免，學期成績直接算100。
+ 檢測日期：每年1、6、10月
+ [檢測系統環境](https://apcs.csie.ntnu.edu.tw/index.php/info/environment/)、[檢測作答系統說明](https://apcs.csie.ntnu.edu.tw/index.php/info/systemdescription/)
+ 考古題_[實作題](https://yuihuang.com/apcs/)、[觀念題](https://www.google.com/search?q=apcs+%E7%AD%86%E8%A9%A6+site%3Ahackmd.io&rlz=1C1ONGR_zh-TWTW972TW972&sxsrf=APwXEdf-9KDcc1Qu7Un015OlwMVLQfOHkQ%3A1685505970019&ei=ssd2ZIBq-oXaug-dvbLoBg&ved=0ahUKEwiAi_CE157_AhX6glYBHZ2eDG0Q4dUDCA8&uact=5&oq=apcs+%E7%AD%86%E8%A9%A6+site%3Ahackmd.io&gs_lcp=Cgxnd3Mtd2l6LXNlcnAQA0oECEEYAVDZGFjZGGCkH2gBcAB4AIABQIgBQJIBATGYAQCgAQHAAQE&sclient=gws-wiz-serp)
+ [APCS對升學的效益(愷哥電腦科普-高中生該怎麼準備學習歷程)](https://www.youtube.com/watch?v=ooNgyQRDO4E)
+ [APCS實作題的內容(50:00)](https://www.youtube.com/watch?v=gMsg559nUo0#t=50m)
[](https://i.imgur.com/tkEB5Su.jpg)
+ [吳邦一教授-實作3級分策略](https://www.facebook.com/groups/359446638362710/permalink/685485375758833)
+ [APCS各級距比例](https://www.facebook.com/groups/359446638362710/permalink/732497984390905/)
### 4. APCS 實作題檢測從三級到五級(中正大學 吳邦一教授)
+ [AP325(講義)](https://drive.google.com/drive/mobile/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m?usp=sharing)
+ [APCS實作題檢測(Facebook)](https://www.facebook.com/groups/359446638362710)
+ [TCFSH CIRC Judge(例題與習題)](https://judge.tcirc.tw/)
+ [吳邦一教授簡介AP325內容(【資訊科技學科中心】109學年度研究/種子教師第2次專業知能培訓研習)](https://www.youtube.com/watch?v=gMsg559nUo0)
+ [PythAPCS123講義](https://drive.google.com/drive/folders/1mnVdO2LHq7e4vesn6pt_R0-S6YWtz4Q4?fbclid=IwAR2Xo7LP8V3lWyhJEbFx3F8JLF9AIEI9t9snla9vwwtI4qlGc0mDwJVuf1o)
+ [PythAPCS123 YouTube撥放清單](https://youtube.com/playlist?list=PLpmg1QLbgMuSIDOgOcwf0Fbbn2ZDR7s-X
)
+ [PyApcs45 YouTube撥放清單](https://www.youtube.com/playlist?list=PLpmg1QLbgMuRQXHRkX9iDHyAVIW1D6OJF
)
### 5. 學習歷程檔案(修課記錄、課程學習成果)
+ 最後一週上課結束前如果認證完成，學期總成績加分。
+ [撰寫「課程學習成果」參考資源](https://hackmd.io/@cube/HkCv90e19)。
### 6. 軟體
+ [The collaborative browser based IDE - Replit](https://replit.com/)
+ [GDB online Debugger | Compiler - Code, Compile, Run, Debug online C, C++](https://www.onlinegdb.com/)
+ [Code::Blocks](http://cs.cysh.cy.edu.tw/software/software_download.html)
+ [CP Editor](https://cpeditor.org/)
+ [VSCode](https://hackmd.io/@liaojason2/vscodecppwindows )([無法debug處理](https://stackoverflow.com/questions/37405975/c-for-vs-code-unable-to-start-debugging-program-path-is-missing-or-invalid?fbclid=IwAR1QQOzXkI6LQc2n0L3q0Sywp_Fx92igG83ngDbhLJrMdZXvaFEqtOW04hM))
### 7. [未來學習資源](https://hackmd.io/@cube/HyPW_cR_j)
<br/>
:::success
### 壹、TOI 線上練習賽 新手組範圍
:::
## 一、輸出與輸入、變數、運算式與運算子
:::info
EX_1_1:[a001: 哈囉](https://zerojudge.tw/ShowProblem?problemid=a001)
:::
:::info
EX_1_2:[d060: 還要等多久啊？](https://zerojudge.tw/ShowProblem?problemid=d060)
+ 3元運算子
+ 多元解法 (85-m)%60
:::
:::info
EX_1_3:[d485: 我愛偶數](https://zerojudge.tw/ShowProblem?problemid=d485)
+ %
+ 複合指定運算子
+ 將a,b調整成偶數(a如果是奇數+1,b如果是奇數-1)，計算2個偶數間的偶數
:::
:::info
EX_1_4:[b004: 繩子上吃草的牛](https://zerojudge.tw/ShowProblem?problemid=b004)
+ while(cin >> D >> L)
+ sqrt()、acos(0)，需含入 cmath
+ 半長軸：L/2，半短軸：sqrt((L/2)\*(L/2)-(D/2)\*(D/2))，橢圓面積：pi\*半長軸\*半短軸
+ Q：int D,L？
+ const double pi= ... ;
+ C++小數點位數控制
``` c
#include <iomanip>
cout << fixed << setprecision(3);
// setprecision(n) 會將輸出的數值控制為 n 位數，如果加上 fixed 表示只控制小數點以下的位數。
```
+ C小數點控制printf，需含入 cstdio 標頭檔。
- [printf-引數說明](https://openhome.cc/Gossip/CGossip/PrintfScanf.html)
+ 萬能標頭檔案 #include <bits/stdc++.h>
:::
:::info
EX_1_5:[d039: 11044 - Searching for Nessy](https://zerojudge.tw/ShowProblem?problemid=d039)
+ 邊界可不計代表除不盡可捨棄
+ 輸入的第一行有一個整數t，代表測試筆數
```c
int t;
cin >> t;
while(t>0)
{
....
t--;
}
或
while(t--)
{
....
}
```
```cpp
int a=1,b;
b=a++;
cout << a << " " << b;
b=++a;
cout << a << " " << b;
```
:::
:::warning
~~1.d483: hello, world~~
~~2.a002: 簡易加法~~
+ $+$
3.a861: 1.Secure the Perimeter
+ 2h+2w(*不能省略)，(h+w)*2
4.d226: 10071 - Back to High School Physics
+ v-t 圖算面積
5.d053: Big Chocolate
+ 3x4巧克力需要11刀
+ m-1+m*(n-1) (why?)
6.h215: 客製金莎巧克力金字塔
+ [平方和級數公式](https://www.youtube.com/watch?v=_cQ0Mh_DB7U)
7.d489: 伏林的三角地
+ 海龍公式計算三角形面積
+ s=(a+b+c)/2
+ $area=\sqrt{(s(s-a)(s-b)(s-c))}$
8.d827: 買鉛筆
+ /、\%、(( ))
+ n/12*50+(n-(n/12)*12)*5
9.d277: 矩陣對角線
+ 3元運算子、%
+ 對角線奇數可共用對角線交叉的花盆，偶數不共用
10.b681: 1. 山洞探險
+ 3元運算子
+ 向北公式為2L-1，向南為？
+ long long int
11.d127: 二、牧場面積
+ 接近正方型面積會最大
+ long long int
12.d461: 班際籃球賽
13.d096: 00913 - Joana and the Odd Numbers
+ long long int
+ 有N個奇數為第(N+1)/2列
+ 找出此列最後3個數字與第(N+1)/2列的關係
14.d051: 糟糕，我發燒了！
+ 浮點數(float、double)
+ setprecision 控制輸出數值的「位數」，需含入 iomanip 標頭檔
+ 只控制「小數點後的位數」fixed
+ 型別轉換
15.c776: 106北二1.六邊形屋瓦
+ 扣掉重覆的白色屋瓦。公式？
16.d549: 矩形中的几何
+ PA^2^ + PC^2^ = PB^2^ + PD^2^ (畢氏定理，why?)
+ sqrt()，需含入 cmath 標頭檔
+ printf小數點，需含入 cstdio 標頭檔
+ PA、PB、PC變數形態用long long int或double
:::
## 二、選擇
:::info
EX_2_1:[d065: 三人行必有我師](https://zerojudge.tw/ShowProblem?problemid=d065)
+ &&
+ a > b > c 要寫成 a > b && b > c
:::
:::info
EX_2_2:[e283: APCS 類似題 - 小崴的特殊編碼](https://zerojudge.tw/ShowProblem?problemid=e283)
+ 多項選擇
+ C++ I/O加速：說明[(1)](https://www.chino.taipei/note-2016-0311C-%E7%9A%84%E8%BC%B8%E5%87%BA%E5%85%A5cin-cout%E5%92%8Cscanf-printf%E8%AA%B0%E6%AF%94%E8%BC%83%E5%BF%AB%EF%BC%9F/)、[(2)](http://slides.com/sylveon/i2a-19#/6)、[(3)](https://akr.tw/post/6)
``` c
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int a;
while(cin >> a)
{
cout << a << '\n';
// endl 為 << '\n' << flush;
// 自行測試時中途會看不到答案，按『Ctrl+Z』暫停程式執行後，答案才會一次顯示出來。
}
}
```
:::
:::info
EX_2_3:[a004: 文文的求婚](https://zerojudge.tw/ShowProblem?problemid=a004)
+ ||
+ 閏年為可被4整除且不被100整除，或可被400整除
+ [C語言:運算子優先次序和運算次序](http://magicjackting.pixnet.net/blog/post/70902861-c-語言:運算子優先次序和運算次序)
:::
:::warning
~~1.d064: ㄑㄧˊ 數？~~
+ 比較運算子
+ ==(等於)
+ !=(不等於)
~~2.a012: 10055 - Hashmat the Brave Warrior~~
3.g496: 彗星列車 (Comet)
4.d058: BASIC 的 SGN 函數
+ 巢狀if
+ 比較運算子 > >= < <= == !=
5.e286: 籃球比賽
6.d066: 上學去吧！
+ 巢狀if
+ 亦可將時化為分
7.a006 一元二次方程式
+ sqrt()，需含入 cmath 標頭檔
+ printf，需含入 cstdio 標頭檔
+ [printf-引數說明](https://openhome.cc/Gossip/CGossip/PrintfScanf.html)
8.a053: Sagit's 計分程式
+ 多項選擇
+ 錯誤：if(11<=n<=20)，正確：if(n>=11 && n<=20)
9.d460: 山六九之旅
+ 多項選擇
10.a273: 小朋友下樓梯
+ 小心n或k等於0的情形
11.b186: 97七區資訊學科1(改編)
+ 取餅乾/10，蛋糕/2中小的數即是贈送的盒數
+ 測資會有0 0 0
12.a005: Eva 的回家作業
+ 判斷等差或等比數列，求第5項
+ while(t\-\-)
13.g497: 電梯 (Elevator)
14.h660: 躲避球 (DodgeBall)
15.d057: 11494 - Queen
+ 垂直、水平、或對角線1步可到，其它2步可到
+ abs()可求絕對值，需含入 cstdlib 標頭檔
+ if(x1 == 0 && y1 == 0 && x2 == 0 && y2 == 0) break;
+ 或 if(!x1 && !y1 && !x2 && !y2) break; 讓輸入0 0 0 0時結束。
16.d984: 棄保效應
+ &&、||
+ 運算子優先順序
+ unsigned int
+ a>b+c(a最大) 或 c>a>b(棄b保a) 或 b>a>c(棄c保a)
c>a && a>b && a+b>c
17.b899: 2. 物品探測
+ 分別計算三點間的距離，最長的為正方形的對角線。
+ 正方形四點 A、B、C、D，假設 A、C 為對角，則 D = A + C - B
18.d095: 00579 - ClockHands
+ 分別計算時針與分針相對於12點的角度再相減
+ fabs()可求浮點數的絕對值，需含入 cmath 標頭檔
``` c
char colon; //設一個字元變數，把冒號讀掉
while( cin >> h >> colon >> m && !(h == 0 && m == 0) )
```
19.c461: apcs 邏輯運算子(Logic Operators)
+ 位元運算子&(AND)、|(OR)、(^)XOR
+ 將a、b以位元運算子運算後和c比較
20.d502: 第三題：產品包裝
+ 裝3\*3\*3產品和2\*2\*2產品剩下的空間，用來裝1\*1\*1的產品，可讓需要的包裝箱最少。
+ 一個3\*3\*3產品裝在箱子裏，會剩37個1\*1\*1的空間。
+ 2\*2\*2產品裝在箱子裏，會剩64-8*(b%8)個1\*1\*1的空間。
:::
## 三、迴圈
:::info
EX_3_1:[a824: 2.藏寶問題](https://zerojudge.tw/ShowProblem?problemid=a824)
+ 先完成1+2+....+n
- 逐行除錯看迴圈如何運作
- Q：i=10時，還會回到上面的 for 嗎？
+ 型別轉換
+ 複合指定運算子
+ 每筆測資變數歸零
+ Q：cout << (char)(sum%26+'A'-1) << endl;
a=26,b=26,c=27時，sum=26 不會印出 Z？
:::
<font color="#fff">cout << (char)( (sum-1)%26 +'A' ) << endl;</font>
:::info
EX_3_2:[a024: 最大公因數(GCD)](https://zerojudge.tw/ShowProblem?problemid=a024)
+ 先試試暴力法會如何？(TLE)
+ i++：min(a,b)
+ i\-\-：break
+ [時間複雜度](https://jason-chen-1992.weebly.com/home/time-space-complexity)
+ [輾轉相除法](http://www.mathland.idv.tw/fun/euclidean.htm) (a=bq+r，則gcd(a, b) = gcd(b, r))
+ while(r>0) 除錯練習
+ 除錯練習
(1) 設中斷點
(2) Debug (F8)
(3) Debugging windows/Watches
(4) Next line (F7)
(5) Stop debugger
:::
:::info
EX_3_3:[a215: 明明愛數數](https://zerojudge.tw/ShowProblem?problemid=a215)
+ do_while迴圈
+ 每筆測資變數歸零
:::
:::info
EX_3_4:[c418: Bert的三角形 (1)](https://zerojudge.tw/ShowProblem?problemid=c418)
EX_3_5:[c419: Bert的三角形 (2)](https://zerojudge.tw/ShowProblem?problemid=c419)
+ 巢狀迴圈(內外圈變數不能重複)
:::
:::info
EX_3_6:[h081: 1. 程式交易](https://zerojudge.tw/ShowProblem?problemid=h081)
+ bool stock=true;
:::
:::warning
~~1.d498: 我不說髒話~~
+ for迴圈
2.d490: 我也愛偶數
+ for
+ i=i+1(i++)
+ 變數初值，區塊變數 v.s. 區域變數
3.d074: 電腦教室
+ for、if
4.f605: 1. 購買力
+ 找出3物品最大值和最小值，可使用if或max、min函式。
+ max 若要傳入三個以上的參數，須用大括號包住，並含入 algorithm 標頭檔。
5.f312: 1.人力分配
+ 以for迴圈窮舉所有可能的工人分配方法。
+ 最大值可用max函式或if。
6.i428: 1. 巴士站牌
+ 最大值、最小值可用max、min函式。
+ 絕對值可abs函式。
7.j605. 1. 程式考試
8.d356: NOIP2002 1.级数求和
+ 型別轉換
+ 浮點數誤差(float->double)
9.d010: 盈數、虧數和完全數
+ 將因數累加
10.c299: 1. 連號或不連號
+ 輸入數列時，找出其最大和最小值(可使用if或max、min函式)
+ 最大-最小+1==n，表示這個數列是連續的
11.d186: 11461 - Square Numbers
+ 完全平方數的判定
12.e622: 虛擬寵物大師 (Master)
+ 計算寵物成長後最終CP值，記錄最大值。
13.a038: 數字翻轉
+ while
+ 不斷取個位數加入翻轉數字
14.g498: 兔子跳躍 (Rabbit)
+ 每次d先-n，再看看剩下的d%m是否為0，亦即試試看所有的組合方式。
15.a536: 11689 - Soda Surpler
+ 每次換的汽水又可再變成空瓶子拿去換
+ 可以換的汽水數量=所有空瓶數/c
+ 手上空瓶=所有空瓶數/c+所有空瓶數%c
16.d189: 11150 - Cola
+ 不論開始有幾瓶，最後的剩餘狀況都只1瓶或2瓶
17.d122: Oh! My Zero!!
+ 0的數量為2和5因數個數的較小值，對n!來說2的因數個數一定會比5多
18.a149: 乘乘樂
+ 運算子優先順序 sum=sum*(n%10)
+ 複合指定運算子
19.c561: Bert 愛搗蛋
+ 將數值反轉的方法，假設 a為原數值，rvs為反轉後的數值(預設值為 0)
rvs=rvs*10+(a%10);
a/=10; // 讓個位數消失
20.d660: 11764 - Jumping Mario
+ prev=now
21.b003: 運算式 + - 符號設定問題
+ 1+2....+n=sum，沒有任何負號時是最大值，如果此時sum小於k，根本不可能有答案，所以sum一定要>=k。
+ 如果m前有一個負號時，sum會少2*m，所以如果sum-k為偶數，則可從1~n找出數字減掉。
+ [解題參考1](https://home.gamer.com.tw/creationDetail.php?sn=4156133)、[解題參考2](https://zrn-code.github.io/2020/09/22/b003/)
22.c420: Bert的三角形 (3)
+ 巢狀迴圈
23.f063: The Strongest Chain
+ 巢狀迴圈
24.c013: 00488-Triangle Wave
+ 巢狀迴圈
+ 下半部 for(k=A-1;k>0;k\-\-)
25.h026: 202001_1 猜拳
:::
## 四、陣列
### 1. 陣列宣告
``` c
int a[5]; // 宣告一個大小為5的int陣列
a[0]=80; // 陣列的索引值由0開始
a[5]=90; // 錯誤，索引值0~4
int a[5]={1,3,5,7,9}; // 宣告陣列時設定初值
int a[5]={1}; // a[0]初值1，其餘預設為0
for(int i=0;i<5;i++) // 以 for 迴圈來控制陣列的 index
cin >> a[i];
int a2d[4][2]; // 宣告二維陣列(多維陣列)
int a2d[4][2]={{1,2},{3,4},{5,6},{7,8}};
Q：如何建立可以儲存班上期中考成績的二維陣列？
// a2d[r][c]表示第 r 列，第 c 欄的值(類似英文書寫習慣)
```
:::info
EX_4_1:[g275: 1. 七言對聯](https://zerojudge.tw/ShowProblem?problemid=g275)
+ [1-based indexing](https://xlinux.nist.gov/dads/HTML/oneBasedIndexing.html)
+ bool error=false;
:::
:::info
EX_4_2:[d478: 共同的數 - 簡易版](https://zerojudge.tw/ShowProblem?problemid=d478)
+ 先試試直觀巢狀迴圈會如何？(TLE，50%)
+ 依序比較兩數列
+ C++ I/O加速
:::
:::info
EX_4_3:[c291: APCS 2017-0304-2小群體](https://zerojudge.tw/ShowProblem?problemid=c291)
+ 不斷追蹤下一位朋友，直到他已經被紀錄過。
+ 先完成沒有 vst 陣列(會造成重復算)。
:::
### 2. 二維陣列
:::info
EX_4_4:[f606: 2. 流量](https://zerojudge.tw/ShowProblem?problemid=f606)
+ 二維陣列
+ [整數最大值可用0x3f3f3f3f](https://blog.csdn.net/jiange_zh/article/details/50198097)
+ memset將陣列歸零，memset(a, 0, sizeof(a)); 需含入 cstring 標頭檔
+ 檢定時如果沒有把握二維陣列的解法，可以先做n=1時的子題，會簡化為1維陣列，拿到一半的分數。
範例輸入
1 3 3
30 23 23
0
1
2
範例輸出
168
+ 同城市的伺服器流量要合併計算費用，所以不能直接以伺服器對城市計算費用 → 範例輸入 #1 會對，但範例輸入 #2 合併流量超過 1000 會錯誤。
+ 先將伺服器傳送到城市的流量Q[n][m]，轉為城市(伺服器所在城市)到城市間的流量A[m][m] (將伺服器流量加總到它所在城市編號那一列)。
以範列輸入1為例 (假設 城市0 為 台北、1 為 台中、2 為 台南)：
2 3 3
30 23 23
5 25 3
0 0
0 1
0 2
|c=(0,0)||||(0,1)||||(0,2)||||
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
||台北|台中|台南||北|中|南||北|中|南|
|台北|35|48|26|北|30|23|23|北|30|23|23|
|台中|0 |0 |0 |中|5 |25|3 |中|0|0|0|
|台南|0 |0 |0 |南|0 |0 |0 |南|5|25|3|
:::
:::info
EX_4_5:[d596: 1. 猜九宮格裡的地雷](https://zerojudge.tw/ShowProblem?problemid=d596)
+ 因為只有9個格子，且每個格子只有4個相鄰格子，所以以二維陣列記錄每個格子其相鄰格子的編號最簡單。[不然就要分別計算上、下、左、右的編號。](https://zrn-code.github.io/2020/07/03/d596/)
+ 以一維陣列記錄格子編號是否有地雷(bool)
+ 「與地雷相鄰格子」的4個鄰居都可能是地雷
+ 「與地雷不相鄰格子」的4個鄰居都不是地雷
+ [1-based indexing](https://xlinux.nist.gov/dads/HTML/oneBasedIndexing.html)
:::
:::warning
1.b138: NOIP2005 1.陶陶摘苹果
2.b127: 會議中心（Room）
+ 一維陣列
+ [費式數列](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97)
3.g595: 1. 修補圍籬
4.c067: Box of Bricks
+ 一維陣列
5.a034: 二進位制轉換
+ 餘數輸出由下而上倒序寫 for(int j=i-1;j>=0;j\-\-)
6.f579: 1. 購物車
+ 商品編號為陣列的索引值。
+ 不用陣列亦可。
7.i399: 1. 數字遊戲
8.i071: 風景 (Landscape)
+ 1-based indexing
+ 從小明家往左、往右檢查>小明家樓高的數量，錯誤的原因為？
+ 以變數(LMax、RMax)記錄小明家左邊、右邊最高樓高(初值為小明家高度)。從小明家往左、往右檢查，如果檢查的樓高>LMax、RMax，則答案+1，並調整LMax、RMax。
9.g797: 洗牌 (Cards)
10.a240: 第一題：1 / 17 小數第 n 位
11.a020: 身份證檢驗
+ 以陣列將英文代號轉為數字
12.b139: NOIP2005 2.校门外的树
13.d097: 10038 - Jolly Jumpers
+ 宣告一個記錄差的陣列d(初值為0)，若兩數的差為3，則d[3]=1
+ 輸入結束後，如果d[1~n-1]有0，則不是jolly jumper
14.d563: 等值首尾和
+ 以迴圈讓prefix由前往後加，suffix由後往前加
+ 如果prefix(前段和)==suffix(後段和)則答案加1，同時往前、後各加一個元素
+ 如果prefix<suffix，則prefix往後加一個元素
+ 如果prefix>suffix，則suffix往前加一個元素
15.a040: 阿姆斯壯數
+ pow(x,y)計算xy，需含入 cmath 標頭檔
+ 以迴圈和%求n位數整數的個位、十位…，放入陣列，並計算n
+ 再以迴圈將所有位數的n次方加起來，判斷是否等於此整數
16.d123: 11063 - B2-Sequence
+ 宣告一個記錄兩數和是否存在的陣列s(初值為0)
+ 以兩數和當成index，如果不存在，則s[兩數和]=1
17.d424: 00105 - The Skyline Problem
+ 使用陣列紀錄每個x軸座標上的最高高度
+ 輸出時注意邊界
18.c435: MAX ! MAX ! MAX !
+ 爆力解會TLE
+ 往後掃描時不斷記錄最大範圍答案和最大值(一層迴圈完成)
+ [解題參考](https://alan23273850.github.io/Online-Judge-Problems/zerojudge/c435MAX-MAX-MAX-/)
19.a693: 吞食天地
+ 每次都重算會TLE
+ 前綴和
20.a015: 矩陣的翻轉
+ 二維陣列
21.d481: 矩陣乘法
+ 二維陣列
22.a694: 吞食天地二
+ 二維陣列
+ 前綴和
+ [C++ I/O加速](http://chino.taipei/note-2016-0311C-的輸出入cin-cout和scanf-printf誰比較快？/)
23.a417: 螺旋矩陣
+ 二維陣列
+ memset將陣列歸零，memset(a, 0, sizeof(a)); 需含入 cstring 標頭檔
+ 逆時針即順時針的轉置矩陣
24.i376: 尋寶 (Treasure)
+ 每一列的最大值可能會有2個以上。
25.b965: 第 2 題 矩陣轉換
+ 二維陣列
+ 旋轉座標轉換
A (0,0) -> (0,2)
B (1,0) -> (0,1)
C (2,0) -> (0,0)
D (0,1) -> (1,2)
E (1,1) -> (1,1)
F (2,1) -> (1,0)
+ 旋轉後的r，等於轉換前的c。
+ 旋轉後的c，等於r數量(3)-r-1。
26.a291: nAnB problem
+ 使用陣列紀錄是否比較過
+ 使用 scanf 和 printf 才不會TLE
27.h026: 202001_1 猜拳
28.g276: 2. 魔王迷宮
29.g596: 2. 動線安排
+ 水平線若有和垂直線相交，刪除時要注意交點不可刪除。
30.h027: 202001_2 矩陣總和
+ 將矩陣距離計算、總和差異寫成函式會比較方便。
31.j123: 2. 運貨站
+ 可直接模擬，或以陣列紀錄每一列目前的右端位置，計算每個貨物加入之後每一列的改變(目前每一列右端加貨物每一列的寬度)，最大值就是貨物停下來的右端位置，判斷丟棄或放入(貨物右側平整，將陣列貨物所佔的列的右端位置全部調成最大值)。
:::
## 五、字串(字元陣列)
### 1. 字串宣告
``` c
int a[3]={1,2,3};
cout << a << endl; // 陣列名稱為陣列開始的位址
char c='x'; // 宣告字元
cout << c << endl;
cout << (int)c << endl; // ASCII
char s1[3]={'a','b','c'}; // 字元陣列，宣告長度為3的字串要多一個空間用來儲存空字元'\0'作為結束符號，否則會有錯誤
cout << s1 << endl;
char s1[4]={'a','b','c','\0'};
cout << s1 << endl;
string s2="abcd"; // 宣告string類別的字串
cout << s2 << endl;
cout << s2[1] << endl;
cout << s2.size() << endl;
cout << s2.substr(1,2) << " " << s2.substr(1) << endl; // 從idx 1 取2個字元，取的長度不寫代表取到最後1個字元
string s3="1234.56"; // 利用stringstream 做數字、字串間的轉換
float a;
stringstream ss;
ss << s3;
ss >> a;
cout << a+10 << endl;
string s4="1 2 3 4";
stringstream ss(s4);
int a,b;
ss >> a;
ss >> b;
cout << a << " " << b << endl;
```
### 2. 字串相關操作 [演算法筆記](https://archive.is/u1lQL)
:::info
EX_5_1:[a782: 4. Redundant Acronym Syndrome Syndrome](https://zerojudge.tw/ShowProblem?problemid=a782)
+ 不能使用cin >> s
+ getline(cin,s)
+ toupper()將字元變大寫
+ C 需用strcmp()比較兩字串是否相等，陣列的名字代表陣列開始的位址，s=="END"的寫法，即使s為"END"也不會相等。C++ string 可直接用==比較
:::
:::info
EX_5_2:[h083: 3. 數位占卜](https://zerojudge.tw/ShowProblem?problemid=h083)
+ 先用暴力法 $\rightarrow$ NA (score:20%)
+ [string字串截取str.substr(pos,n) ](https://crmne0707.pixnet.net/blog/post/316362030-c%2B%2B-%E5%AD%90%E5%AD%97%E4%B8%B2-substring)
+ [C++基础-string截取、替换、查找子串函数](http://blog.csdn.net/ezhou_liukai/article/details/13779091)
:::
:::info
EX_5_3:[i400: 2. 字串解碼](https://zerojudge.tw/ShowProblem?problemid=i400)
+ 加密步驟
- 如果 e 中 1 的出現次數是奇數，S=BCAAD $\Rightarrow$ S'=ADABC
- e[i]=0 切頭，e[i]=1 切尾，接到 T
|e|1|0|1|1|0|
|-|-|- |- |-|- |
|S'|A D A B ~~C~~|~~A~~ D A B ~~C~~|~~A~~ D A ~~B~~ ~~C~~|~~A~~ D ~~A~~ ~~B~~ ~~C~~| |
|T|C|CA|CAB|CABA|CABAD|
+ 解密步驟(將加密的方法倒著做)
- 對每個 e[i]，如果 e[i] 是 0，把 T[i] 放到 S' 的左側，如果 e[i] 是 1，把 T[i] 放到 S' 的右側。
|e|1|0|1|1|0|
|-|-|- |- |-|- |
|T|~~C~~ A B A D|~~C~~ ~~A~~ B A D|~~C~~ ~~A~~ ~~B~~ A D|~~C~~ ~~A~~ ~~B~~ ~~A~~ D|C A B A D|
|S'|$\,\_$ $\_\,$ $\_$ $\_$ C|A $\_\,$ $\_\,$ $\_$ C|A $\_\,$ $\_$ B C|A $\_\,$ A B C|A D A B C|
- 如果 S' 宣告為 string，可以先將字串擴充為長度 n 的空字串，才能依索引值放入。[S.resize(n);](https://cplusplus.com/reference/string/string/resize/)
- 如果 e 中 1 出現次數是奇數，將 S' 左右對調得到 S，可直接交換前後元素(swap)或使用 str.substr()
+ 後面的 e 要先處理。
:::
:::info
EX_5_4:[a130: 12015 - Google is Feeling Lucky](https://zerojudge.tw/ShowProblem?problemid=a130)
+ 找最大值
+ [結構(struct)](https://kopu.chat/2017/05/30/c-%E8%AA%9E%E8%A8%80%EF%BC%9A%E7%B5%90%E6%A7%8B%EF%BC%88struct%EF%BC%89%E8%87%AA%E8%A8%82%E4%B8%8D%E5%90%8C%E8%B3%87%E6%96%99%E5%9E%8B%E6%85%8B%E7%B6%81%E4%B8%80%E8%B5%B7/)
``` c
// 自訂的資料型別
struct 結構名稱
{
資料型別 變數1;
資料型別 變數2;
...
};
```
:::
:::info
EX_5_5：[d392: 读取练习——强大的加法！](https://zerojudge.tw/ShowProblem?problemid=d392)
+ [StringStream－int和sting轉換的另一種方案與清空StringStream](https://dotblogs.com.tw/v6610688/2013/11/08/cplusplus_stringstream_int_and_string_convert_and_clear)
:::
:::warning
1.b428: 凱薩加密
2.a009: 解碼器
3.d124: 3的倍数
+ 3的倍數判別法：各個數字和為3的倍數
+ [1～13的倍數判別法](https://leestar2013.pixnet.net/blog/post/45638266)
4.c290: APCS 2017-0304-1秘密差
+ string類別
+ str.size()
+ abs()可求絕對值，需含入 cstdlib 標頭檔
5.h033: 雜訊移除 (Noise)
6.a022: 迴文
- string類別
- getline(cin,str)
- str.size()
- i\-\-
- str.clear()
- 將字串反轉後比較是否相等
- reverse(str.begin(),str.end()) 需含入 algorithm 標頭檔
- [C++/STL/Algorithm - 維基教科書，自由的教學讀本](https://zh.m.wikibooks.org/zh-tw/C%2B%2B/STL/Algorithm)
6.a054: 電話客服中心
+ 注意100000000答案為KLY
7.a065: 提款卡密碼
+ abs()可求絕對值，需含入 cstdlib 標頭檔
8.d235: Q10929:You can say 11
+ 11的倍數判別法：奇數位數字和與偶數位數字和相差為11的倍數
9.a011: 00494 - Kindergarten Counting Game
+ 不能只算空的數量，字母的後一個是非字母即一個字。
+ getline(cin,s)
+ isalpha()
10.a224: 明明愛明明
+ 統計每個字母出現的次數
+ 迴文的條件為：只有一個字母出現的次數是奇數或全部都是偶數
+ 每筆測資統計的陣列要歸零
+ isalpha()判斷字元是否為英文字母
+ toupper()將字元變大寫
11.d430: 第二題: 計算字數 (count)
+ isalpha()、isdigit()、isalnum()
12.c440: Bert Love QQ !
+ [解題參考](https://naukri7707.github.io/%E7%B7%9A%E4%B8%8A%E8%A7%A3%E9%A1%8C/ZeroJudge/c440/)
13.f291: 試算表大小
+ 將輸入字串的字母轉成整數(26進位)，A為1，B為2，…，AA為27，AA為28，…。
+ [string字串截取str.substr(pos,n) ](https://crmne0707.pixnet.net/blog/post/316362030-c%2B%2B-%E5%AD%90%E5%AD%97%E4%B8%B2-substring)
+ [C++基础-string截取、替换、查找子串函数](http://blog.csdn.net/ezhou_liukai/article/details/13779091)
+ [stoi](https://tw511.com/a/01/11129.html)
+ isdigit()
14.d614: 簡易加法運算
+ 讀入測試筆數T後，需以getline(cin,str)將T後的換行字元讀掉，或cin.ignore()
+ 以cin.getline()或getline(cin,str)，讀入一行
+ isdigit()判斷字元是否為數字
+ 如果是數字，減48(0的ascii)得到數值，加前一個數字*10
+ 如果不是數字，答案加上目前已經造出來的數字。
15.a865: 5. Greek Numerals
+ 將26個字母對應的值儲存為陣列
+ #、$、3為多的字母
16.d275: 11586 - Train Tracks
+ 只要M和F數量一樣且軌道一個以上即可
+ cin.ignore()
17.c459: 2. 自戀數
+ 可將N以字元陣列讀入
+ strlen(N)計算其長度
+ 數字字元-'0'求其數值
+ pow(a,b)計算a^b^，需含入 cmath 標頭檔
+ 根據進位制求出數值大小及每位數字的d次方合，比較是否相等
18.d103: NOIP 2008 1.ISBN号码
+ 數字字元-'0'求得其數值
+ 計算識別碼，如果等於最後一個數字，或餘10且最後一個字元為'X'，則為正確
19.d086: 態度之重要的證明
+ toupper()將字元變大寫或tolower()將字元變小寫
+ A的ASCII值為65，a的ASCII值為97
20.a275: 字串變變變
+ 使用陣列儲存兩字串各別字母出現的次數(以字母的ascii為陣列索引)
+ 如果各別字母出現次數一樣，表示可經由調整順序後，讓兩字串一樣
21.d267: 11577 - Letter Frequency
+ cin.ignore()把數字後的換行字元讀掉
+ isalpha()判斷字元是否為英文字母
+ tolower()將字元變小寫
+ 以字母的ascii為陣列索引記錄出現次數，迴圈找出頻率最高的次數，迴圈印出頻率最高的字母
22.d671: 11716 - Digital Fortress
+ cin.ignore()把數字後的換行字元讀掉
23.c462: apcs 交錯字串 (Alternating Strings)
+ 找出每一個連續大(小)寫片段的長度並將其記錄在陣列
+ [解題參考](https://yuihuang.com/zj-c462/)
24.e294: APCS 類似題 - 小崴的新發現
+ 找下一個完全奇數的方法：從左往右找到某位數為偶數，把此位數加1，此位數之後的數都設為1
+ 找前一個完全奇數的方法：從左往右找到某位數為偶數，把此位數減1(偶數可能為0，要處理向前借位的問題)，此位數之後的數都設為9
+ stoi 把字串轉換為 int，stoll 把字串轉換為 long long
+ atoll()將C字元陣列轉成long long
+ s.c_str()將C++ string轉成C字元陣列
25.j606. 2. 造字程式
+ string s[21];
+ [s[i].resize(k);](https://cplusplus.com/reference/string/string/resize/)：先將新字串擴充為長度k的空字串，才能依索引值放入。
--- stringstream ---
1.d018: 字串讀取練習
2.a158: 11827 - Maximum GCD
+ 數字數量不定以stringstream拆解放入陣列，巢狀迴圈求兩數的GCD
+ __gcd(a,b)可求a、b兩數的GCD，需含入 algorithm 標頭檔
3.d574: 節約符咒
+ stringstream數字轉字串
+ string字串相加
+ 每次都開新的stringstream會TLE
+ ss.str("");
+ ss.clear();
+ ss.str()、ss.str().size()
4.d098: Stringstream運用練習(C++)
+ stringstream字串數字轉換
+ str.length()
+ isdigit()
+ getline()
:::
## 六、函式(遞迴)
``` c
回傳值的型態 函式名稱(變數型態 參數1，變數型態 參數2，...)
{
程式碼
return 回傳值或運算式;
}
```
:::info
EX_6_1:[c039: 00100 - The 3n + 1 problem](https://zerojudge.tw/ShowProblem?problemid=c039)
+ 自訂函式(先練習寫mypow(n,m))
+ 內建函式：swap、max、min
:::
:::info
EX_6_2:[f637: DF-expression](https://zerojudge.tw/ShowProblem?problemid=f637)
+ [遞迴](http://cs.cysh.cy.edu.tw/computer_concept_108/高中數學遞迴.pdf)(先印出[費式數列](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0))
- 問題的答案，可從同類的子問題(規模更小)得到。
- 在函式之中呼叫函式自己本身，要有終止條件，不然會無窮遞迴下去。
+ [解題參考(1)](https://www.youtube.com/watch?v=LMlQIJoU6PA)、[(2)](https://yuihuang.com/zj-f637/)
+ 測資
|  |  | ||
| :--- | :--- | :--- | :--- |
| 1<br>8<br>ans=64<br>| 20101<br>8<br>ans=32<br>| 202010101<br>8<br>ans=24<br>||
+ 函式除錯
- Step into(Shift+F7)
``` c
int f(int n)
{
if(s[idx++]=='0')
return 0;
else if (s[idx++]=='1')
return ~
else
return ~
}
```
:::
:::info
EX_6_3:[f640. 函數運算式求值](https://zerojudge.tw/ShowProblem?problemid=f640)
+ 遞迴
h f f 5 g 3 f 4 3
h(f(f(5)), g(3, f(4)), 3)
= h(f(7), g(3, 5), 3)
= h(11, 4, 3)
= 28
+ stringstream字串轉數字
:::
:::warning
1.f044: 2. 史萊姆生態區 (Slime)
+ log2()
2.c294: APCS-2016-1029-1三角形辨別
+ 自定交換函式swap(傳參考呼叫)(除錯Step into)
+ 使用swap讓a,b,c依小->大排序(c為最長邊)
3.a623: Combination
+ 將n!寫成函式，在主程式呼叫3次
4.b112: 5.高中運動會
+ 多個數的最大公因數
5.a121: 質數又來囉
+ 1不是質數
6.d237: 質數合
+ 以質數函式測試是否需加此數
+ 不可直接輸出142913828922
7.d117: 10924 - Prime Words
+ 以質數函式測試字母值總合
8.c015: 10018 - Reverse and Add
+ 將數字反轉寫成函式
+ 迴文的檢查為數字反轉後和原數字相等即是
9.a263: 日期差幾天
+ 判斷閏年可寫成函式
+ 可算出總天數再相減
--- 遞迴 ---
1.c002: 10696 - f91
+ 遞迴
2.c813: 11332 - Summing Digits
+ 將f(x)寫成函式，遞迴呼叫
3.j124: 3. 石窟探險
4.d693: 最小公倍數
+ n個數的公倍數可以從兩兩連續求公倍數得到
+ long long int
+ 以遞迴求gcd
5.[TCFSH CIRC Judge d007: 習題 Q-1-8. 子集合的和 (APCS201810, subtask)](https://judge.tcirc.tw/ShowProblem?problemid=d007)
+ [解題參考](https://yuihuang.com/tcirc-d007/)
6.a227: 三龍杯 -> 河內之塔
+ 遞迴
+ scanf()、printf() 需含入 cstdio 標頭檔
+ [河內塔|樂和遊戲](http://www.novelgames.com/zh-HK/tower/)
+ [河內塔程式參考](http://notepad.yehyeh.net/Content/DS/CH02/4.php)
7.d672: 10922 - 2 the 9s
+ 遞迴
+ ss.str()
8.f638: 支點切割
+ 遞迴
+ 前綴和、後綴和
+ [解題參考](https://yuihuang.com/zj-f638/)
+ [題目&解題參考](https://www.youtube.com/watch?v=sXjsHFfBBiA)
9.j607. 3. 先加後乘與函數
+ 計算運算式的函式和f函式會互相呼叫，需將函式放在main後，main之前加上函式原型宣告。
+ using ll=long long;
+ [解題參考](https://www.youtube.com/watch?v=12oj97rWjhI)
:::
<br/>
:::success
### 貳、TOI 線上練習賽 潛力組範圍
:::
## 一、物件導向簡介
+ 封裝(私有型態)
+ 繼承(保護型態)
## 二、C++ STL
+ [STL參考文件](https://tioj.ck.tp.edu.tw/uploads/attachment/11/40/1.pdf)
### (一) 演算法
+ [<algorithm> - C++ Reference](https://cplusplus.com/reference/algorithm/)
:::info
EX_2_1_1:[a225: 明明愛排列](https://zerojudge.tw/ShowProblem?problemid=a225)
+ 陣列名為指標說明
+ [0-13 排序 | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/11/16/0-13/)
+ 自訂比較函式(小到大排列時，如果左邊元素<右邊元素，回傳true)
+ 大到小排列比較函式可用greater<int>()
:::
:::info
EX_2_1_2:[a362: 1. 搬雕像](https://zerojudge.tw/ShowProblem?problemid=a362)
+ sort
+ 自訂比較函式
+ struct
+ 排序後的位置-原來的位置編號
:::
:::info
EX_2_1_3:[a524: 手機之謎](https://zerojudge.tw/ShowProblem?problemid=a524)
+ [next_permutation](https://blog.tenyi.com/2007/08/stlnextpermutation.html)
+ [0-14 常用工具/函式(reverse) | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/11/18/0-14/)
+ 如果要產生所有排序，陣列需小到大排序
:::
:::info
EX_2_1_4:[b582: 一個窩](https://zerojudge.tw/ShowProblem?problemid=b582)
+ 找中位數，使用 [nth_element](https://www.itread01.com/content/1543482306.html)，使第n大的元素置於n的位置。用 sort 亦可，但如果測資更大會TLE。
+ C++ I/O加速
+ 開一個100萬的全域變數陣列(區域變數的整數陣列大小只能約50萬)，用 vector 會 TLE。
+ 不可以把所有 x 座標相加再除以 n，此為平均數。
:::
:::warning
1.a251: 假費波那契數
+ 陣列名為指標說明
+ sort
+ 陣列的編號為0~n-1，若從1開始放，要多加空間。
2.b964: 第 1 題 成績指標
+ 排序(STL sort)
3.f408: 迷你蘋菓鎮
+ sort 自訂比較函 式abs(a)<abs(b)
+ 排序後相鄰2數字為不同符號則+1
4.f410: 芝麻街的郵件投遞
+ sort
+ 自訂比較函式
5.c230: 松鼠旅行
+ [TIOJ 1419 . 飛天李晴(?) (Sunny)](https://tioj.ck.tp.edu.tw/problems/1419)
+ 將距離原點的距離由近到遠排序。依距離順序，找出高低差最多的樹。
6.c044: 10008 - What's Cryptanalysis
+ isalpha()
+ toupper()
7.d829: 00146 - ID Codes
+ next_permutation
8.d534: 1. 戰艦謎題
+ next_permutation
9.d913: 1. 彈珠配置
+ next_permutation依序產生一組彈珠順序
+ 比對前6次彈珠順序，如果都符合每次猜測的結果即是答案
10.g005: 倒置文章 (Inversion)
+ reverse(s.begin(), s.end())
11.a480: 導彈攔截系統
+ 設城市與導彈攔截系統1,2的距離為d1,d2
+ 先對各城市d1排序，之後再窮舉求p
+ p = c[i].d1 + max(c[i+k].d2),k>=1
(i城市與導彈1的距離) (其它城市與導彈2的最大距離)
:::
### (二) 循序式容器Sequence Container(vector)
+ [0-17 vector | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/11/30/0-17/)
+ [第 02 課、vector 的使用 - C++ 基礎演算法 - 程式語言筆記 | Zrn Code = 為了夢想、永不停歇](https://zrn-code.github.io/2020/07/19/vector/)
+ [vector小指南](https://www.796t.com/article.php?id=245579)
+ [vector二維陣列](https://ramihaha.tw/c-program-container-vector-array-linklist/)
``` c
// vector 宣告
vector<int> v1; // 宣告一個空的vector，長度不定
vector<int> v2(5); // 宣告一個長度為 5 的vector，初值預設為 0。若要設定其它初值如1 vector<int> v2(5,1)
// 輸出 vector 裡的所有元素
for(int i=0;i<v2.size();i++)
cout << v2[i] << " ";
for(vector<int>::iterator it=v2.begin();it!=v2.end();it++) // 迭代器方式讀取，可用 auto 取代 vector<int>::iterator
cout << *it << " ";
for(int e:v2) // C++ 11 以上
cout << e << " ";
// 加入元素
for(int i=0,x;i<5;i++)
{
cin >> x;
v1.push_back(x); // emplace_back(C++11) 比 push_back 速度稍快
}
for(int i=0;i<5;i++)
cin >> v2[i]; // v1長度不定，不能用idx寫入。可在 for 前先用 v2.resize(5) 調整容器大小
for(int& e:v2) // C++ 11 以上
cin >> e
// 二維 vector 宣告
vector<vector<int>> v3(2, vector<int>(3)); // 2列 3欄
for(int i=0;i<2;i++)
for(int j=0;j<3;j++)
cin >> v3[i][j];
for(int i=0;i<2;i++)
{
for(int j=0;j<3;j++)
cout << v3[i][j] << " ";
cout << endl;
}
for(auto row:v3)
{
for(auto e:row)
cout << e << " ";
cout << endl;
}
vector<int> v4[2]; // v4為一個陣列，有2個元素(2 列)，元素內容為 vector(可變長度)
for(int i=0;i<2;i++)
for(int j=0,x;j<4;j++)
{
cin >> x;
v4[i].push_back(x);
}
for(auto row:v4)
{
for(auto e:row)
cout << e << " ";
cout << endl;
}
```
:::info
EX_2_2_1:[d323: 電腦-窮人的](https://zerojudge.tw/ShowProblem?problemid=d323)
+ sort(v.begin(), v.end())
+ C\+\+ 11設定
- CodeBlocks：Settings / Compiler / Have g++ follow the C\+\+11 ISO C++ language standard
- Dev-C\+\+：專案 / 專案選項 / 編譯器訊息 / 程式碼產生 / 語言標準(-std) / ISO C\+\+11
:::
:::info
EX_2_2_2:[d186: 11461 - Square Numbers](https://zerojudge.tw/ShowProblem?problemid=d186)
+ 以vector改寫
+ [0-14 常用工具/函式(lower_bound & upper_bound) | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/11/18/0-14/)
:::
:::info
EX_2_2_3:[LeetCode 118. Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/)
+ [圖示](https://blog.devgenius.io/leetcode-118-pascals-triangle-b2b1d600de49) [](https://i.imgur.com/ZMweZPz.png)
+ 2維 vector，vector<vector<int>> v(n);
+ v[i].resize(i+1); // vector.resize(空間);
+ vector<vector<int>> v(n, vector<int>(n));
:::
:::warning
1.f819: 圖書館 (Library)
+ 將逾期的書本編號放入vector，排序後印出。
2.f820: 極限運動 (Sports)
+ 將高度儲存在vector，從著陸點分別向左、右滑至停止點。比較停止點高度，輸出高度小(垂直落差大)的位置。
3.c295: APCS-2016-1029-2最大和
+ 將可以整除S的被選擇數字，以vector儲存後印出。
4.h034: 宴會 (Banquet)
+ vector<string> v(n);
5.b051: 2. 排列最大值
+ sort
+ 自訂比較函式大到小排序(s1+s2>s2+s1)
6.a915: 二维点排序
+ vector
+ struct
+ sort
+ [運算子多載，傳參考呼叫](http://web.nuu.edu.tw/~carlu/cpp/ch15.ppt)
+ C++ 11
``` c
for(point& p:v)
cin >> p.x >> p.y;
```
7.b844: 一堆按鈕
+ 直觀解陣列會太大，且會TLE( O(N*K) )。
+ 用陣列記錄N個按鍵號碼，陣列中有幾個數字小於等於詢問的數字，即0、1切換的次數
+ 可先排序，以2分搜加速
8.b005: 布林矩陣的等價短陣
+ 分別計算每行、每列的和為奇數的個數，若沒有奇數為等價，若行、列中各有一個奇數則Change bit (該行,該列)，其餘情況均為Corrupt
9.h082: 2. 贏家預測
+ 以 vector 記錄每輪比賽的編號，依題意模擬記錄贏家、輸家、輸了幾次。
+ v.clear()
:::
### (三) 循序式容器Sequence Container(list)
:::warning
1.a870: 10. List Maker
+ [C++ STL list的初始化、新增、遍歷、插入、刪除、查詢、排序、釋放](https://www.itread01.com/content/1541708352.html)
+ list:push_back、insert、erase
+ find，需含入 algorithm 標頭檔
2.b938: kevin 愛殺殺
+ 鏈結串列Linked List
+ C++ I/O加速 ios::sync_with_stdio(false); cin.tie(0);
+ 已殺，排最後一個，剩最後一個，都要輸出0u0
:::
### (四) 關聯式容器Associative Container(set、multiset)
+ set 內的元素不會重複，且會自動排序(小->大)
+ [0-20 set | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/07/0-20/)
+ [第 06 課、set 的使用 - C++ 基礎演算法 - 程式語言筆記 | Zrn Code = 為了夢想、永不停歇](https://zrn-code.github.io/2020/07/21/set/)
:::info
EX_2_4_1:[d129: 00136 - Ugly Numbers](https://zerojudge.tw/ShowProblem?problemid=d129)
+ 第1500個醜數為8億多，暴力法會TLE
+ 醜數為2^x^ * 3^y^ * 5^z^，所以對已存在的醜數*2、*3、*5放入集合
+ set會自動排序，並過濾重複數字
+ next(it)
:::
:::info
EX_2_4_2:[f607: 3. 切割費用](https://zerojudge.tw/ShowProblem?problemid=f607)
+ 依切割順序排序後，以set來儲存已切割的點，對每個切割點找它的前、後點。
+ [set 初始化](https://shengyu7697.github.io/std-set/)
+ [s.lower_bound()](https://blog.csdn.net/zsnowwolfy/article/details/88057500)、s.upper_bound()
+ insert() 返回值是pair<iterator,bool>，iterator代表插入的位置，若值已經在set中，則iterator表示原來值的位置；bool表插入是否成功。
+ next(it)、prev(it)
+ [解題參考](https://yuihuang.com/zj-f607/)
:::
:::info
EX_2_4_3:[j608. 4. 機器出租](https://zerojudge.tw/ShowProblem?problemid=j608)
+ 先完成 K=1的子題(Greedy)
- activity selection problem 經典題，同[TCFSH CIRC Judge d045: 例題 P-4-4. 幾場華山論劍(activity selection)](https://judge.tcirc.tw/ShowProblem?problemid=d045)
- 若[x,y]是還未選取線段中右端點最小的線段，那麼一定有個最佳解會挑選[x,y]。
- 一開始依照右端點由小到大排序，然後不斷將最小右端的線段挑進最佳解，略過與它重疊的線段。
- 排序自訂比較函數的偷懶寫法$\rightarrow$利用pair。
+ K<=100
- 先依線段右端點排序。
- 一開始一定有個最佳解選取了最小的 K 個右端點，將其放入集合 A。
- 對下一個線段 S，如果其左端點 <= 集合A的最小值，則不可能選取。否則一定有最佳解會選它，將S右端點取代A中 < S左端點的最大值。(從可用的機器中，找「最晚」結束的機器來使用，因為留較早結束的機器，可讓之後的活動被選的機會更多)
- 因為 K<=100，用線性搜尋O(nk)的方式找要取代的點，整體的時間複雜度為(nlogn+nk)。如果 K 很大，用 multiset 可讓搜尋降為O(nlogk)
+ [解題參考](https://www.youtube.com/watch?v=Orf42tOdAsk)
:::
:::warning
1.b523: 先別管這個了，你聽過安麗嗎？
+ set:count、insert、find、end
2.a541: 字典
+ set:insert、find、end
3.h083: 3. 數位占卜
+ 如果 s+t 可以拆成2半相同，那麼 s 的前後端會有 n 個字元相同(枚舉1~s.size()/2)，在 set 尋找是否有剩下的字串。例如 abyyyab，前後端有ab，只要能找到 yyy，就可以形成聖筊。
+ [string字串截取str.substr(pos,n) ](https://crmne0707.pixnet.net/blog/post/316362030-c%2B%2B-%E5%AD%90%E5%AD%97%E4%B8%B2-substring)
+ [C++基础-string截取、替换、查找子串函数](http://blog.csdn.net/ezhou_liukai/article/details/13779091)
+ set:find、count
4.c122: 00443 - Humble Numbers
+ 類似d129
+ typedef long long ll;
+ vector<ll> v(s.begin(),s.end());
5.d442: 10591 - Happy Number
+ 以set記錄曾經出現過的數字，產生下一數字時檢查是否在set中
6.f929: 程式老師的作業
+ 以set記錄0的index，因為set會自動排序，每次操作只要處理s.begin()即可。
7.c421: pA 雲端列印
+ multiset同set會自動排序，但允許重複
+ set: size、empty、begin、end(指向最後一個元素之後的位置iterator)、erase
8.a016: 數獨(SUDOKU)
+ 可用set記錄橫向、縱向、九宮格裏的數字，因為set會過濾重複的數字，判斷是不是剛好有9個數字
9.d194: 11572 - Unique Snowflakes
+ 求最長相異子序列
+ set:count、insert、erase、find
+ queue:front、push、pop、size
+ 當新元素x重複時，刪除queue中x之前的元素(可能產生最多相異的新的開始)
10.c423: pB 還原密碼
+ set:begin、end、insert、erase
+ for(auto e:s) //C++11
+ stringstream字串數字轉換
+ [string字串截取str.substr(pos,n) ](https://crmne0707.pixnet.net/blog/post/316362030-c%2B%2B-%E5%AD%90%E5%AD%97%E4%B8%B2-substring)
+ [C++基础-string截取、替换、查找子串函数](http://blog.csdn.net/ezhou_liukai/article/details/13779091)
11.c807: 一維凸包問題
+ set:insert、erase、empty、begin、end
+ set<int>::iterator(auto) it;
+ auto last=prev(s.end());
+ 使用 s.lower_bound(num)，不要用[lower_bound(s.bebgin(),s.end(),num)](https://blog.csdn.net/weixin_43571920/article/details/100024603)，效率較差。
+ erase 注意[封閉區間、開放區間](http://blog.udn.com/Gabriel33/6398926)
:::
### (五) 關聯式容器Associative Container(map)
+ map 將一個 key，對應到一個 value。key 不會重複，且會自動排序(小->大)
+ [Map (STL) 用法與心得完全攻略](http://mropengate.blogspot.tw/2015/12/cc-map-stl.html)
+ [C++ STL: map的按key和按value排序](https://www.itread01.com/content/1544616191.html)
+ [0-21 map | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/09/0-21/)
+ [第 07 課、map 的使用 - C++ 基礎演算法 - 程式語言筆記 | Zrn Code = 為了夢想、永不停歇](https://zrn-code.github.io/2020/07/21/map2/)
:::info
EX_2_5_1:[a743: 10420 - List of Conquests](https://zerojudge.tw/ShowProblem?problemid=a743)
+ 在map插入<key, value>時，就會按照key的大小順序儲存。
+ mp.find()、mp.end()、iterator
``` c
for(auto it=mp.begin();it!=mp.end();it++)
cout << it->first << " " << it->second << endl;
for(auto e:mp) //取得的元素是pair
cout << e.first << " " << e.second << endl;
```
:::
:::info
EX_2_5_2:[e288: 互補CP](https://zerojudge.tw/ShowProblem?problemid=e288)
+ map<int ,int> mp;
+ mp.find()，mp.end()
+ 位元運算(|、^、<<)
+ 可將第n位元作為有無對應角色的狀態。「1」代表有該角色，「0」代表沒有。
+ 若 a xor b = c 則 a xor c = b。
+ [解題參考](https://www.youtube.com/watch?v=5XSydGMi2HA)
+ C++ IO加速
:::
:::warning
1.b162: NOIP2007 1.统计数字
+ map<int,int>
+ map插入<key, value>時，就會按照key的大小順序儲存。
2.g796: 檔案分類 (Files)
+ 以s%1000/10為map的key
3.c054: 10082 - WERTYU
+ map:find、end
4.d517: 文字抄寫 I
+ map<string,int>
+ C++ IO加速(+'\n')
5.d244: 一堆石頭
+ map<int,int>
+ iterator
+ C++11 auto
6.d492: 10226 - Hardwood species
7.e289: 美麗的彩帶
+ 顏色編號介於0~10^150，以string儲存顏色代號。map<string,int>記錄顏色的數量。(離散化觀念 discretization)
+ 因為順序不重要，可用unordered_map查詢會更快。
+ 因為n最大只到20萬，可以將所有的彩帶顏色讀入陣列，再以L、R代表要出去、進來的顏色索引。
+ C++ IO加速。
+ [解題參考](https://www.youtube.com/watch?v=cvAX9vtjFY8)
8.b265: Q11286 - Conformity
+ 將課程代碼排序後組成字串當成map的key。
9.a821: 4.王者之路
+ 將每一隊擊數的隊伍以set記錄，輸出擊數隊伍數為n-1，且沒有被擊數的隊伍。
+ map<string, set<string> > mp;
10.e839: P6. 飲食分類 (Food)
+ map<string, vector<string>> mp;
:::
### (六) 容器配接器Container Adaptor(stack)
+ [0-19 queue 與 stack | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/03/0-19/)
+ [第 04 課、stack 的使用 - C++ 基礎演算法 - 程式語言筆記 | Zrn Code = 為了夢想、永不停歇](https://zrn-code.github.io/2020/07/21/stack/)
:::info
EX_2_6_1:[b304: 00673 - Parentheses Balance](https://zerojudge.tw/ShowProblem?problemid=b304)
+ stack:push、pop、top、empty
+ 空的stack執行sk.top()會錯誤
+ scanf("%d\n",&n) 或cin.ignore() 將換行字元讀掉
+ 輸入有空字串，要輸出 Yes，所以以getline(cin,s)讀一整行
:::
:::info
EX_2_6_2:[TCFSH CIRC Judge d028: 例題 P-3-4. 最接近的高人(APCS201902, subtask)](https://judge.tcirc.tw/ShowProblem?problemid=d028)
+ 暴力法會 TLE，尋找前方最近高人的過程中，那些資訊可以刪除以加速之後的搜尋？
+ 如果 a[i-1]<=a[i]，那麼 a[i-1] 不可能是 i 之後的高人，因為由後往前找時，一定會先碰到 a[i] (如果 a[i] 不夠高，那 a[i-1] 也一定不夠高)。
- 7 2 3 1 **5** 6，假設目前處理到 5 ，之前比 5 小的 2 3 1，在處理 6 時，都不需要再檢查。
- 只要以 stack 維護好一個遞減序列，就可有效率的解決問題。
+ 雖然要比較身高，但 stack 裏不能存陣列的值(身高)，而要存陣列的索引(為了計算距離)。
:::
:::warning
1.i213: stack 練習
2.d318: 11185 - Ternary
3.a132: 10931 - Parity
+ 以stack記錄除2的餘數
+ stack:push、pop、top
+ n&1
+ n>>1
4.a565: 2.p&q的邂逅
+ stack:push、pop、empty
+ scanf("%d\n",&n) 或cin.ignore() 將換行字元讀掉
+ C++ IO加速
5.e799: p6. 資工系的浪漫
+ 正整數 Si 要宣告為long long。
+ 10進位轉2進位。
6.b838: 104北二2.括號問題
+ 遇「(」push
+ 遇「)」檢查stack是否是空的，如果不空pop，如果空，則括號不正確。
7.e924. pC. 括號配對
8.h028: 202001_3 砍樹
+ [解題參考](https://www.youtube.com/watch?v=OdUS1kYxvjg&list=PLpmg1QLbgMuRQXHRkX9iDHyAVIW1D6OJF&index=18)
9.f698: 後序運算式
+ [stoi](https://tw511.com/a/01/11129.html)
10.c123: 00514 - Rails
+ 將車廂依序從A方向「push」進Station(stack)，並檢查stack的top是否為B方向要的車廂編號，若是則「pop」(表示開到B方向)。
+ 最後檢查stack是不是空的。
+ stack:push、pop、top、empty
+ 空的stack執行sk.top()會錯誤
11.c907: 尋找最大矩形
+ [解題參考](https://zrn-code.github.io/2020/10/18/c907/)
12.a017: 五則運算
+ [堆疊的應用—中序表示轉後序表示](https://www.notes-hz.com/post/99)
+ [中序式轉後序式](https://market.cloud.edu.tw/content/senior/computer/ks_ks/et/datastruct/compute/compute.htm)->後序式運算。實作步驟可合併。
:::
### (七) 容器配接器Container Adaptor(queue)
+ [0-19 queue 與 stack | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/03/0-19/)
+ [第 03 課、queue 的使用 - C++ 基礎演算法 - 程式語言筆記 | Zrn Code = 為了夢想、永不停歇](https://zrn-code.github.io/2020/07/21/queue/)
+ [0-22 priority_queue | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/10/0-22/)
- 預設pq.top()為取最大值，欲取最小值要使用 greater<int> 當比較函式(Container也要寫)。
- priority_queue<int, vector<int>, greater<int>> pq;
:::info
EX_2_7_1:[TCFSH CIRC Judge d094: Q-7-5. 闖關路線 (APCS201910)](https://judge.tcirc.tw/ShowProblem?problemid=d094)
+ BFS
+ [解題參考](https://yuihuang.com/tcirc-d094/)
:::
:::info
EX_2_7_2:[b231: TOI2009 第三題：書](https://zerojudge.tw/ShowProblem?problemid=b231)
+ 印刷機只有一台，所以不管順序為何，總列印時間不變
+ 隨時可以裝訂無限本書，所以要先列印裝訂久的書
+ pair
+ pair 排序會先以 first 為基準，相同再比 second。因為要根據裝訂時間排序，所以將 {b,p} 放入 pq。
:::
:::warning
1.e447: queue 練習
2.e155: 10935 - Throwing cards away
3.d221: 10954 - Add All
+ 取priority_queue中兩個最小值相加後再放入佇列。
4.d900: NOIP2010 2.接水问题
+ 依輸入序，將其時間與優先佇列中最小值相加後，再放入優先佇列。
5.d371: 3. Huffman編碼中的編碼效能問題
+ 需要求出Huffman code嗎？
6.b298: 老闆阿我要退貨
+ 先把有問題的廠商放入佇列，不斷的從佇列中取出廠商，並且把其下游的廠商加入佇列，直到佇列空為止。
7.f816: TOI_y21m4_a02Youtube
+ priority_queue + 前綴和(累積的下降度)
+ ios::sync_with_stdio(false), cin.tie(NULL); + '\n'
+ [解題參考](https://www.youtube.com/watch?v=lpPhi25Md1c)
8.f174: m6a2-蛋糕(Cake)
+ 雙向佇列(deque)兩端都可push、pop：push_front、pop_front、push_back、pop_back。
+ 前綴和、單調隊列
+ [解題參考](https://tpmso.org/toi/wp-content/uploads/question/202006/Cake.odp)
9.f631: 同學會
+ 以 priority_queue 模擬。
10.c835: 第六題：背包問題
+ 以01背包問題的解法會TLE
+ 2^(1或2或…n-1)^ + 2^n-1^ ≤ 2^n^
:::
### (八) pair
+ [0-18 pair | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/02/0-18/)
+ [C++ STL-Introduction to pair<T1, T2>](https://forum.gamer.com.tw/Co.php?bsn=60292&sn=3518)
+ [c++ pair 用法详解](https://blog.csdn.net/sinat_35121480/article/details/54728594)
:::info
EX_2_8_1:[a915: 二维点排序](https://zerojudge.tw/ShowProblem?problemid=a915)
+ 以 pair 改寫
``` c
pair<int,int> p;
p.first=1;
p.second=2;
p={1,2};
p=make_pair(1,2);
cout << p.first << p.second << endl;
```
+ pair的比較原則是先比前面元素，一樣再比後面元素。
+ 一般 make_pair 使用在需要 pair 當參數時。例如 vector 內的元素為 pair，使用 lower_bound 搜尋。
:::
:::info
EX_2_8_2:[b563: 3.魔法學校交換生問題](https://zerojudge.tw/ShowProblem?problemid=b563)
:::
:::warning
1.b512: 高維度稀疏向量
+ scanf("%d:%d",&n,&m)可忽略 ':'
2.c012: 10062 - Tell me the frequencies!
+ vector<pair<int,int>> v(mp.begin(),mp.end());
:::
### (九) bitset
+ [C++ STL bitset的用法](https://www.itread01.com/content/1542789363.html)
+ [bitset 整理](https://edisonx.pixnet.net/blog/post/34045379)
+ [0-25 bitset | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/14/0-25/)
:::info
EX_2_9_1:[f630: 5. 共同朋友](https://zerojudge.tw/ShowProblem?problemid=f630)
+ 相鄰矩陣平方，計算右上半(對角線除外)非零的元素有幾個。
$$
\begin{bmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{bmatrix}
\begin{bmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{bmatrix}
=
\begin{bmatrix}
2 & 1 & 1 & 1 \\
1 & 2 & 1 & 1 \\
1 & 1 & 3 & 0 \\
1 & 1 & 0 & 1 \\
\end{bmatrix}
$$
+ O(n^3^)，以陣列表示朋友關系只會過88%，改以bitset表示朋友關係，並以AND取代乘法。
+ 檢查是否為0，用count() (時間複雜度 O(n))還不會全對，改用any() (時間複雜度 O(1))。
+ C++ I/O加速。
:::
:::warning
1.f629: 3. 樣本解析
+ 以 int(第0個bit記錄有沒有a，第1個bit記錄有沒有b…) 或 bitset 表示集合。
+ [解題參考](https://nhspc.csie.ntnu.edu.tw/wp-content/uploads/2020/11/nhspc2020_solution.html)
:::
<br/>
## 三、枚舉（enumeration）(Brute Force)
:::info
EX_3_1:[b230: TOI2009 第二題：方便數](https://zerojudge.tw/ShowProblem?problemid=b230)
+ [idoreal number](https://oeis.org/A000926)
+ 使用三層迴圈分別列舉 a、b、c(1~65)，計算非方便數，並以陣列標記。
:::
:::info
EX_3_2:[c460: 3. 軍隊部署](https://zerojudge.tw/ShowProblem?problemid=c460)
+ 單純窮舉會TLE，可利用特性只有8種排列組合來思考。
+ 記錄army[種族][特性]的數量，可將3種特性表示成1個特性值(用2進位觀點，ai權值4、ri權值2、di權值1)。
+ 對3種族的特性值窮舉，如果3個特性值位元運算為7，數量相乘。
+ [狀態壓縮](https://www.csie.ntu.edu.tw/~sprout/algo2017/ppt_pdf/dynamic_programming_3.pdf)
:::
:::warning
1.a583: 1. 座位距離計算問題
+ 窮舉2點間距離
2.d809: 黑暗土地
+ struct
+ 浮點數誤差([以行列式算三角形面積](http://euler.tn.edu.tw/area.pdf))
+ C輸入輸出
3.b122: 用餐地點 (Lunch)
+ 窮舉所有可能的用餐地點，計算移動時間
4.a364: 2.神秘的進位問題
+ 窮舉a,b,c，檢查 C(a, 3) + C(b, 2) + C(c, 1) 是否等於n
5.c049: 00356-Square Pegs And Round Holes
+ 窮舉1/4圓的格子情形再*4
+ 判斷格子的四個點是否都在圓內
6.d914 2. 圍棋資料庫比對
+ 窮舉比較棋盤上每個點的狀況
7.c093: 00608 - Counterfeit Dollar
+ 數據小，直接窮舉可能的24種答案，看那一組符合秤重結果
8.APCS 201806 第2題 完全奇數
+ 從n開始往後，將每個數字都拿來檢查，找到第一個完全奇數。(測資只能過兩組)
+ 找下一個、前一個完全奇數的規律。
9.c074: 00441 – Lotto
+ 不用DFS也可解嗎？
10.i402: 4. 內積
+ 直接按題意做可能會TLE。
+ 暴利枚舉 A 的所有起點s，計算 $C_i=A_{s+i}*B_i$，
使用最大連續區間和累積內積的值。
+ 把 A 或 B 翻轉再做一次。
+ [最大連續區間和](https://www.796t.com/content/1545608012.html)：不斷往後加，每加一次更新答案。如果當前區間和小於
0，則歸零再繼續。
+ DP想法
- [解題參考](https://www.youtube.com/watch?v=7qN9Wg0jmJo)
- 令dp[i][j]為以S[i]與T[j]結尾的最大內積。
- dp[i][j]=dp[i-1][j-1]+S[i]*T[j] (if dp[i][j]\>0)
:::
## 四、排序
+ [各種排序演算法](https://docs.google.com/document/d/10-N2JoDV0ZSH49d4s9zpoE71oPFUMORCfKOaJHKV27w/edit#heading=h.7sf5u9kriydv)
:::info
EX_4_1:[b542: 聽到這兩個人的身高，讓十萬人都驚呆了](https://zerojudge.tw/ShowProblem?problemid=b542)
+ 先以身高排序，以兩個idx L=0、R=1，如果 a[R]-a[L]>K，表示差距過大，L+1；反之 R+1，判斷可不可以找到 a[R]-a[L]==K。
:::
:::info
EX_4_2:[g277: 3. 幸運數字](https://zerojudge.tw/ShowProblem?problemid=g277)
+ 依題意模擬，尋找區間最小值時，可先排序，再檢查數值是否在區間內(區間外直接忽略)。
+ 可用 map 或 pair 記錄數值的索引值。
+ 區間和用前綴和。
:::
:::warning
1.a737: 10041 - Vito's family
+ 將所有親戚的門牌號碼排序，中位數即為 Vito 新家的門牌號碼。
2.d150: 11369 - Shopaholic
+ 將商品價格降序排序，再取每三個內的最小值。
+ reverse
+ i+=3
3.c010: 10107 - What is the Median?
+ 每次輸入都排序會TLE。
+ 以insertion sort的觀念，在已排序的序列找出新數字的正確位置。
4.a539: 10327 - Flip Sort
+ 找出每個元素右邊比它大的有幾個。
5.d385: 10905 - Children's Game
+ 比較函式：(a+b)>(b+a)時為要的順序。
6.b966: 第 3 題 線段覆蓋長度
+ 開10^7^bool陣列，讀一筆線段就從L標記到R，最後計算標記的數量。時間O(n)*O(10^7^)可行嗎？ 空間？
+ 將輸入線段依左端點座標排序。則前後兩線段的關係只可能為重疊(包含相連)或不重疊(新線段)
- 如果下一線段的左端點 > 前一線段的右端點，表示前一線段已結束，計算並加總覆蓋長度。
- 如果下一線段的左端點 <= 前一線段的右端點，表示前一條線段可延續，調整前一線段右端點位置即可。
+ [掃描線演算法(sweep line algorithm)](http://web.ntnu.edu.tw/~algo/Point2.html)
7.d501: 第二題：數列最小值
+ 中位數
+ 如果有兩個中位數，介於其中的所有整數都是答案。
8.d555: 平面上的極大點
+ 點的x由小到大序列時，極大點的y是嚴格遞減的。
+ [寻找平面上的极大点](https://blog.csdn.net/cqyz_holiday/article/details/52495567)
9.f461: 現金兌換點卷
+ 巢狀迴圈的暴力法只能過50%，其餘會TLE。
``` javascript=
for(int i=0;i<n;i++)
for(int j=i;j<n;j++)
sum+=abs(a[i]-a[j]);
```
+ 將卡片的數字由小到大排序(a~0~、a~1~、a~2~ ...a~n-1~)，現金點數總和為 (a~1~-a~0~) + (a~2~-a~0~) + (a~3~-a~0~) + …… + (a~n-1~-a~0~) + (a~2~-a~1~) + (a~3~-a~1~) + …… + (a~n-1~-a~1~) + …… ……+(a~n-1~-a~n-2~)
+ 上述式子裏加總 a~i~ (0<=i<=n-1)出現的地方，可得到 i*a~i~ - (n-i-1)*a~i~
+ 排序可用sort(a,a+n)，需含入 algorithm 標頭檔。
+ 還需使用 scanf、printf 才會AC。
+ long long int
10.e809: 1.字母排序 (Letters)
+ 1<=Q<=10^2^、1<=S<=5×10^6^
+ counting sort
+ 前綴和
+ 2分搜
:::
## 五、搜尋
+ [要定義好搜尋的區間是\[a,b\]或\[a,b)或其它。](https://www.itread01.com/content/1548961212.html)
+ 區間選擇不正會確導致無窮迴圈，陣列越界→模擬剩下兩個元素時，是否能正確執行到結束。
:::info
EX_5_1:[f581: 3. 圓環出口](https://zerojudge.tw/ShowProblem?problemid=f581)
+ [TCFSH CIRC Judge d024: 例題 P-2-15. 圓環出口 (APCS202007)](https://judge.tcirc.tw/ShowProblem?problemid=d024)
+ 依題意模擬，直接做會TLE。二分搜必須是單調遞增序列->先將數字轉成前綴和(prefix sum)
- 在位子s開始找一個t，使a[s]~a[t]的和>=Q，相當於找 prefix[t]>=prefix[s-1]+Q。
+ 陣列是圓環，找到陣列尾端時，必須從頭開始找。搜尋前先檢查是否會超過尾端，如果會，扣除到尾端的總和，再從頭開始搜尋。
+ [解題參考](https://www.youtube.com/watch?v=KT23btgYQqA)
:::
:::info
EX_5_2:[c575: APCS 2017-0304-4基地台](https://zerojudge.tw/ShowProblem?problemid=c575)
+ 對n個服務點排序，並計算服務點兩兩相鄰距離。若要分成K群，則找出前K-1個最大的兩兩相離距離，作為分群切割處。(時間複雜度高)
+ 如果基地台直徑 x 可以覆蓋所有服務點，則超過 x 的長度一定也可以->單調性，可用二分搜。
+ 因為基地台直徑的答案一定介於1~(最遠服務點-最近服務點)。先假設可能答案為最大最小值中間，測試k個基地台可否覆蓋所有服務點，不行則調整基地台直徑，對答案進行二分搜。
+ 座標範圍為10億，使用二分搜每次可把數值減半，最多30次的就可找出答案。
:::
:::warning
1.e541: 10474 - Where is the marble
+ 二分搜可用lower_bound
2.g640: 璽羽的壽司
+ 二分搜可用lower_bound
3.f815: TOI_y21m4_a01遊戲升等
+ 以二分搜找出符合條件的最大等級。
4.[d029: 習題 Q-3-5. 帶著板凳排雞排的高人 (APCS201902)](https://judge.tcirc.tw/ShowProblem?problemid=d029)
+ 最左邊界的無限大高度，初值要超過 2*10^7^
+ [TCFSH CIRC Judge d028: 例題 P-3-4. 最接近的高人(APCS201902, subtask)](https://judge.tcirc.tw/ShowProblem?problemid=d028) + 2分搜
+ stack 改用 set 存身高，2分搜可用 st.upper_bound({h[i]+p[i],i});
5.h084: 4. 牆上海報
+ 若海報能張貼的最高高度為 h，則所有 >h 都不能張貼，<=h 都能張貼。(單調性)。使用二分搜在1~10^9^裡找一個可成功的最大值。
+ 以 Greedy 檢查指定高度能否張貼，如果有區間寬度比現在要張貼的海報還寬，則把海報對齊區間的最左邊(可留更多空間給下一張海報)。
6.c904: 天龍國的蜜蘋果
+ [最大化平均值1](https://www.twblogs.net/a/5c9e53cabd9eee7523887628)
+ [最大化平均值2](https://blog.csdn.net/karry_zzj/article/details/70232097)
7.e616: Aggressive cows
+ [最小值最大化](https://blog.csdn.net/qq_43690454/article/details/104020240)
+ 對答案二分搜。假設一個答案，檢查這個答案是不是符合條件限件，以二分搜尋的方式逼進最大值。
8.c942: 露營區規劃
+ 每個圓都至少有一個露營點，所以各點之間環狀距離的最大值為「最小圓周長」，最小值為 0。
+ 以二分搜測試假設的環狀距離，是否可以規劃出 M 個露營點。
+ 可假設 PI=2*acos(0);
9.j125: 4. 蓋步道
+ 以 BFS 求某最大高度差的限制下，起點到終點的最短距離。
+ 對最大高度差二分搜找最小值(可以從起點走到終點)。
10.k290. 借款金額 (Loan)
+ [解題參考](https://tpmso.org/toi/wp-content/uploads/question/202303/loan.odp)
:::
## 六、模擬
:::info
EX_6_1:[f580: 2. 骰子](https://zerojudge.tw/ShowProblem?problemid=f580)
- 骰子有每個相對面之點數和等於7的特性，所以只需儲存三個面的點數即可，如題目所提的上、前、右。
- b為-1向前翻轉，所以原本上面會變成新的前面、原本後面(7-前面點數)會變成新的上面。
- b為-2向右翻轉，所以原本上面會變成新的右邊、原本左邊(7-右邊點數)會變成新的上面。
:::
:::info
EX_6_2:[i401: 3. 雷射測試](https://zerojudge.tw/ShowProblem?problemid=i401)
+ 以2個二維vector分別記錄x、y座標各點上有的鏡子，並排序。
+ y軸有負值，若以vector記錄，可加30000位移為正值。
+ 以二分搜查詢此點的上、下、左、右點。
+ 若以 [二維map](https://www.796t.com/post/NHZjM3U=.html) 記錄可以省略排序。
:::
:::warning
1.c006: 10550 - Combination Lock
+ 逆時針旋轉度數為後刻度減前刻度
2.c036: 00573 - The Snail
3.c094: 00661 - Blowing Fuses
4.d192: 11351 - Last Man Standing
+ 模擬的時間為O(n*k)，當n,k很大時會TLE
+ [遞迴解](https://www.itread01.com/content/1504374014.html)
5.c296: APCS-2016-1029-3定時K彈
+ 約瑟夫斯問題
+ 模擬的時間為O(n*k)，當n,k很大時會TLE
+ [遞迴解](https://www.itread01.com/content/1504374014.html)
6.b351: 幻方(魔方陣)之一：奇N 階
+ 二維陣列
+ 全域變數
+ 記憶體不足
+ memset將陣列歸零，需含入 cstring 標頭檔
+ while(!(r == R && c == C))
錯誤：while(r!=R && c!=C) r或c其中一個等於時就不繼續執行。
7.c292: APCS2017-0304-3數字龍捲風
8.c297: APCS-2016-1029-4棒球遊戲
+ [解題參考](https://ithelp.ithome.com.tw/articles/10197956?sc=pt)
9.f313: 2. 人口遷移
:::
## 七、Greedy
:::info
EX_7_1:[TCFSH CIRC Judge d044: 例題 P-4-3. 十年磨一劍(最少完成時間)](https://judge.tcirc.tw/ShowProblem?problemid=d044)
+ minimum completion time 經典題
+ 放在越前面的工作，等它的人越多，所以短的工作先做。
:::
:::info
EX_7_2:[c471: apcs 物品堆疊 (Stacking)](https://zerojudge.tw/ShowProblem?problemid=c471)
+ next_permutation計算所有排列的消耗能量，時間複雜度 O(n!)
+ 假設a,b其上物品的重量為x，則這些物品的順序，不會影響(a,b)或(b,a)消耗的能量的計算，所以只要考慮a,b順序即可。
- (a,b)-> x*f(a) + (x+w(a))*f(b) = x(f(a)+f(b)) + w(a)*f(b)
- (b,a)-> x*f(b) + (x+w(b))*f(a) = x(f(a)+f(b)) + w(b)*f(a)
- 依兩兩物品(a,b) 其上重量*頻率的值排序(a.w * b.f < b.w * a.f)
+ w(i)/f(i) 由小到大排序。
:::
:::warning
1.[TCFSH CIRC Judge d042: 例題 P-4-1. 少林寺的代幣](https://judge.tcirc.tw/ShowProblem?problemid=d042)
2.[TCFSH CIRC Judge d043: 例題 P-4-2. 笑傲江湖之三戰](https://judge.tcirc.tw/ShowProblem?problemid=d043)
3.a465: 12405 – Scarecrow
+ 遇到可耕種土地時，即在右邊之土地放一個稻草人，並將已被涵蓋的可耕種土地視為不可耕種之土地
4.g544: 美味漢堡 (Hamburger)
+ int 陣列區域變數無法超過50萬，要宣告成全域變數，或用vector。
+ 針對每一段有相同屬性編號的連續區間，取最大的美味程度來加總。
- 當第 i 個配料的屬性和第 i-1 個配料的屬性不一樣，則加上第 i-1 個配料的美味度。
- 當第 i 個配料的屬性和第 i-1 個配料的屬性一樣，則記錄相同屬性配料的美味度中最大者。
5.e538: 11389 - The Bus Driver Problem
+ 將早晨巴士路線由小->大排序，傍晚巴士路線由大->小排序。( sort搭配比較函式 greater<int>() )
+ 最短的早晨巴士路線搭配最長的傍晚巴士路線，會使支付的總加班費最小。
6.g597: 3. 生產線
+ 先計算各機器所要產出的資料量(亦即給若干線段計算每一點有多少線段經過)(差分+前綴和)，再以 greedy 配對，最小工作量配最大時間，第二小配第二大…
+ [前綴和與差分 - WiwiHo 的競程筆記](https://cp.wiwiho.me/prefix-sum/)
+ [解題參考](https://hackmd.io/@peienwu/APCS1107)
7.f832: 隕石 (Meteorite)
+ 將隕石重量、捕捉器容量排序
+ 由捕捉器容量大到小，決定是否可以裝入此時最大重量的隕石。
8.e801: p8. 排課表
+ 依照課程結束時間由小到大排序（結束時間早可增加後面選課的機會），然後從小的開始選。
9.f627: 1. 礦砂採集
+ Fractional knapsack
+ 依單位重量價值由大到小排序。
+ 不斷將單位重量價值最大的礦砂放入背包，直到背包已滿或沒有礦砂可放入。
10.d418: 00993 - Product of digits
+ 將整數分解因數，因為要求Q最小，所以從9開始找
+ 當因數全部分解完，n不等於1，表示不存在Q
11.d731: 11039 - Building designing
+ 樓層分顏色儲存排序，分別從兩陣列中交錯拿出符合條件的最大面積
+ 運算子多載
12.c134: 00668 - Parliament
+ 將n切割成相異數字，並且各數字的乘積最大
13.a673: 10026 - Shoemaker's Problem
+ 兩相鄰工作a(Ta,Fa),b(Tb,Bb)，無論成ab或ba，其他部分的罰金是固定的。差別在於ab(Ta * Fb)還是ba(Tb * Fa)的損失較小
+ 假如ab較小，則 (Ta * Fb)<(Tb * Fa) => (Fa/Ta)>(Fb/Tb) (a的「罰金/時間」比較大)，因此工作的「罰金/時間」大的優先做
+ [解題參考](http://programming-study-notes.blogspot.com/2013/12/uva-10026-shoemakers-problem.html)
14.e915: pC. 追求完美的廚師
+ 點餐所需的累積時間要用long long。
15.f160: 1. 音檔剪輯
+ 從頭開始，盡量讓每次切割出的區間最長，區間個數即會最少。
16.g774: 校隊 (School Team)
+ 依每個班級男生差、女生差排序，男生差小的排前面，排序後先取前n個男生，剩下取女生。
+ 亦可用DP解
:::
## 八、Divide & Conquer
:::info
EX_8_1:[TCFSH CIRC Judge d064: P-5-4. 反序數量 (APCS201806)
](https://judge.tcirc.tw/ShowProblem?problemid=d064)
+ 先完成 merge sort
+ [資訊之芽算法班 第六週 Divide and conquer](https://www.csie.ntu.edu.tw/~sprout/algo2019/ppt_pdf/week06/divide_and_conquer.pdf)
+ 如果看成從前往後掃，對於每個數a[i]只要能求在i之前有多少大於它的數，即可用線段樹來做。[參考網站](https://zh.codeprj.com/blog/4c8dff1.html)
:::
:::info
EX_8_2:[f315: 4. 低地距離](https://zerojudge.tw/ShowProblem?problemid=c471)
+ [解題參考](https://www.youtube.com/watch?v=IkZADcf3lcE)
+ 可依照數字大小分治，把數字分成 small[] 與 large[] 兩子序列分別計算。
- small[] 存 <=n/2 的數字，large[] 存 >n/2 的數字
- 例如[1,4,3,2,3,1,2,4] 分成 small=[1,2,1,2]，large=[4,3,3,4]
+ 合併時，對於 small[] 而言，有多少 large[] 的數字在其中並無影響；對於 large[] 中的數字，除了本身求到的低地距離，還須加上有多少 small[]的數字介於其間才是答案。
+ 或對每個位置i，計算i之前有多少小於a[i]的元素。每個數字第2個位置的值-第1個位置的值即是答案。
- 亦即計算有多少 j<i 且 a[j]<a[i]，即是上一題反序數量同類型的題目。
:::
:::warning
1.d636: 大爆炸bomb
2.a233: 排序法~~~ 挑戰極限
+ MergeSort
3.d542: 10810 - Ultra-QuickSort
+ MergeSort
4.b373: [福州19中]车厢重组
+ 當n很大時(100000)，逆序數對O(n^2^)會TLE(TIOJ 1080)
+ 需用D&C(MergeSort) 或 BIT
5.d861: NOIP2001 3.求先序排列
6.d828: Pascal's triangle's secret (II)
+ 亦即求第n項的費波那契數
+ [矩陣快速冪加速](https://puremathcrush.blogspot.tw/2015/09/blog-post.html)
+ [矩陣快速冪加速實作](http://acm.cs.nthu.edu.tw/problem/10322/)
7.f372: 崑棋的臭豆腐
+ 如果只能通過75%，試著以數學觀念[(費馬小定理)](https://www.youtube.com/watch?v=SyK3IXPITco)找出循環的現象，[建表查表](https://zerojudge.tw/ShowThread?postid=23268&reply=0)。
+ 還需使用 scanf、printf 才會AC。
8.[TCFSH CIRC Judge d056: P-4-15. 最靠近的一對(closest pair) (@@)](https://judge.tcirc.tw/ShowProblem?problemid=d056)
+ [演算法筆記](https://web.ntnu.edu.tw/~algo/Point2.html#3)
+ 橫跨兩側的最近點對，只要依序窮舉中線左側距離 d 以內的點，作為左端點；再找右側距離 d 以內的點，作為右端點。
9.[TCFSH CIRC Judge d065: P-5-7. 大樓外牆廣告](https://judge.tcirc.tw/ShowProblem?problemid=d065)
+ 以最小高為中間的切割點，如果每次的最低點都在邊緣，例如輸入高度是遞增或遞減，時間複雜度會高到O(n^2^)。
+ STL min_element
:::
## 九、Graph
+ [板橋高中校內培訓-圖論](https://docs.google.com/document/d/1ZptN-ebhkOITe1a_BTacqRqWW6DH4HZEv5DBbPnukk0/edit#heading=h.6fi8c333cw4)
+ [圖論相關主題](http://slides.com/sylveon/graph-7)
### (一) DFS
:::info
EX_9_1_1:d626: 小畫家真好用
+ 全域變數
+ 分四個方向做DFS
:::
:::info
EX_9_1_2:[TCFSH CIRC Judge d091: P-7-2. 開車蒐集寶物](https://judge.tcirc.tw/ShowProblem?problemid=d091)
:::
:::info
EX_9_1_3:[c463: apcs 樹狀圖分析 (Tree Analyses)](https://zerojudge.tw/ShowProblem?problemid=c463)
+ 子節點因數量不定，可用vector諸存
vector<int> child[100000];
+ memset
:::
:::warning
1.d365: 10336 - Rank the Languages
+ 類似d626
2.c129: 00572 - Oil Deposits
+ 可以在地圖外包一層0，則不用檢查邊界
+ 可以使用陣列儲存要走的方向
3.d165: 八、草场普查
+ 類似c129
4.a290: 新手訓練系列 ~ 圖論
5.e287: 機器人的路徑
+ [TCFSH CIRC Judge d092: P-7-3. 機器人走棋盤 (APCS 201906)](https://judge.tcirc.tw/ShowProblem?problemid=d092)
6.c139: 00291 - The House Of Santa Claus
7.d324: 00750 - 8 Queens Chess Problem
+ 一維陣列queen[8]，陣列索引為皇后的col，值為皇后的row
+ backtracking
8.b554. 5.貪吃龍遊戲
+ backtracking
9.a229: 括號匹配問題
10.d115: 數字包牌
+ 窮舉
11.d653: VAC+ _ 社費問題 d115加強版
+ 剪枝(將不可能的解剪掉，不繼續遞迴下去)
12.b110: 3. 黑白影像的四分樹表示法
13.d536: 第三題：圖形迴圈偵錯問題
+ DFS偵測環
14.b583. 一個環
+ DFS偵測環
+ [解題參考](https://hackmd.io/@cyk/112/https%3A%2F%2Fhackmd.io%2F%40cyk%2Fbacktracking#%E5%88%A4%E6%96%B7%E6%98%AF%E5%90%A6%E6%9C%89%E7%92%B0)
15.b967: 第 4 題 血緣關係
+ 類似c463
16.b108: 1. 銀河帝國旅行社
+ 類似b967
17.f161: 3. 尋寶之旅
+ 在 DFS 過程中，每次走到一個節點，就將該點顏色數量加一。當 DFS 返回父節點8，把該點顏色數減一，以表示回復到沒有走到此點的狀態。
+ 在拜訪每個節點時，檢查該點的顏色數量有沒有超過最大值。
+ 寶石的顏色號碼不超過10^9^，記錄每一顏色的寶石數用陣列會太大，離散化可以用 [STL map](http://larry850806.github.io/2016/06/06/STL1/#map)。
18.b343: 11518 - Dominos 2
+ 骨牌後可能有多張骨牌
+ vector二維陣列
+ v.clear()
+ fill()
19.a470: 12406 - Help Dexter
+ 數字*10+1或2，產生下一位p位數DFS
20.d762: 10344 - 23 out of 58
+ next_permutation
+ DFS窮舉所有可能
21.c812: 1. 觀光景點
+ DFS搜尋所有和Vk相鄰的點
+ [Edge List](http://www.csie.ntnu.edu.tw/~u91029/Graph.html#2)
+ vector、pair
22.f168: m4a2-分配寶物(Treasure)
+ 枚舉各個寶物分配的情況，總共有3^N種可能的組合。
+ 剪枝。
:::
### (二) BFS
:::info
EX_9_2_1:[TCFSH CIRC Judge d090: P-7-1. 探索距離](https://judge.tcirc.tw/ShowProblem?problemid=d090)
:::
:::info
EX_9_2_2:[f170: m5a1-尋找小狗(Dog)](https://zerojudge.tw/ShowProblem?problemid=f170)
+ queue
+ pair
+ C++ IO加速
:::
:::warning
1.a982: 迷宮問題#1
+ queue
+ pair
2.i177: 小畫家 (Painter)
+ vector二維陣列指定大小與初值：vector<vector<int>> p(h,vector<int>(w,0));
+ [解題參考](https://tpmso.org/toi/wp-content/uploads/question/202204/Painter.odp)
3.a833: 3、沙漠旅行
+ adjacency list
+ priority queue
4.d406: 倒水時間
5.d663: 11730 - Number Transformation
+ 產生轉換次數相同的所有數字B(佇列開頭A+小於它的質因數)，放入佇列
+ 如果產生的數字已在佇列則忽略(新數字轉換次數一定較大)
+ [解題參考](http://kos74185foracm.blogspot.com/2013/07/11730-number-transformation.html)
6.c077: 00417 - Word Index
+ 取出佇列前的字串，添加可以加的字母後放入佇列
+ 使用map存字串對應的值
7.b059: 4. 靈犬尋寶
+ BFS
+ 類似a982: 迷宮問題
8.b701: 我的領土有多大
+ BFS或DFS
9.c117: 00439 - Knight Moves
+ 騎士L走法有八個方向
+ queue
+ struct
10.a634: 14. Knights Path
+ BFS+DFS
:::
### (三) Floyd-Warshall
:::warning
1.d908: 4. 最佳路徑
+ memset
+ 因為陣列包含所有26個字母，所以檢查時沒有連通要略過
2.d282: 11015 - 05-2 Rendezvous
+ 先求所有兩點之間的最短距離，再加總求每個人到其他人的路徑總合最小
+ [整數最大值可用0x3f3f3f3f](https://blog.csdn.net/jiange_zh/article/details/50198097)
+ memset(a, 0x3f, sizeof(a));
3.c128: 00544 - Heavy Cargo
+ d[i][j]=max( d[i][j], min(d[i][k],d[k][j]) )
4.a874: 14. Trace Route
5.a674: 10048 - Audiophobia
+ n[i][j]=min( n[i][j], max(n[i][k],n[k][j]) )
:::
### (四) Dijkstra
:::warning
1.d793: 00929 - Number Maze
+ 把數字迷宮想成無向圖，每個格子與四個方向的格子相連。
+ 以 Dijkstra 演算法求出左上角到右下角的最短距離。
+ priority_queue。
+ [Dijkstra+heap優化](https://www.cnblogs.com/flipped/p/6830073.html)
+ [Dijkstra無法處理負邊，如果有負邊要用SPFA](https://blog.csdn.net/qq_36932169/article/details/78806863)
:::
### (五) SPFA(Shortest Path Faster Algorithm)
:::warning
1.c125: 00534 - Frogger
+ 從起點到終點的每條路都有一個石頭間最大距離，在每條路的石頭間最大距離中，找最小值。
+ [SPFA ](https://blog.csdn.net/muxidreamtohit/article/details/7894298)
+ [解題參考](http://naivered.github.io/2016/04/04/Problem_Solving/UVa/UVa-534-Frogger/)
+ 或使用 Dijkstra、Floyd-Warshall。[Dijkstra+heap和SPFA的区别。](https://www.cnblogs.com/flipped/p/6830073.html)
:::
### (六) 最小生成樹
:::warning
1.a129: 最小生成樹
+ [Kruskal](https://www.itread01.com/content/1545066724.html)
+ [並查集](https://www.youtube.com/watch?v=JoCeTg0QAZQ)(disjoint set)
+ Weight會超過int
2.b181: 2. 網路設計
3.d909: 公路局長好煩惱！？
4.e810: 2.潛水 (Diving)
5.k715. 糧食便道 (Supply)
:::
### (七) 尤拉路徑(Eulerian Path)
:::warning
1.b924: kevin 愛畫畫
+ [尤拉路徑](https://www.csie.ntu.edu.tw/~sprout/algo2017/ppt_pdf/euler_hamilton.pptx)
+ [尤拉迴路](https://meteor.today/article/npAfph)
+ [C++輸出入加速](http://chino.taipei/note-2016-0311C-的輸出入cin-cout和scanf-printf誰比較快？/)
:::
### (八) 拓撲排序(Topological Sort)
:::warning
1.f167: m4a1-社團 Club
+ kahn's algorithm
+ [解題參考](http://slides.com/sylveon/basic-graph#/5/2)
2.a552: 模型
+ kahn's algorithm
3.k734. 4. 開啟寶盒
+ [解題參考](https://hackmd.io/@o2sU2kaQTFW6FIkUj2M-xQ/rkL6-NhU2)
4.f628: 2. 村莊與小徑
+ 圖為 DAG（有向無環圖），所以存在拓樸排序，依照拓樸排序由前往後算，O(n+m)。
+ 邊的權重可能是負的，Dijkstra 不能處理負權的最短路徑。
+ Bellman–Ford / SPFA: 在最糟狀況下的複雜度為 Θ(nm)，只能過比較小的測資。
:::
### (九) 最大流(Maximum Flow)
:::warning
1.d667: 00820 - Internet Bandwidth
+ [演算法筆記-Flow](http://web.ntnu.edu.tw/~algo/Flow.html)
+ Edmonds-Karp
+ [Ford-Fulkerson](http://alrightchiu.github.io/SecondRound/flow-networksmaximum-flow-ford-fulkerson-algorithm.html)
:::
### (十) 二分圖
:::warning
1.c889: 2. 二分圖
+ [二分圖判斷](https://www.itread01.com/content/1545440778.html)
2.d768: 10004 – Bicoloring
+ 清空 vector
```c
vector<int> g[205];
for(int i=0;i<205;i++)
g[i].clear();
```
3.c455: 4. 警力配置
+ [二分圖最大匹配](https://www.itread01.com/content/1501297091.html)
4.g598: 4. 真假子圖
+ [圖論入門———深度優先搜尋實現二分圖判定(dfs染色)](https://www.itread01.com/content/1546276331.html)
+ [解題參考](https://hackmd.io/@peienwu/APCS1107)
:::
### (十一) 關結點(articulation point、割點)
:::warning
1.c111: 00315 - Network
+ [Tarjan算法：求解图的割点与桥（割边）](https://www.cnblogs.com/nullzx/p/7968110.html)
+ [UVa315 Network](http://tnuier.blogspot.com/2018/04/uva315-network.html)
:::
### (十二) 強連通元件
:::warning
1.d197: 11504 - Dominos
+ [Kosaraju’s Algorithm]( https://hackmd.io/@nckuacm/ryLIV6BYI/%2F%40nckuacm%2FryJbqvgjI#Strongly-Connected-Components-SCC)
+ [Tarjan's Algorithm(1)](https://byvoid.com/zht/blog/scc-tarjan/)
+ [Tarjan's Algorithm(2)](http://web.ntnu.edu.tw/~algo/Component.html#4)
+ [解題參考1](https://timbian.wordpress.com/2015/02/16/uva-11504-dominos/)
+ [解題參考2](http://naivered.github.io/2018/03/23/Problem_Solving/UVa/UVa-11504-Dominos/)
2.g554: 周遊列國(Travel)
:::
### (十三) LCA
:::warning
1.d767. 血緣關係
+ [倍增法](https://shawnliang.wiki/post/lca-binary-lifting/)
:::
## 十、Set
+ [演算法筆記 Set](http://web.ntnu.edu.tw/~algo/Set.html#5)
:::info
EX_10_1:[a445: 新手訓練系列- 我的朋友很少](https://zerojudge.tw/ShowProblem?problemid=a445)
+ [並查集](https://www.youtube.com/watch?v=JoCeTg0QAZQ)(disjoint set)
:::
:::warning
1.d831: 畢業旅行
+ 並查集(Union-find Sets、disjoint set)
2.d813: 10583 - Ubiquitous Religions
+ 並查集(Union-find Sets、disjoint set)
3.f677. FJCU_109_Winter_Day3_Lab1 並查集練習
4.[TCFSH CIRC Judge d101: Q-7-11. 紅白彩帶 (APCS201902)(併查集)](https://judge.tcirc.tw/ShowProblem?problemid=d101)
+ [解題參考](https://yuihuang.com/tcirc-d101/)
5.c131: 00615 - Is It A Tree?
+ [以並查集判斷加入的邊是否形成cycle](http://kos74185foracm.blogspot.com/2011/08/615-is-it-tree.html)
+ 只能有一個樹根
6.j243. 111北二2a.資料分組問題
+ [解題參考](https://hackmd.io/@cyk/2022-hc#2a-%E8%B3%87%E6%96%99%E5%88%86%E7%B5%84%E5%95%8F%E9%A1%8C)
:::
## 十一、Tree
:::warning
1.a584: 2. 親等關係
+ 找尋距離兩節點最近的共同祖先。
2.d526: Binary Search Tree (BST)
+ 鏈結串列
+ 二元搜尋樹
3.c126: 00536 - Tree Recovery
+ 二元樹追蹤(前序、中序、後序)
4.f163: 貨物分配
+ 二元搜尋樹
+ [解題參考](https://yuihuang.com/tcirc-d105/)
:::
## 十二、DP
### (一) 基本
:::warning
1.d038: 00900 - Brick Wall Patterns
+ F(1) = 1，F(2) = 2，F(n) = F(n-1)+F(n-2)
2.d054: 11310 - DELIVERY DEBACLE
+ F(0) = 1，F(1) = 1，F(2) = 5，F(n) = F(n-1)+4\*F(n-2)+2\*F(n-3)
+ [解題參考](http://kos74185foracm.blogspot.kr/2011/06/11310-delivery-debacle.html)
3.a111: 12149 – Feynman
+ F(1) = 1，F(2) = 5，F(n) = F(n-1)+n\*n
+ [解題參考](https://sites.google.com/site/zsgititit/home/c-cheng-shi-she-ji/a111-12149-feynman)
4.d378: 最小路徑
+ dp[i][j]=min(dp[i-1][j],dp[i][j-1])+map[i][j]
5.d887: 1.山脈種類(chain)
+ F[0] = 1
+ F[n] = F[n-1]\*F[0] + F[n-2]\*F[1] + F[n-3]\*F[2] +… + F[1]\*[n-2] + F[0]\*F[n-1]
+ [解題參考](https://sites.google.com/a/hpsh.co.cc/code/ti-mu/d887-1chain)
6.b062: 1. 城市道路連通網
+ DFS會TLE
+ i->j路徑長度為m的走法，為檢查所有中繼點k(i->k->j)。
亦即所有 i->k(直接連通) k->j(路徑長度m-1)的總和
7.d198: 00825 - Walking on the Safe Side
+ stringstream可能有問題？
+ dp[i][j]=dp[i-1][j]+dp[i][j-1];
8.c100: 00116 - Unidirectional TSP
+ 從右向左掃描，以解決要求輸出字典序最小的問題
9.f173: m6a1-作物種植(Plant)
+ [解題參考](https://tpmso.org/toi/wp-content/uploads/question/202006/Plant.odp)
:::
### (二) Maximum Consecutive Sum(MCS)
:::warning
1.a540: 10684 - The jackpot
$$
MCS(i)=
\begin{cases}
element[i], MCS(i-1)<0 \\[2ex]
element[i]+MCS(i-1),otherwise
\end{cases}
$$
2.d784: 一、連續元素的和
+ 類似a540
3.d206: 00108 - Maximum Sum
+ [O(n4)](http://chchwy.blogspot.tw/2008/11/acm108-maximum-sum-ac.html)
+ [O(n3)](http://hanting1225.blogspot.tw/2015/11/uva-108-maximum-sum.html)
4.b565: 5.採蘑菇攻略問題
5.b840. 104北二4.農作物採收問題
+ 2D 最大連續區間和
+ [解題參考](https://hackmd.io/@cyk/112/https%3A%2F%2Fhackmd.io%2F%40cyk%2Fdp#2D-%E6%9C%80%E5%A4%A7%E9%80%A3%E7%BA%8C%E5%8D%80%E9%96%93%E5%92%8C)
6.f162. 4. 獵人與斯芬克斯
+ 2D 最大連續區間和
:::
### (三) 零錢
+ [演算法筆記-Money Changing Problem](http://web.ntnu.edu.tw/~algo/KnapsackProblem.html#6)
:::warning
1.d904: 換零錢
+ [解題參考](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/d904)
2.d253: 00674 - Coin Change
+ [解題參考](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/d253-674---coin-change)
3.d289: 多元一次方程式
+ 數學解？
4.b232: TOI2009 第四題：分房子
+ 將1,3,5,7,9…視為幣值，n間房子視為金額
+ f(n)=f(n-1)+f(n-3)+f(n-5)…
:::
### (四) 01knapsack
+ [演算法筆記-Fractional Knapsack Problem](http://web.ntnu.edu.tw/~algo/KnapsackProblem.html#3)
:::warning
1.d637: 路過的鴨duck
+ F(n,w)為背包有前n樣物品，重量為w時的最大價值
$$
\begin{cases}
F(0,j)=0 \\[2ex]
F(i,j)=MAX(F(i-1,j-w[i]) + v[i], F(i-1,j) )
\end{cases}
$$
+ [解題參考](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/d637-duck)
2.a587: 祖靈好孝順
+ 二維 -> 一維
3.b184: 5. 裝貨櫃問題
+ 二維 -> 一維
4.b140: NOIP2005 3.採藥
5.b131: NOIP2006 2.开心的金明
+ [解題參考](https://sites.google.com/view/zsgititit/home/c-cheng-shi-she-ji/b131-noip2006-2-kai-xin-de-jin-ming)
6.a522: 12455 - Bars
7.f455: 詠竣的哀鳳12
6.d890: 3.禮物分配(gift)
+ 背包負重上限為所有禮物單價總和除以2
+ 物品重量與價值相同，取能放入背包的最大價值
7.d390: 00562 - Dividing coins
+ 同上
8.b116: TOI2008 3. 加減問題
+ 同上，問題可視為可否將N個正整數分成數值和相等的兩堆數字。
9.c147: 105北二5搬家規劃問題
+ ss.str("");
+ ss.clear();
+ stoi(str);
10.[TCFSH CIRC Judge d075: Q-6-10. 置物櫃出租 (APCS201810)](https://judge.tcirc.tw/ShowProblem?problemid=d075)
+ [解題參考](https://www.youtube.com/watch?v=0SNyjUl2t4A)
11.g278: 4. 美食博覽會
+ [解題參考](https://hackmd.io/@peienwu/APCS0904)
:::
### (五) LIS
+ [演算法筆記-LIS](http://web.ntnu.edu.tw/~algo/Subsequence.html)
:::warning
1.[TCFSH CIRC Judge d078: P-6-15. 一覽衆山小](https://judge.tcirc.tw/ShowProblem?problemid=d078)
2.d242: 00481 - What Goes Up
+ LIS(i)=MAX~1<=j<i~ ~&&~ ~element[j]<element[i]~ LIS(j)+1
+ 找出i之前所有比i小的元素j，LIS(i)即LIS(j)+1其中的最大值
+ 上述O(n2)的方法會TLE，要用O(nlog2n)的方法
+ [Robinson-Schensted-Knuth Algorithm](http://wiki.csie.ncku.edu.tw/acm/course/LIS)(只能求長度)
- EX：
$$
4 5 1 2 3 \qquad\qquad 4\,5→1\,5→1\,2→1\,2\,3\\
\,\,\,\,\,\,\,\,\,1 4 5 3 2 \qquad\qquad 1\,4→1\,4\,5→1\,3\,5→1\,2\,5
$$
3.f608: 4. 飛黃騰達
+ 將點依 x 座標排序後，對 y 座標求LIS。
+ 排序時 x 相等則比較 y，可以用 pair 來記錄點，預設即會這樣比較。
+ STL [vector(1)](https://larry850806.github.io/2016/06/06/STL1/) [(2)](http://wiki.csie.ncku.edu.tw/acm/course/Vector) [(3)]+ STL [sort、upper_bound](https://zrn-code.github.io/2020/07/23/algorithm/)
+ STL [pair](https://blog.csdn.net/sinat_35121480/article/details/54728594)
4.d052: 11456 - Trainsorting
+ [解題參考1](
http://par.cse.nsysu.edu.tw/~advprog/advprog2014/tip/11456.ppt)、[解題參考2](https://yuihuang.com/zj-d052/)
+ fill()
+ LIS+LDS
+ 接後面的車廂重量要越來越小即LDS，接前面的車廂重量要越來越大即LIS
+ 計算每個節點的LIS、LDS，相加-1(自己會重覆)的最大值
+ 序列要逆序儲存(Why？)
- LIS、LDS的最大值是記錄在序列最右的元素，但兩序列的接點卻是最左邊的元素
:::
### (六) LCS
+ [演算法筆記-LCS](http://web.ntnu.edu.tw/~algo/Subsequence2.html)
:::warning
1.c001: 10405 - Longest Common Subsequence
+ X陣列的index由0開始，長度i的元素為X[i-1]
+ LCS(0,j)=0 ，LCS(i,0)=0
$$
LCS(i,j)=
\begin{cases}
LCS(i-1,j-1)+1, if X[i]==Y[j] \\[2ex]
MAX(LCS(i-1,j), LCS(I,j-1)), otherwise
\end{cases}
$$
2.a133: 10066 - The Twin Towers
+ [解題參考](http://par.cse.nsysu.edu.tw/~advprog/advprog2013/tip/10066.ppt)
3.c499: ♋大耳神下麵真好吃♋
4.d674: 10192 - Vacation
5.d231: 97北縣賽-2-基因序列密碼問題
+ 記錄來源
6.a252: Another LCS
:::
### (七) 最小編輯距離（Minimum Edit Distance）
:::warning
1.f507: 1207 - AGTC
+ [解題參考](https://home.gamer.com.tw/artwork.php?sn=5019239)
2.e828: 3.猴子打字遊戲 (Typing)
+ [滾動陣列](https://www.geeksforgeeks.org/edit-distance-dp-5/)
:::
### (八) Largest Empty Rectangle
+ [演算法筆記-Largest Empty Interval](https://web.ntnu.edu.tw/~algo/MaximumSubarrayProblem.html)
:::warning
1.b123: 最大矩形 (Area)
+ 計算每列的面積，再往上找出能構成最大面積的高度
:::
### (九) 矩陣鏈乘積(Matrix Chain Multiplication)
:::warning
1.[TCFSH CIRC Judge d086: Q-6-18. 矩陣乘法鏈](https://judge.tcirc.tw/ShowProblem?problemid=d086)
2.c112: 00348 - Optimal Array Multiplication Sequence
+ [演算法筆記-DP](http://web.ntnu.edu.tw/~algo/DynamicProgramming.html#4)
+ [Backtracking](http://programming-study-notes.blogspot.com/2014/03/backtracking.html)
3.d652: 貪婪之糊
4.f817: TOI_y21m4_a03枯枝
+ dp[i][j] = dp[i][i] + min( max(dp[i+1][k], dp[k+1][j])，i+1 ≦ k < j)
:::
### (十) 區間DP
:::warning
1.d686: 10003 - Cutting Sticks
+ 計算類似矩陣鏈乘積，由2切點相鄰開始計算
+ [解題參考1](https://cloud.tencent.com/developer/article/1100098)
+ [解題參考2](http://www.itread01.com/content/1501765089.html)
:::
### (十一) 集合最優配對
:::warning
1.d879: 10911 - Forming Quiz teams
+ 利用二進位元存集合，[狀態壓縮(bitmask)](https://www.quora.com/What-is-bitmasking-What-kind-of-problems-can-be-solved-using-it)
+ d(S)表示把S中的元素兩兩配對的最小距離和，
dp(S)=min(任取兩點的距離|Pa, Pb | + dp(S - {a} – {b}) )
+ [解題參考1](http://par.cse.nsysu.edu.tw/~advprog/advprog2017/tip/10911.ppt)、[解題參考2](http://naivered.github.io/2016/09/16/Problem_Solving/UVa/UVa-10911-Forming-Quiz-Teams/)、[解題參考3](https://blog.csdn.net/u011345461/article/details/38037983)、[解題參考4](http://qu66q.iteye.com/blog/2098429)
:::
### (十二) 樹上DP
:::warning
1.h559. pC. 共享自行車 (bike)
+ [解題參考](https://hackmd.io/@cyk/2022-toi#C-%E5%85%B1%E4%BA%AB%E8%87%AA%E8%A1%8C%E8%BB%8A)
2.j248. 111北二7a.驛站換馬、郵政系統
+ [解題參考](https://hackmd.io/@cyk/2022-hc#7a-%E9%A9%9B%E7%AB%99%E6%8F%9B%E9%A6%AC%E3%80%81%E9%83%B5%E6%94%BF%E7%B3%BB%E7%B5%B1)
:::
## 十三、數學
+ [板橋高中校內培訓-中學數學](
https://docs.google.com/document/d/1XPeYYxMYlyXq5n9kOD9FNZcWpiF37jykvKtTB1Ts8XQ/edit#heading=h.5pvnicy44wm8)
+ [板橋高中校內培訓-數學](
https://docs.google.com/document/d/15BdaOYpGJyqFOpidHB4GVNGmTOCb7-TFj630HeUfhyI/edit#heading=h.e1iwh4n9reau)
### (一) 雜項
:::warning
1.d111: 10110 - Light, more light
+ n的因數如果是奇數個，燈就會是亮的
+ 一個數會等於成對的因數相乘，完全平方數的因數個數為奇數
2.d361: 10515 - Power et al.
+ 將2^n^~9^n^的最後一個數字列表，會發現規律，最長的循環周期為4
+ [解題參考](http://www.cnblogs.com/xiong-/p/3218741.html)
3.a858: 數三角形
+ 正算 v.s. 反算
4.a241: 第二題：1 / x 是有限小數
+ x的因數只能為為2或5
+ 若用x是否能被2、5除盡的方式檢查，會TLE
+ 改進方式1：採用位元運算子x%2、x/=2 -> x&1、x>>=1
+ 改進方式2：建表查詢
5.b897: 10219 - Find the ways !
+ 直接計算n!會爆掉
+ 可用floor(log10(n))+1判斷n是幾位數
+ log10(1\*2\*3)= log10(1) + log10(2) + log10(3)
+ [解題參考](https://tausiq.wordpress.com/2010/08/31/uva-10219-find-the-ways/)
:::
### (二) 大數
:::warning
1.c034: 00424 - Integer Inquiry
+ 大數加法
2.c119: 10220 - I Love Big Numbers
+ 大數乘法
3.a884: 11448 - Crisis
+ 大數減法
:::
### (三) 數論
:::warning
1.d256: 11388 - GCD LCM
+ a、b是最大公因數的倍數，所以最小的a就是gcd(a,b)
+ lcm(a,b)=a*b/gcd(a,b)，a為最大公因數，則b為最小公倍數
+ 最小公倍數(G)是最大公因數(L)的倍數，所以G%L!=0則輸出 -1
2.a007: 判斷質數
+ 單純埃拉托斯特尼篩法建質數表(取質數將其倍數們篩掉)還是會TLE
+ 埃拉托斯特尼篩法建質數表，只要判別小於等於根號此數的質數是否為其因數即可
3.d362: 10394 - Twin Primes
+ 以埃拉托斯特尼篩法建質數表，並同時找出所有的Twin Primes
4.b467: NOIP2013 Day1.1.转圈游戏
+ 快速冪
+ [解題參考](https://blog.csdn.net/McDonnell_Douglas/article/details/72784052)
5.a289: Modular Multiplicative Inverse Extended Euclidean Algorithm
+ [解題參考1](https://www.youtube.com/watch?v=mgvA3z-vOzc)、[解題參考2](http://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/)、[解題參考3](http://www.geeksforgeeks.org/basic-and-extended-euclidean-algorithms/)
6.d440: 10299 - Relatives Euler's Totient Function
+ [解題參考1](http://kos74185foracm.blogspot.tw/2011/07/10299-relatives.html)、[解題參考2](http://www.aichengxu.com/view/924080)、[解題參考3](http://blog.csdn.net/mobius_strip/article/details/40338831)
7.e902: 昴的交響樂
+ 模逆元
8.b429: 離散對數
:::
### (四) 機率
:::warning
1.e162: 01636 - Headshot
:::
### (五) 矩陣
:::warning
1.a410: 解方程
+ [克拉瑪公式](
http://math1.ck.tp.edu.tw/陳嘯虎/小虎/95課綱/第五冊/重點/95課綱5-2-3矩陣-行列式與克拉瑪公式.pdf)
2.a272: 猥瑣罐頭下樓梯
+ 矩陣快速求線性遞迴
+ [矩陣快速冪加速](https://zerojudge.tw/ShowThread?postid=11099&reply=0)
3.d639: 企鵝村三兄弟penguin
+ 矩陣快速求線性遞迴
+ [矩陣快速冪加速](https://zerojudge.tw/ShowThread?postid=10974&reply=0)
4.e811: 3. 密碼產生器 (Password)
+ 矩陣建構
+ 矩陣快速冪
:::
<br/>
## 十四、計算幾何
+ [板橋高中校內培訓-計算幾何](https://docs.google.com/document/d/1Xi3LPnAvCOLXHX_h9Vk_Fr74Dy-_Dtn1jKypCQkEvJc/edit)
+ [資訊之芽-計算幾何](https://www.csie.ntu.edu.tw/~sprout/algo2016/ppt_pdf/computational_geometry.pdf)
:::warning
1.d055: 11437 - Triangle Fun
+ [解題參考](http://blog.csdn.net/freezhanacmore/article/details/8171942)
2.d170: 飛蛾撲火(一)
+ [向量內積、外積](https://web.ntnu.edu.tw/~49440326/T3260b/T3260b.htm)
:::
## 十五、進階資料結構
:::warning
1.d788: 排名順序
+ [Binary Indexed Tree 樹狀數組](https://yuihuang.com/binary-indexed-tree/)
+ [Binary Indexed Tree](https://www.csie.ntu.edu.tw/~sprout/algo2016/homework/week11.pdf)
+ [树状数组（Binary Indexed Tree），看这一篇就够了](https://blog.csdn.net/Yaokai_AssultMaster/article/details/79492190)
+ [模板-Binary Indexed Tree](https://psychicalcoder.github.io/2017/03/11/binaryindexedtree/)
+ [BIT 說明1](http://slides.com/sylveon/2017wds#/1/14)、[說明2](https://slides.com/sylveon/cp2019-spring#/6)
2.f315: 4. 低地距離
+ BIT
3.d794: 世界排名
+ BIT
+ 離散化
4.d847: 2D rank finding problem
+ 二維BIT
+ [解題參考](https://yuihuang.com/zj-d847/)
5.d539: 區間 MAX
+ [RMQ](http://blog.csdn.net/emailed/article/details/4761806)
+ Sparse Table
- [Sparse Table1](https://www.youtube.com/watch?v=c5O7E_PDO4U)
- [Sparse Table2](http://www.cppblog.com/jackdongy/archive/2012/12/17/196369.html)
- [Sparse Table3](http://www.cnblogs.com/five20/p/7531644.html)
- [Sparse Table4](http://blog.csdn.net/qq_34594236/article/details/53912731)
+ [Segment Tree 線段樹](https://yuihuang.com/segment-tree/)(邏輯腦P.172)
- [線段樹](http://www.cnblogs.com/TenosDoIt/p/3453089.htm)
- [說明](https://slides.com/sylveon/cp2019-spring#/7)
- 進階：d799 区间求和
- [線段樹+懶惰標記1](https://www.smwenku.com/a/5b9ed6502b71773ebacea120/zh-cn/)
- [線段樹+懶惰標記2](https://hk.saowen.com/a/9f18526a9bd9ccd865b10744d4584c83157747692bb7965edb4af7f1e376518b)
6.b687: 7. 坐好坐滿
+ Sparse Table
7.c424: pC 框架區間
+ 建Sparse Table，窮舉數列任兩數，只要兩數值差==序號差且，左數為區間最小值，右數為區間最大值即是一解
:::
Sign in with Wallet
Connect another wallet