###### tags: `選修` # APCS(大學程式設計先修檢測)程式實作 :::success ### 零、評量、C++語法參考網站、相關網站 ::: ### 1. 評量方式 + 上課基本練習 40% + 作業解題數(ZJ共通過(AC)題數) 20% - 本課程是為了考APCS，檢定的難度會比上課更難，不願意自主練習是沒機會到3級(約能完整解出2題)以上。 - 作業題目選擇 * 可從題單裏沒教過的題目選擇，或任選其它題目都可。 * 不會的可以去參考網路上的程式碼、解法。 * 同學也可以互相討論，而且是鼓勵的。 * 不論如何，都要在了解解法後，不看別人的程式碼，自己親自寫一遍。 * 不要為了分數直接貼別人的程式碼，那是無意義的行為，上機考你就會現出原形。 * 題數登記時間：上機考當週。 * 成績計算方式：作業不批改，以上機考檢核作業是否抄襲。 ```c 原始作業成績=min(題數*4,120) // 上限120 if(原始作業成績>=100) // 認真的同學可以有一點失誤的空間，例如原始作業120分，上機考 80分，作業成績實得 96分。 作業成績=原始作業成績*(上機考成績/100) else if(上機考成績>=原始作業成績) 作業成績=原始作業成績 // 老師承認你的作業是自己做的，例如原始作業 80分，上機考100分，作業成績實得 80分。 else if(上機考成績<原始作業成績) 作業成績=上機考成績 // 老師不承認作業是你自己做的，例如原始作業 80分，上機考 30分，作業成績實得 30分。 ``` + 期中上機考 20% - 時間約第1、2次期中考中間。 - 上機考時網路會切斷，無任何其它參考資料可看。 - 每單元請至少練習一半題目，熟練基本語法。 - 因為課程的目的是要考APCS，上機考會比較難，也會算分(資概的上機考只是基本語法檢核，不算分)。 + 期末作業解題報告 20% - 上機考考差的同學請保握最後的機會。 - 10~12題。 * 每寫一題10分，上限120分(12題)。 * 期中考之前的舊範圍(上學期：四、陣列之前。下學期：STL 演算法之前)，最多只能放3題。 * 其餘的必須是新範圍(上學期：五、字串之後。下學期：STL vector之後)新寫的題目，每個單元至多可放3題(不可以都寫同一單元的題目)。 - 每題的子標題為 (1) 單元、題號、題目、題目簡述 (2) 解題動態、評分結果截圖 (3) 解題思路 (4) 程式碼 (5) 反思(遇到的錯誤、修正的地方、更好的方法…) (6) 錯誤程式碼 - 檢核方式 * 請儘量放一開始有錯，然後修正的題目。如果你每一題都是一次AC，那你應該是骨骼清奇、萬中無一的練武奇才，應該不用怕老師的檢核吧。 * 有交期末作業解題報告者，會請你在沒有網路的狀態下重寫一題當做檢核(題目由老師挑選)，寫不出來作業直接作廢0分，所以作業請務必自思考己完成，如果你只想上網找程式複製貼上賺分數，就不用做這種白工了。 - 可放到學習歷程檔案。 ### 2. [TOI推廣計畫-線上練習賽](https://toi-reg.csie.ntnu.edu.tw/) + 成績計算 - 新手組：分數/300直接加在總成績。 - 潛力組：分數/100直接加在總成績。 + 上學期10、11、12月，下學期3、4、5月，最後一週。 + 星期一08:00 ～ 星期五20:00。90分鐘。 + [證書](https://drive.google.com/open?id=1DcgDKn1R33kOPc_HazdIyQDgyYxSCPlZ) ### 3. 學習歷程檔案(修課記錄、課程學習成果)(Bonus) + [作伙學：課程學習成果作品呈現建議](https://www.108epo.com/results-detail.php?Key=23) + [大學選才與高中育才輔助系統](https://collego.edu.tw/) + [大學申請入學參採高中學習歷程資料完整版查詢系統(大學招生委員會聯合會)](https://www.cac.edu.tw/cacportal/jbcrc/LearningPortfolios_MultiQuery_ppa/index.php) + 最後一週上課結束前如果認證完成，學期總成績加分。 + 上傳的PDF大小限制為2MB，圖片如果太大，可用小畫家將解析度調小。 + HackMD筆記可下載成HTML(選單／下載 / HTML)，再以[PDF24 Tools](https://tools.pdf24.org/zh/)轉成PDF。如果要將PDF插入到Word中，可用同一網站將PDF轉圖像再插入。 + [Canva線上設計](https://www.canva.com/zh_tw/) ### 5. APCS + 實作級分*2，直接加在總成績。5級分者學期成績直接滿分。 + [APCS官網](https://apcs.csie.ntnu.edu.tw/) + [採計成績大學校系](https://apcs.csie.ntnu.edu.tw/index.php/apcs-introduction/gradeschool/) + [個人申請-校系分則查詢](https://www.cac.edu.tw/apply108/query.php) + 檢測日期：每年1、6、10月 + [檢測內容](https://apcs.csie.ntnu.edu.tw/index.php/info/) + 觀念題 - [評量架構](https://apcs.csie.ntnu.edu.tw/index.php/questionstypes/) - [c subset](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2018/12/C-subsetGuidelineV1.0.pdf) - [CodeBlocks除錯](http://jiannrong.blogspot.com/2014/06/codeblocks-debug.html)、 [如何使用 CodeBlocks 的 Debugger](https://www.youtube.com/watch?v=HghfCpOcfF0) * EX：2016-10-29(4、9、12、23、5、20、18、24) - 題目解析 * [20160305](http://yhhuang1966.blogspot.com/2017/09/apcs-2016.html) * [20161029](http://yhhuang1966.blogspot.com/2017/10/apcs-105-10.html) * [題目分類](https://hackmd.io/@h3BSPiUpQhCVyCHgJAWWHg/HypYLEPtQ?type=view) + [檢測系統環境](https://apcs.csie.ntnu.edu.tw/index.php/info/environment/) + [檢測作答系統說明](https://apcs.csie.ntnu.edu.tw/index.php/info/systemdescription/) + [學習資源](https://apcs.csie.ntnu.edu.tw/index.php/apcs-introduction/websites/) + [歷次試題](https://yuihuang.com/apcs/) - [201906](https://miohitokiri5474.github.io/code/APCS-19-06/) - [201910](https://hackmd.io/@wiwiho/HJwOGYb5r) - [202001](https://hackmd.io/@joylintp/APCS20200105) - [202007](https://hackmd.io/@emanlaicepsa/APCS202007) - [202010](https://hackmd.io/@cthbst/APCS_10910) - [202101](https://akr.tw/tag/7) + [APCS對升學的效益(愷哥電腦科普-高中生該怎麼準備學習歷程)](https://www.youtube.com/watch?v=ooNgyQRDO4E) + [APCS課程(已參加過APCS檢測，且實作題為2級分或3級分之高中職學生)](https://apcs.csie.ntnu.edu.tw/index.php/apcsclass/) + [成績單](https://drive.google.com/file/d/1t_2zLXhcibQ6oHtZZBf64AyUq-bzudPN/view?usp=sharing) ### 6. 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) - 0~1:04:00 競程介紹 - 1:04:00~ 2:31:00 遞迴、排序、搜尋、佇列、堆疊 - 2:31:00~4:24:00 休息 - 4:25:30~5:27:30 滑動視窗、greedy、分治 - 5:40:00~6:28:30 DP - 6:40:00~7:05:20 圖論演算法綱要、樹上演算法綱要、其它競技程式綱要 + [APCS實作題的內容(50:00)](https://www.youtube.com/watch?v=gMsg559nUo0#t=50m) ![](https://i.imgur.com/tkEB5Su.jpg) ### 7. 軟體 + [Code::Blocks](http://cs.cysh.cy.edu.tw/software/software_download.html) + [Dev-C++](http://cs.cysh.cy.edu.tw/software/software_download.html) + [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)) + [GDB online Debugger | Compiler - Code, Compile, Run, Debug online C, C++](https://www.onlinegdb.com/) + [The collaborative browser based IDE - Replit](https://replit.com/) ### 8. 面試線上題庫 + [LeetCode](https://leetcode.com/) + [HackerRank](https://www.hackerrank.com/) <br/> :::success ### 壹、TOI 線上練習賽 新手組考式範圍 ::: ## 一、變數與運算子 :::info EX_1_1:a001: 哈囉 ::: :::info EX_1_2:d060: 還要等多久啊？ + 3元運算子 + 多元解法 (85-m)%60 ::: :::info EX_1_3:d485: 我愛偶數 + % + 複合指定運算子 + 將a,b調整成偶數(a如果是奇數+1,b如果是奇數-1)，計算2個偶數間的偶數 ::: :::info EX_1_4:b004: 繩子上吃草的牛 + while(cin >> D >> L) + const + acos(0)、sqrt()，需含入 cmath + 半長軸：L/2，半短軸：sqrt((L/2\*L/2)-(D/2\*D/2))，橢圓面積：pi\*半長軸\*半短軸 + Q：int D,L？ + 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 + 邊界可不計代表除不盡可捨棄 + 輸入的第一行有一個整數t，代表測試筆數 ```c int t; cin >> t; while(t>0) { .... t--; } 或 while(t--) { .... } ``` ::: :::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.d489: 伏林的三角地 + 海龍公式計算三角形面積 + s=(a+b+c)/2 + $area=\sqrt{(s(s-a)(s-b)(s-c))}$ 7.d827: 買鉛筆 + /、\%、(( )) + n/12*50+(n-(n/12)*12)*5 8.d277: 矩陣對角線 + 3元運算子、% + 對角線奇數可共用對角線交叉的花盆，偶數不共用 9.b681: 1. 山洞探險 + 3元運算子 + 向北公式為2L-1，向南為？ + long long int 10.d127: 二、牧場面積 + 接近正方型面積會最大 + long long int 11.d461: 班際籃球賽 12.d096: 00913 - Joana and the Odd Numbers + long long int + 有N個奇數為第(N+1)/2列 + 找出此列最後3個數字與第(N+1)/2列的關係 13.d051: 糟糕，我發燒了！ + 浮點數(float、double) + setprecision 控制輸出數值的「位數」，需含入 iomanip 標頭檔 + 只控制「小數點後的位數」fixed + 型別轉換 14.c776: 106北二1.六邊形屋瓦 + 扣掉重覆的白色屋瓦。公式？ 15.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: 三人行必有我師 + && ::: :::info EX_2_2:e283: APCS 類似題 - 小崴的特殊編碼 + 多項選擇 + C++ I/O加速 - [說明1](http://chino.taipei/note-2016-0311C-的輸出入cin-cout和scanf-printf誰比較快？/) - [說明2](http://slides.com/sylveon/i2a-19#/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; // 自行測試時中途會看不到答案 } } ``` ::: :::info EX_2_3:a004: 文文的求婚 + || + 閏年為可被4整除且不被100整除，或可被400整除 + [C語言:運算子優先次序和運算次序](http://magicjackting.pixnet.net/blog/post/70902861-c-語言:運算子優先次序和運算次序) :::   :::warning 1.d064: ㄑㄧˊ 數？ + 比較運算子 + ==(等於) + !=(不等於) 2.a012: 10055 - Hashmat the Brave Warrior 3.d058: BASIC 的 SGN 函數 + 巢狀if + 比較運算子 > >= < <= == != 4.d066: 上學去吧！ + 巢狀if + 亦可將時化為分 5.a006 一元二次方程式 + sqrt()，需含入 cmath 標頭檔 + printf，需含入 cstdio 標頭檔 + [printf-引數說明](https://openhome.cc/Gossip/CGossip/PrintfScanf.html) 6.a053: Sagit's 計分程式 + 多項選擇 7.d460: 山六九之旅 + 多項選擇 8.a273: 小朋友下樓梯 + 小心n或k等於0的情形 9.b186: 97七區資訊學科1(改編) + 取餅乾/10，蛋糕/2中小的數即是贈送的盒數 + 測資會有0 0 0 10.a005: Eva 的回家作業 + 判斷等差或等比數列，求第5項 + while(t\-\-) 11.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時結束。 12.d984: 棄保效應 + &&、|| + 運算子優先順序 + unsigned int + a>b+c(a最大) 或 c>a>b(棄b保a) 或 b>a>c(棄c保a) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c>a && a>b && a+b>c 13.g275: 1. 七言對聯 14.b899: 2. 物品探測 + 分別計算三點間的距離，最長的為正方形的對角線。 + 正方形四點 A、B、C、D，假設 A、C 為對角，則 D = A + C - B 15.d095: 00579 - ClockHands + 分別計算時針與分針相對於12點的角度再相減 + fabs()可求浮點數的絕對值，需含入 cmath 標頭檔 ``` c char colon; //設一個字元變數，把冒號讀掉 while( cin >> h >> colon >> m && !(h == 0 && m == 0) ) ``` 16.c461: apcs 邏輯運算子(Logic Operators) + 位元運算子&(AND)、|(OR)、(^)XOR + 將a、b以位元運算子運算後和c比較 17.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.藏寶問題 + 型別轉換 + 複合指定運算子 + 每筆測資變數歸零 ::: :::info EX_3_2:a024: 最大公因數(GCD) + 暴力法(i++ v.s. 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)) + 除錯練習 (1) 設中斷點 (2) Debug (F8) (3) Debugging windows/Watches (4) Next line (F7) (5) Stop debugger ::: :::info EX_3_3:a215: 明明愛數數 + do_while迴圈 ::: :::info EX_3_4:c418: Bert的三角形 (1) EX_3_5:c419: Bert的三角形 (2) + 巢狀迴圈(內外圈變數不能重複) ::: :::info EX_3_6: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://emiliatancoding.blogspot.com/2019/02/b003.html) ::: :::warning 1.d498: 我不說髒話 + for迴圈 2.d490: 我也愛偶數 + for + i=i+1(i++) + 變數初值，區塊變數 v.s. 區域變數 3.d074: 電腦教室 + for、if 4.c022: 10783 - Odd Sum + 累加 5.d356: NOIP2002 1.级数求和 + 型別轉換 + 浮點數誤差(float->double) 6.a147: Print it all + break + continue 7.d010: 盈數、虧數和完全數 + 將因數累加 8.c299: 1. 連號或不連號 + 輸入數列時，找出其最大和最小值(可使用if或max、min函式) + 最大-最小+1==n，表示這個數列是連續的 9.d186: 11461 - Square Numbers + 完全平方數的判定 10.e622: 虛擬寵物大師 (Master) + 計算寵物成長後最終CP值，記錄最大值。 11.a038: 數字翻轉 + while + 不斷取個位數加入翻轉數字 12.a536: 11689 - Soda Surpler + 每次換的汽水又可再變成空瓶子拿去換 + 可以換的汽水數量=所有空瓶數/c + 手上空瓶=所有空瓶數/c+所有空瓶數%c 13.d189: 11150 - Cola + 不論開始有幾瓶，最後的剩餘狀況都只1瓶或2瓶 14.d122: Oh! My Zero!! + 0的數量為2和5因數個數的較小值，對n!來說2的因數個數一定會比5多 15.a149: 乘乘樂 + 運算子優先順序 sum=sum*(n%10) + 複合指定運算子 16.c561: Bert 愛搗蛋 + 將數值反轉的方法，假設 a為原數值，rvs為反轉後的數值(預設值為 0) rvs=rvs*10+(a%10); a/=10; // 讓個位數消失 17.d660: 11764 - Jumping Mario + prev=now 18.c420: Bert的三角形 (3) + 巢狀迴圈 19.f063: The Strongest Chain + 巢狀迴圈 20.c013: 00488-Triangle Wave + 巢狀迴圈 + 下半部 for(k=A-1;k>0;k\-\-) ::: ## 四、陣列 :::info EX_4_1:d212: 東東爬階梯 + 一維陣列 + DP + [費式數列](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97)，[前100項](https://wywu.pixnet.net/blog/post/26512033) ::: :::info EX_4_2:d478: 共同的數 - 簡易版 + 依序比較兩數列 + [C++ I/O加速](http://chino.taipei/note-2016-0311C-的輸出入cin-cout和scanf-printf誰比較快？/) ::: :::info EX_4_3:f579: 1. 購物車 + 商品編號為陣列的索引值 ::: :::info EX_4_4:f606: 2. 流量 + 二維陣列 + 同城市的伺服器流量要合併計算費用，所以預處理先將伺服器流量加總到它所在城市編號那一列。 + 計算花費時，i==j 代表伺服器在那個城市。 + [整數最大值可用0x3f3f3f3f](https://blog.csdn.net/jiange_zh/article/details/50198097) + memset將陣列歸零，memset(a, 0, sizeof(a)); 需含入 cstring 標頭檔 ::: :::info EX_4_5:d596: 1. 猜九宮格裡的地雷 + 因為只有9個格子，且每個格子只有4個相鄰格子，所以以二維陣列記錄每個格子其相鄰格子的編號最簡單 + 以一維陣列記錄格子編號是否有地雷(bool) + 「與地雷相鄰格子」的4個鄰居都可能是地雷 + 「與地雷不相鄰格子」的4個鄰居都不是地雷 ::: :::warning 1.b138: NOIP2005 1.陶陶摘苹果 2.b127: 會議中心（Room） + 費式數列 3.c067: Box of Bricks + 一維陣列 4.a034: 二進位制轉換 + 餘數輸出由下而上倒序寫 for(int j=i-1;j>=0;j\-\-) 5.a240: 第一題：1 / 17 小數第 n 位 6.a020: 身份證檢驗 + 以陣列將英文代號轉為數字 7.b139: NOIP2005 2.校门外的树 8.d097: 10038 - Jolly Jumpers + 宣告一個記錄差的陣列d(初值為0)，若兩數的差為3，則d[3]=1 + 輸入結束後，如果d[1~n-1]有0，則不是jolly jumper 9.d563: 等值首尾和 + 以迴圈讓prefix由前往後加，suffix由後往前加 + 如果prefix(前段和)==suffix(後段和)則答案加1，同時往前、後各加一個元素 + 如果prefix<suffix，則prefix往後加一個元素 + 如果prefix>suffix，則suffix往前加一個元素 10.a040: 阿姆斯壯數 + pow(x,y)計算xy，需含入 cmath 標頭檔 + 以迴圈和%求n位數整數的個位、十位…，放入陣列，並計算n + 再以迴圈將所有位數的n次方加起來，判斷是否等於此整數 11.d123: 11063 - B2-Sequence + 宣告一個記錄兩數和是否存在的陣列s(初值為0) + 以兩數和當成index，如果不存在，則s[兩數和]=1 12.d424: 00105 - The Skyline Problem + 使用陣列紀錄每個x軸座標上的最高高度 + 輸出時注意邊界 13.c435: MAX ! MAX ! MAX ! + 爆力解會TLE + 往後掃描時不斷記錄最大範圍答案和最大值(一層迴圈完成) + [解題參考](https://alan23273850.github.io/Online-Judge-Problems/zerojudge/c435MAX-MAX-MAX-/) 14.a693: 吞食天地 + 每次都重算會TLE + S[-1]陣列除錯 15.a015: 矩陣的翻轉 + 二維陣列 16.d481: 矩陣乘法 + 二維陣列 17.a694: 吞食天地二 + 二維陣列 + [C++ I/O加速](http://chino.taipei/note-2016-0311C-的輸出入cin-cout和scanf-printf誰比較快？/) 18.a417: 螺旋矩陣 + 二維陣列 + memset將陣列歸零，memset(a, 0, sizeof(a)); 需含入 cstring 標頭檔 + 逆時針即順時針的轉置矩陣 19.b965: 第 2 題 矩陣轉換 + 二維陣列 + 旋轉座標轉換 ![](https://i.imgur.com/dRW9LxQ.jpg =300x) 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。 20.a291: nAnB problem + 使用陣列紀錄是否比較過 + 使用 scanf 和 printf 才不會TLE 21.e287: 機器人的路徑 22.g276: 2. 魔王迷宮 ::: ## 五、字串(字元陣列) + [演算法筆記-字串](https://archive.is/u1lQL) :::info EX_5_1:a149: 乘乘樂 + 改寫為以字元陣列方式讀入 + 字串結束符號 '\0' ::: :::info EX_5_2:a782: 4. Redundant Acronym Syndrome Syndrome + 不能使用cin >> s + cin.getline(s,1000) + getline(cin,s) + toupper()將字元變大寫 + C 需用strcmp()比較兩字串是否相等，陣列的名字代表陣列開始的位址，s=="END"的寫法，即使s為"END"也不會相等。C++ string 可直接用==比較 ::: :::info EX_5_3:a011: 00494 - Kindergarten Counting Game + 不能只算空的數量，字母的前一個是非字母即一個字 + 不能使用cin >> s + getline(cin,s) + isalpha() ::: :::info EX_5_4: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) ::: :::info EX_5_5:a130: 12015 - Google is Feeling Lucky + 找最大值 + struct + printf()，需含入 cstdio 標頭檔 ::: :::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.a054: 電話客服中心 + 注意100000000答案為KLY 6.a065: 提款卡密碼 + abs()可求絕對值，需含入 cstdlib 標頭檔 7.d235: Q10929:You can say 11 + 11的倍數判別法：奇數位數字和與偶數位數字和相差為11的倍數 8.a224: 明明愛明明 + 統計每個字母出現的次數 + 迴文的條件為：只有一個字母出現的次數是奇數或全部都是偶數 + 每筆測資統計的陣列要歸零 + isalpha()判斷字元是否為英文字母 + toupper()將字元變大寫 9.d430: 第二題: 計算字數 (count) + islpha()、isdigit()、isalnum() 10.c440: Bert Love QQ ! + [解題參考](https://naukri7707.github.io/%E7%B7%9A%E4%B8%8A%E8%A7%A3%E9%A1%8C/ZeroJudge/c440/) 11.f291: 試算表大小 + 將輸入字串的字母轉成整數(26進位)，A為1，B為2，…，AA為27，AA為28，…。 + [substr](https://crmne0707.pixnet.net/blog/post/316362030-c%2B%2B-%E5%AD%90%E5%AD%97%E4%B8%B2-substring) + [stoi](https://tw511.com/a/01/11129.html) + isdigit() 12.d614: 簡易加法運算 + 讀入測試筆數T後，需以getline(cin,str)將T後的換行字元讀掉，或cin.ignore() + 以cin.getline()或getline(cin,str)，讀入一行 + isdigit()判斷字元是否為數字 + 如果是數字，減48(0的ascii)得到數值，加前一個數字*10 + 如果不是數字，答案加上目前已經造出來的數字。 13.a865: 5. Greek Numerals + 將26個字母對應的值儲存為陣列 + #、$、3為多的字母 14.d275: 11586 - Train Tracks + 只要M和F數量一樣且軌道一個以上即可 + cin.ignore() 15.c459: 2. 自戀數 + 可將N以字元陣列讀入 + strlen(N)計算其長度 + 數字字元-'0'求其數值 + pow(a,b)計算a^b^，需含入 cmath 標頭檔 + 根據進位制求出數值大小及每位數字的d次方合，比較是否相等 16.d103: NOIP 2008 1.ISBN号码 + 數字字元-'0'求得其數值 + 計算識別碼，如果等於最後一個數字，或餘10且最後一個字元為'X'，則為正確 17.d086: 態度之重要的證明 + toupper()將字元變大寫或tolower()將字元變小寫 + A的ASCII值為65，a的ASCII值為97 18.a275: 字串變變變 + 使用陣列儲存兩字串各別字母出現的次數(以字母的ascii為陣列索引) + 如果各別字母出現次數一樣，表示可經由調整順序後，讓兩字串一樣 19.d267: 11577 - Letter Frequency + cin.ignore()把數字後的換行字元讀掉 + isalpha()判斷字元是否為英文字母 + tolower()將字元變小寫 + 以字母的ascii為陣列索引記錄出現次數，迴圈找出頻率最高的次數，迴圈印出頻率最高的字母 20.d671: 11716 - Digital Fortress + cin.ignore()把數字後的換行字元讀掉 21.c462: apcs 交錯字串 (Alternating Strings) + 找出每一個連續大(小)寫片段的長度並將其記錄在陣列 22.e294: APCS 類似題 - 小崴的新發現 + 找下一個完全奇數的方法：從左往右找到某位數為偶數，把此位數加1，此位數之後的數都設為1 + 找前一個完全奇數的方法：從左往右找到某位數為偶數，把此位數減1(偶數可能為0，要處理向前借位的問題)，此位數之後的數都設為9 + atoll()將C字元陣列轉成long long + s.c_str()將C++ string轉成C字元陣列 ::: ## 六、函式(遞迴) :::info EX_6_1:d171: 飛蛾撲火(二) + 內建函式：pow、log10、floor + logN^M^ = M*logN ::: :::info EX_6_2:c039: 00100 - The 3n + 1 problem + 自訂函式(先練習寫pow(n,m)) + 內建函式：swap、max、min ::: :::info EX_6_3:a216: 數數愛明明 + 遞迴(先印出費式數列) + long long int + TLE(遞迴求一般項) ::: :::info EX_6_4:f637: DF-expression + 遞迴 + [解題參考](https://yuihuang.com/nuts-apcs1071027-3/) ::: :::warning 1.d658: 11636 - Hello World! + 以log2()求N為2的幾次方 + 以ceil()無條件進位 2.f044: 2. 史萊姆生態區 (Slime) + log2() 3.c294: APCS-2016-1029-1三角形辨別 + 自定交換函式swap(傳參考呼叫)(除錯Step into) + 使用swap讓a,b,c依小->大排序(c為最長邊) 4.a121: 質數又來囉 + 1不是質數 5.b112: 5.高中運動會 + 多個數的最大公因數 6.d237: 質數合 + 以質數函式測試是否需加此數 + 不可直接輸出142913828922 7.d117: 10924 - Prime Words + 以質數函式測試字母值總合 8.a623: Combination + 將n!寫成函式，在主程式呼叫3次 9.d255: 11417 - GCD + 將gcd寫成函式 10.c813: 11332 - Summing Digits + 將f(x)寫成函式，不斷呼叫了式，直到n為個位數 11.c015: 10018 - Reverse and Add + 將數字反轉寫成函式 + 迴文的檢查為數字反轉後和原數字相等即是 12.a263: 日期差幾天 + 判斷閏年可寫成函式 + 可算出總天數再相減 13.a227: 三龍杯 -> 河內之塔 + 遞迴 + scanf()、printf() 需含入 cstdio 標頭檔 + [河內塔|樂和遊戲](http://www.novelgames.com/zh-HK/tower/) + [河內塔程式參考](http://notepad.yehyeh.net/Content/DS/CH02/4.php) 14.c002: 10696 - f91 + 遞迴 15.d693: 最小公倍數 + n個數的公倍數可以從兩兩連續求公倍數得到 + long long int + 以遞迴求gcd 16.f638: 支點切割 + 遞迴 + 前綴和、後綴和 + [解題參考](https://yuihuang.com/zj-f638/) 17.f640: 合成函數 + 遞迴 + stringstream + 或用堆疊反向處理 18.d269: 11579 - Triangle Trouble + 排序後找連續3個邊，可構成最大三角形 + [更快的排序演算法 quick sort1](https://kopu.chat/2017/08/03/快速排序-quick-sort/) + [quick sort2](http://www.algolist.net/Algorithms/Sorting/Quicksort) ::: <br/> :::success ### 貳、TOI 線上練習賽 潛力組考式範圍 ::: ## 一、物件導向簡介 + 封裝(私有型態) + 繼承(保護型態) ## 二、stringstream + [StringStream－int和sting轉換的另一種方案與清空StringStream](https://dotblogs.com.tw/v6610688/2013/11/08/cplusplus_stringstream_int_and_string_convert_and_clear) :::info EX_2_1:d392: 读取练习——强大的加法！ + stringstream字串轉數字 ::: :::info EX_2_2:d574: 節約符咒 + stringstream數字轉字串 + string字串相加 + 每次都開新的stringstream會TLE + ss.str(""); + ss.clear(); + ss.str()、ss.str().size() ::: :::warning 1.a158: 11827 - Maximum GCD + 數字數量不定以stringstream拆解放入陣列，巢狀迴圈求兩數的GCD + __gcd(a,b)可求a、b兩數的GCD，需含入 algorithm 標頭檔 2.d098: Stringstream運用練習(C++) + stringstream字串數字轉換 + str.length() + isdigit() + getline() + atoi() + string.c_str() 3.d018: 字串讀取練習 4.d672: 10922 - 2 the 9s + 遞迴 + string.c_str() ::: ## 三、C++ STL + [STL參考文件](https://tioj.ck.tp.edu.tw/uploads/attachment/11/40/1.pdf) + [[C++] STL 容器 (一) - 基本介紹](http://larry850806.github.io/2016/06/06/STL1/) + [[C++] STL 容器 (二) - Iterator](http://larry850806.github.io/2016/06/06/STL2/) ### (一) 演算法 :::info EX_3_1_1:a225: 明明愛排列 + 陣列名為指標說明 + [常用C++ algorithm：sort](https://yuihuang.com/cpp-algorithm-sort/) + 自訂比較函式(小到大排列時，如果左邊元素<右邊元素，回傳true) + 大到小排列比較函式可用greater<int>() ::: :::info EX_3_1_2:a362: 1. 搬雕像 + sort + 自訂比較函式 + struct + 排序後的位置-原來的位置編號 ::: :::info EX_3_1_3:a524: 手機之謎 + [next_permutation](https://blog.tenyi.com/2007/08/stlnextpermutation.html) + [常用C++ algorithm：next_permutation](https://yuihuang.com/cpp-algorithm-next-permutation/) + [常用C++ algorithm: reverse](https://yuihuang.com/cpp-algorithm-reverse/) + 如果要產生所有排序，陣列需小到大排序 ::: :::info EX_3_1_4:b582: 一個窩 + [nth_element](https://www.itread01.com/content/1543482306.html)，使第n大的元素置於n的位置。用 sort 亦可，但如果測資更大會TLE。 + c++ I/O加速 + 開一個1000000的全域變數陣列，用 vector 會 TLE。 ::: :::warning 1.a251: 假費波那契數 + 陣列名為指標說明 + sort + 陣列的編號為0~n-1，若從1開始放，要多加空間。 2.b964: 第 1 題 成績指標 + 排序(STL sort) 3.f410: 芝麻街的郵件投遞 + sort + 自訂比較函式 4.c230: 松鼠旅行 + [TIOJ 1419 . 飛天李晴(?) (Sunny)](https://tioj.ck.tp.edu.tw/problems/1419) + 將距離原點的距離由近到遠排序。依距離順序，找出高低差最多的樹。 5.c044: 10008 - What's Cryptanalysis + isalpha() + toupper() 6.d829: 00146 - ID Codes + next_permutation 7.d913: 1. 彈珠配置 + next_permutation依序產生一組彈珠順序 + 比對前6次彈珠順序，如果都符合每次猜測的結果即是答案 8.g005: 倒置文章 (Inversion) + reverse(s.begin(), s.end()) 9.a480: 導彈攔截系統 + 設城市與導彈攔截系統1,2的距離為d1,d2 + 先對各城市d1排序，之後再窮舉求p + p = c[i].d1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max(c[i+k].d2),k>=1 (i城市與導彈1的距離)&nbsp;(其它城市與導彈2的最大距離) ::: ### (二) 循序式容器Sequence Container(vector) + [常用C++ STL：vector](https://yuihuang.com/cpp-stl-vector/) + [vector 心得整理](http://edisonx.pixnet.net/blog/post/34345257-vector-%E5%BF%83%E5%BE%97%E6%95%B4%E7%90%86) + [0-17 vector | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/11/30/0-17/) + vector [說明1](http://slides.com/sylveon/cp2019-spring#/1/14)、[說明2](http://slides.com/sylveon/i2a-19#/8/2) :::info EX_3_2_1:d323: 電腦-窮人的 + 指標、樣板說明 + vector + iterator + v.push_back(x) v.s. cin >> v[i] + sort(v.begin(), v.end()) + [STL vector 效率小記](http://pingyeh.blogspot.tw/2011/09/stl-vector.html) + C\+\+ 11設定 - CodeBlocks：Settings / Compiler / Have g++ follow the C\+\+11 ISO C++ language standard - Dev-C\+\+：專案 / 專案選項 / 編譯器訊息 / 程式碼產生 / 語言標準(-std) / ISO C\+\+11 - for(int e:v) - for(int& e:v) * v.resize(n) ::: :::info EX_3_2_2:d186: 11461 - Square Numbers + 以vector改寫 + iterator + [常用C++ algorithm：lower_bound & upper_bound](https://yuihuang.com/cpp-algorithm-lower-bound-upper-bound/) ::: :::warning 1.f819: 圖書館 (Library) + 將逾期的書本編號放入vector，排序後印出。 2.f820: 極限運動 (Sports) + 將高度儲存在vector，從著陸點分別向左、右滑至停止點。比較停止點高度，輸出高度小(垂直落差大)的位置。 3.c295: APCS-2016-1029-2最大和 + 將可以整除S的被選擇數字，以vector儲存後印出。 4.b051: 2. 排列最大值 + sort + 自訂比較函式大到小排序(s1+s2>s2+s1) 5.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; ``` 6.b844: 一堆按鈕 + 直觀解陣列會太大，且會TLE( O(N*K) )。 + 用陣列記錄N個按鍵號碼，陣列中有幾個數字小於等於詢問的數字，即0、1切換的次數 + 可先排序，以2分搜加速 7.b005: 布林矩陣的等價短陣 + 分別計算每行、每列的和為奇數的個數，若沒有奇數為等價，若行、列中各有一個奇數則Change bit (該行,該列)，其餘情況均為Corrupt ::: ### (三) 循序式容器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) + [0-20 set | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/07/0-20/) + [常用C++ STL：set & multiset](https://yuihuang.com/cpp-stl-set/) :::info EX_3_4_1:d129: 00136 - Ugly Numbers + 第1500個醜數為8億多，暴力法會TLE + 醜數為2^x^ * 3^y^ * 5^z^，所以對已存在的醜數*2、*3、*5放入集合 + set會自動排序，並過濾重複數字 + next(it) ::: :::info EX_3_4_2:c807: 一維凸包問題 + [scanf、printf](https://openhome.cc/Gossip/CGossip/PrintfScanf.html) + 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) ::: :::info EX_3_4_3:f607: 3. 切割費用 + 加分題。 + 依切割順序排序後，以set來儲存已切割的點，對每個切割點找它的前、後點。 + s.lower_bound()、s.upper_bound() + insert() 返回值是pair<iterator,bool>，iterator代表插入的位置，若值已經在set中，則iterator表示原來值的位置；bool表插入是否成功。 + next(it)、prev(it) ::: :::warning 1.a541: 字典 + set:insert、find、end 2.b523: 先別管這個了，你聽過安麗嗎？ + set:count、insert、find、end 3.c122: 00443 - Humble Numbers + 類似d129 + typedef long long ll; + vector<ll> v(s.begin(),s.end()); 4.d442: 10591 - Happy Number + 以set記錄曾經出現過的數字，產生下一數字時檢查是否在set中 5.f929: 程式老師的作業 + 以set記錄0的index，因為set會自動排序，每次操作只要處理s.begin()即可。 6.c421: pA 雲端列印 + multiset同set會自動排序，但允許重複 + set: size、empty、begin、end(指向最後一個元素之後的位置iterator)、erase 7.a016: 數獨(SUDOKU) + 可用set記錄橫向、縱向、九宮格裏的數字，因為set會過濾重複的數字，判斷是不是剛好有9個數字 8.d194: 11572 - Unique Snowflakes + 求最長相異子序列 + set:count、insert、erase、find + queue:front、push、pop、size + 當新元素x重複時，刪除queue中x之前的元素(可能產生最多相異的新的開始) 9.c423: pB 還原密碼 + set:begin、end、insert、erase + for(auto it:s) //C++11 + stringstream字串數字轉換 + string字串截取str.substr(pos,n) + [C++基础-string截取、替换、查找子串函数](http://blog.csdn.net/ezhou_liukai/article/details/13779091) ::: ### (五) 關聯式容器Associative Container(map) + [Map (STL) 用法與心得完全攻略](http://mropengate.blogspot.tw/2015/12/cc-map-stl.html) + [C++ STL: map的按key和按value排序](https://www.itread01.com/content/1544616191.html) + [常用C++ STL：map & unordered_map](https://yuihuang.com/cpp-stl-map/) :::info EX_3_5_1:a743: 10420 - List of Conquests + 在map插入<key, value>時，就會按照key的大小順序儲存。 + map:find、end、iterator + stringstream + cin.ignore() + C++11 auto ``` c for(auto it=mp.begin();it!=mp.end();it++) cout << it->first << " " << it->second << endl; for(auto elm:mp) //取得的元素是pair cout << elm.first << " " << elm.second << endl; ``` ::: :::info EX_3_5_2:e288: 互補CP + map<long long ,int> mp; + mp.find()，mp.end() + 位元運算(|、^、<<) + 可將第n位元作為有無對應角色的狀態。「1」代表有該角色，「0」代表沒有。 + 若 a xor b = c 則 a xor c = b。 + [解題參考](https://home.gamer.com.tw/creationDetail.php?sn=4467142) + C++ IO加速 ::: :::warning 1.b162: NOIP2007 1.统计数字 + map<int,int> + map插入<key, value>時，就會按照key的大小順序儲存。 2.c054: 10082 - WERTYU + map:find、end 3.d517: 文字抄寫 I + map<string,int> + C++ IO加速(+'\n') 4.d244: 一堆石頭 + map<int,int> + iterator + C++11 auto 5.d492: 10226 - Hardwood species 6.b265: Q11286 - Conformity + 將課程代碼排序後組成字串當成map的key。 7.a821: 4.王者之路 + 將每一隊擊數的隊伍以set記錄，輸出擊數隊伍數為n-1，且沒有被擊數的隊伍。 + map<string, set<string> > mp; 8.e839: P6. 飲食分類 (Food) + map<string, vector<string>> mp; ::: ### (六) 容器配接器Container Adaptor(stack) + [常用C++ STL：stack](https://yuihuang.com/cpp-stl-stack/) :::info EX_3_6_1:b304: 00673 - Parentheses Balance + stack:push、pop、top、empty + 空的stack執行sk.top()會錯誤 + scanf("%d\n",&n) 或cin.ignore() 將換行字元讀掉 + 輸入有空字串，要輸出 Yes，所以以getline(cin,s)讀一整行 ::: :::info EX_3_6_2:c123: 00514 - Rails + 將車廂依序從A方向「push」進Station(stack)，並檢查stack的top是否為B方向要的車廂編號，若是則「pop」(表示開到B方向)。 + 最後檢查stack是不是空的。 + stack:push、pop、top、empty + 空的stack執行sk.top()會錯誤 ::: :::warning 1.b923: 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.f698: 後序運算式 + [stoi](https://tw511.com/a/01/11129.html) 7.b838: 104北二2.括號問題 + 遇「(」push + 遇「)」檢查stack是否是空的，如果不空pop，如果空，則括號不正確。 8.最接近的高人 + [TCFSH CIRC Judge](https://judge.tcirc.tw/ShowProblem?problemid=d028) + 暴力法會TLE，由前往後看時，那些是沒有用的資訊？ + 如果 a[i-1]<=a[i]，那麼a[i-1]不可能是i之後的高人，因為由後往前找時，一定會先碰到a[i](如果a[i]不夠高，那a[i-1]也一定不夠高)。 + 所以只要以stack維護好一個遞減序列，就可有效率的解決問題。 9.c907: 尋找最大矩形 + [提示](http://course.lksh.ntpc.edu.tw/ShowProblem?problemid=a144) + [解題心得](https://home.gamer.com.tw/creationDetail.php?sn=4234008) 10.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) + [C++ queue 和 deque的区别](https://blog.csdn.net/qq_25800311/article/details/89060069) + [0-22 priority_queue | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/10/0-22/) + [0-23 deque | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/14/0-23/) + [常用C++ STL：queue](https://yuihuang.com/cpp-stl-queue/) + [常用C++ STL：priority_queue](https://yuihuang.com/cpp-stl-priority-queue/) :::info EX_3_7_1:e289: 美麗的彩帶 + 顏色編號介於0~10^150，以string儲存顏色代號。map<string,int>記錄顏色的數量。(離散化觀念 discretization) + 因為順序不重要，可用unordered_map查詢會更快。 + 滑動視窗，使用queue或deque，模擬區間由左向右滑，左邊出去一個顏色(front pop)，右邊進來一個顏色(back push)。比對queue內相異顏色數量是不是等於M。 + 因為n最大只到20萬，可以將所有的彩帶顏色讀入陣列，再以L、R代表要出去、進來的顏色索引，即不用用到queue。 + C++ IO加速。 ::: :::info EX_3_7_2:b151: NOIP2004 2.合并果子 + 取priority_queue中兩個最小值相加後再放入佇列 + priority_queue< Type, Container, Functional > - priority_queue<int, vector<int>, greater<int>> pq; - priority_queue<int, deque<int>, greater<int>> pq; + 欲取最大值使用less，欲取最小值使用greater ::: :::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://toi-reg.csie.ntnu.edu.tw/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_3_8_1:a915: 二维点排序 + 以pair改寫，pair的比較原則是先比前面元素，一樣再比後面元素。 ::: :::info EX_3_8_2:b563: 3.魔法學校交換生問題 + {v1,v2} 或 make_pair(v1,v2) ::: :::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_3_9_1:f630: 5. 共同朋友 + 相鄰矩陣平方，計算有多少1。 $$ \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()還不會全對，改用any()。 + 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_4_1:b230: TOI2009 第二題：方便數 + [idoreal number](https://oeis.org/A000926) + 使用三層迴圈分別列舉 a、b、c(1~65)，計算非方便數，並以陣列標記。 ::: :::info EX_4_2:c460: 3. 軍隊部署 + 單純窮舉會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也可解嗎？ ::: ## 五、排序 + [各種排序演算法](https://docs.google.com/document/d/10-N2JoDV0ZSH49d4s9zpoE71oPFUMORCfKOaJHKV27w/edit#heading=h.7sf5u9kriydv) :::info EX_5_1:b966: 第 3 題 線段覆蓋長度 + 開10^7^bool陣列，讀一筆線段就從L標計到R，最後計算標計的數量。時間O(n)*O(10^7^)可行嗎？ 空間？ + 將輸入線段依左端點座標排序。則前後兩線段的關係只可能為重疊(包含相連)或不重疊(新線段) - 如果下一線段的左端點 > 前一線段的右端點，表示前一線段已結束，計算並加總覆蓋長度。 - 如果下一線段的左端點 <= 前一線段的右端點，表示前一條線段可延續，調整前一線段右端點位置即可。 + 掃描線演算法(sweep line algorithm) ::: :::info EX_5_2:g277: 3. 幸運數字 + 區間範圍會越來越小，且區間外的數字不會用到。因此可以先將數列排序後，從頭開始檢查是否在區間內(區間外直接忽略)，即是區間最小值。 + 區間和用前綴和。 + 可用 map 記錄數值的索引值。 + 也可用線段樹找區間最小值。 ::: :::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)時為true 6.b542: 聽到這兩個人的身高，讓十萬人都驚呆了 + [解題參考](https://emiliatancoding.blogspot.com/2019/02/b542.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_6_1:d732: 二分搜尋法 + 函式陣列參數。 + 陣列從index 1 開始存。 ::: :::info EX_6_2：e616: Aggressive cows + [最小值最大化](https://blog.csdn.net/qq_43690454/article/details/104020240) + 對答案二分搜。假設一個答案，檢查這個答案是不是符合條件限件，以二分搜尋的方式逼進最大值。 ::: :::warning 1.f679: 公會成員 + 二分搜尋可用lower_bound 2.e541: 10474 - Where is the marble + 二分搜尋可用lower_bound 3.b836: kevin戀愛攻略系列題-2 說好的霸王花呢?? + O(N) -> O(log2N) -> O(1) 4.f815: TOI_y21m4_a01遊戲升等 + 以二分搜尋找出符合條件的最大等級。 5.c575: APCS 2017-0304-4基地台 + 對n個服務點排序，並計算服務點兩兩相鄰距離。若要分成K群，則找出前K-1個最大的兩兩相離距離，作為分群切割處。(時間複雜度高) + 實做可用二分搜尋的觀點。因為基地台直徑的答案一定介於1~(最遠服務點-最近服務點)。先假設可能答案為最大最小值中間，測試k個基地台可否覆蓋所有服務點，不行則調整基地台直徑，以二分搜尋法找出答案(直接對答案進行二分搜尋)。 6.c904: 天龍國的蜜蘋果 + [最大化平均值1](https://www.twblogs.net/a/5c9e53cabd9eee7523887628) + [最大化平均值2](https://blog.csdn.net/karry_zzj/article/details/70232097) 7.c942: 露營區規劃 + 每個圓都至少有一個露營點，所以各點之間環狀距離的最大值為「最小圓周長」，最小值為 0。 + 以二分搜尋測試假設的環狀距離，是否可以規劃出 M 個露營點。 + 可假設 PI=2*acos(0); 8.圓環出口 + [TCFSH CIRC Judge](https://judge.tcirc.tw/ShowProblem?problemid=d024) + prefix。例如在位子i開始找一個j，使a[i]~a[j]的和>=Q，相當於找 prefix[j]>=prefix[i-1]+Q。 + 二分搜尋 + [解題參考](https://hackmd.io/@emanlaicepsa/APCS202007?fbclid=IwAR167sM5rLEjyCItz0QxNcXz2MjtuWMiH0-9dPHPfJvQWENkfJ0tSR5TVZo#p3) + 因為 qi 不會超過 p 的總和，所以將原序列複製一次再求前綴和，可簡化操作。如果沒有此限制，也只需將 qi 預先 mod p的總和即可。 ::: ## 七、模擬 :::info EX_7_1:f580: 2. 骰子 - 骰子有每個相對面之點數和等於7的特性，所以只需儲存三個面的點數即可，如題目所提的上、前、右。 - b為-1向前翻轉，所以原本上面會變成新的前面、原本後面(7-前面點數)會變成新的上面。 - b為-2向右翻轉，所以原本上面會變成新的右邊、原本左邊(7-右邊點數)會變成新的上面。 ::: :::info EX_7_2:f313: 2. 人口遷移 ::: :::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) ![](https://i.imgur.com/nc8VIrb.png) 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) ::: ## 八、Greedy :::info EX_8_1:d044: 例題 P-4-3. 十年磨一劍(最少完成時間) + [TCFSH CIRC Judge](https://judge.tcirc.tw/ShowProblem?problemid=d044) + minimum completion time 經典題 + 放在越前面的工作，等它的人越多，所以短的工作先做。 ::: :::info EX_8_2:d045: 例題 P-4-4. 幾場華山論劍(activity selection) + [TCFSH CIRC Judge](https://judge.tcirc.tw/ShowProblem?problemid=d045) + activity selection problem 經典題 + 若[x,y]是還未選取線段中右端點最小的線段，那麼最佳解一定會挑選[x,y]。 + 一開始依照右端點由小到大排序，然後不斷將最小右端的線段挑進最佳解，略過與它重疊的線段。 + 排序自訂比較函數的偷懶寫法→利用pair。 ::: :::info EX_8_3:c471: apcs 物品堆疊 (Stacking) + 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.d042: 例題 P-4-1. 少林寺的代幣 + [TCFSH CIRC Judge](https://judge.tcirc.tw/ShowProblem?problemid=d042) 2.d043: 例題 P-4-2. 笑傲江湖之三戰 + [TCFSH CIRC Judge](https://judge.tcirc.tw/ShowProblem?problemid=d043) 3.a465: 12405 – Scarecrow + 遇到可耕種土地時，即在右邊之土地放一個稻草人，並將已被涵蓋的可耕種土地視為不可耕種之土地 4.e538: 11389 - The Bus Driver Problem + 將早晨巴士路線由小->大排序，傍晚巴士路線由大->小排序。( sort搭配比較函式 greater<int>() ) + 最短的早晨巴士路線搭配最長的傍晚巴士路線，會使支付的總加班費最小。 5.f832: 隕石 (Meteorite) + 將隕石重量、捕捉器容量排序 + 由捕捉器容量大到小，決定是否可以裝入此時最大重量的隕石。 6.e801: p8. 排課表 + 依照課程結束時間由小到大排序（結束時間早可增加後面選課的機會），然後從小的開始選。 7.f627: 1. 礦砂採集 + Fractional knapsack + 依單位重量價值由大到小排序。 + 不斷將單位重量價值最大的礦砂放入背包，直到背包已滿或沒有礦砂可放入。 8.d418: 00993 - Product of digits + 將整數分解因數，因為要求Q最小，所以從9開始找 + 當因數全部分解完，n不等於1，表示不存在Q 9.b231: TOI2009 第三題：書 + 印刷機只有一台，所以不管順序為何，總列印時間不變 + 隨時可以裝訂無限本書，所以要先列印裝訂久的書 10.d731: 11039 - Building designing + 樓層分顏色儲存排序，分別從兩陣列中交錯拿出符合條件的最大面積 + 運算子多載 11.c134: 00668 - Parliament + 將n切割成相異數字，並且各數字的乘積最大 12.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) 13.e915: pC. 追求完美的廚師 + 點餐所需的累積時間要用long long。 14.f160: 1. 音檔剪輯 + 從頭開始，盡量讓每次切割出的區間最長，區間個數即會最少。 ::: ## 九、Divide & Conquer :::info EX_9_1:d219: 00374 - Big Mod + [分配律](https://zh.wikipedia.org/wiki/%E6%A8%A1%E9%99%A4) + (A\*B)%M=[ (A%M)\*(B%M) ]%M→B^P^%M=[ (B^P/2^%M)\*(B^P/2^%M) ]%M + EX：4\*5%3=(4%3)\*(5%3)、5\*8%3=(5%3)\*(8%3)%3 ::: :::info EX_9_2:d064: P-5-4. 反序數量 (APCS201806) + [TCFSH CIRC Judge](https://judge.tcirc.tw/ShowProblem?problemid=d064) + [資訊之芽算法班 第六週 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_9_3:d065: P-5-7. 大樓外牆廣告 + [TCFSH CIRC Judge](https://judge.tcirc.tw/ShowProblem?problemid=d065) + 以最小高為中間的切割點，如果每次的最低點都在邊緣，例如輸入高度是遞增或遞減，時間複雜度會高到O(n^2^)。 + STL min_element ::: :::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。 ::: ## 十、Graph + [板橋高中校內培訓-圖論](https://docs.google.com/document/d/1ZptN-ebhkOITe1a_BTacqRqWW6DH4HZEv5DBbPnukk0/edit#heading=h.6fi8c333cw4) + [圖論相關主題](http://slides.com/sylveon/graph-7) ### (一) DFS :::info EX_10_1_1:d626: 小畫家真好用 + 全域變數 + 分四個方向做DFS ::: :::info EX_10_1_2:d091: P-7-2. 開車蒐集寶物 + [TCFSH CIRC Judge](https://judge.tcirc.tw/ShowProblem?problemid=d091) ::: :::info EX_10_1_2:c463: apcs 樹狀圖分析 (Tree Analyses) + 子節點因數量不定，可用vector諸存 vector<int> child[100000]; + [vector二維陣列1](https://ramihaha.tw/c-program-container-vector-array-linklist/) + [vector二維陣列2](http://f74461036.pixnet.net/blog/post/274951462-c%2b%2b-vector二維陣列) + memset ::: :::warning 1.d365: 10336 - Rank the Languages + 類似d626 2.d165: 八、草场普查 + 類似c129 3.c129: 00572 - Oil Deposits + 可以在地圖外包一層0，則不用檢查邊界 + 可以使用陣列儲存要走的方向 4.a290: 新手訓練系列 ~ 圖論 5.c139: 00291 - The House Of Santa Claus 6.d324: 00750 - 8 Queens Chess Problem + 一維陣列queen[8]，陣列索引為皇后的col，值為皇后的row 7.a229: 括號匹配問題 8.d115: 數字包牌 + 窮舉 9.d653: VAC+ _ 社費問題 d115加強版 + 剪枝(將不可能的解剪掉，不繼續遞迴下去) 10.b110: 3. 黑白影像的四分樹表示法 11.d536: 第三題：圖形迴圈偵錯問題 + DFS偵測環 12.c291: APCS 2017-0304-2小群體 + 陣列 + 不斷追蹤下一位朋友，直到他已經被紀錄過 + DFS偵測環 13.b967: 第 4 題 血緣關係 + 類似c463 14.b108: 1. 銀河帝國旅行社 + 類似b967 15.f161: 3. 尋寶之旅+ 在 DFS 過程中，每次走到一個節點，就將該點顏色數量加一。當 DFS 返回父節點時，把該點顏色數減一，以表示回復到沒有走到此點的狀態。 + 在拜訪每個節點時，檢查該點的顏色數量有沒有超過最大值。 + 寶石的顏色號碼不超過10^9^，記錄每一顏色的寶石數用陣列會太大，離散化可以用 [STL map](http://larry850806.github.io/2016/06/06/STL1/#map)。 16.b343: 11518 - Dominos 2 + 骨牌後可能有多張骨牌 + vector二維陣列 + v.clear() + fill() 17.d768: 10004 – Bicoloring + vector二維陣列 + v.clear() + fill() 18.a470: 12406 - Help Dexter + 數字*10+1或2，產生下一位p位數DFS 19.d762: 10344 - 23 out of 58 + next_permutation + DFS窮舉所有可能 20.c812: 1. 觀光景點 + DFS搜尋所有和Vk相鄰的點 + [Edge List](http://www.csie.ntnu.edu.tw/~u91029/Graph.html#2) + vector、pair 21.f168: m4a2-分配寶物(Treasure) + 枚舉各個寶物分配的情況，總共有3^N種可能的組合。 + 剪枝。 ::: ### (二) BFS :::info EX_10_2_1:d090: P-7-1. 探索距離 + [TCFSH CIRC Judge](https://judge.tcirc.tw/ShowProblem?problemid=d090) ::: :::info EX_10_2_2:f170: m5a1-尋找小狗(Dog) + queue + pair + C++ IO加速 ::: :::warning 1.a982: 迷宮問題#1 + queue + pair 2.d406: 倒水時間 3.d663: 11730 - Number Transformation + 產生轉換次數相同的所有數字B(佇列開頭A+小於它的質因數)，放入佇列 + 如果產生的數字已在佇列則忽略(新數字轉換次數一定較大) + [解題參考](http://kos74185foracm.blogspot.com/2013/07/11730-number-transformation.html) 4.c077: 00417 - Word Index + 取出佇列前的字串，添加可以加的字母後放入佇列 + 使用map存字串對應的值 5.b059: 4. 靈犬尋寶 + BFS + 類似a982: 迷宮問題 6.b701: 我的領土有多大 + BFS或DFS 7.c117: 00439 - Knight Moves + 騎士L走法有八個方向 + queue + struct 8.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。 + struct 建構函式、運算子多載 + [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) + [Disjoint Set](http://acm.nudt.edu.cn/~twcourse/DisjointSets.html) + Weight會超過int 2.b181: 2. 網路設計 3.d909: 公路局長好煩惱！？ 4.e810: 2.潛水 (Diving) ::: ### (七) 尤拉路徑(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 + [拓撲排序](https://www.csie.ntu.edu.tw/~sprout/algo2017/ppt_pdf/topological_sort.pdf) 3.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.c455: 4. 警力配置 + [二分圖最大匹配](https://www.itread01.com/content/1501297091.html) ::: ### (十一) 關結點(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](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/) ::: ## 十一、Set + [演算法筆記 Set](http://web.ntnu.edu.tw/~algo/Set.html#5) :::info EX_11_1:a445: 新手訓練系列- 我的朋友很少 + [並查集](https://www.youtube.com/watch?v=JoCeTg0QAZQ)(Union-find Sets、disjoint set) ::: :::warning 1.d831: 畢業旅行 + 並查集(Union-find Sets、disjoint set) 2.d813: 10583 - Ubiquitous Religions + 並查集(Union-find Sets、disjoint set) 3.c131: 00615 - Is It A Tree? + [以並查集判斷加入的邊是否形成cycle](http://kos74185foracm.blogspot.com/2011/08/615-is-it-tree.html) + 只能有一個樹根 ::: ## 十二、Tree :::warning 1.a584: 2. 親等關係 + 找尋距離兩節點最近的共同祖先。 2.d526: Binary Search Tree (BST) + 鏈結串列 + 二元搜尋樹 3.c126: 00536 - Tree Recovery + 二元樹追蹤(前序、中序、後序) 4.f163: 貨物分配 + 二元搜尋樹 + [解題參考](https://yuihuang.com/nuts-apcs1090105-4/) ::: ## 十三、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://toi-reg.csie.ntnu.edu.tw/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.採蘑菇攻略問題 ::: ### (三) 零錢 + [演算法筆記-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/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/b131-noip2006-2) 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.g278: 4. 美食博覽會 + [解題參考](https://hackmd.io/@peienwu/APCS0904) ::: ### (五) LIS + [演算法筆記-LIS](http://web.ntnu.edu.tw/~algo/Subsequence.html) :::warning 1.d078: P-6-15. 一覽衆山小 + [TCFSH CIRC Judge](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](http://web.ntnu.edu.tw/~algo/MaximumSubarray.html) :::warning 1.b123: 最大矩形 (Area) + 計算每列的面積，再往上找出能構成最大面積的高度 ::: ### (九) 矩陣鏈乘積(Matrix Chain Multiplication) :::warning 1.d086: Q-6-18. 矩陣乘法鏈 + [TCFSH CIRC Judge](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) ::: ## 十四、數學 + [板橋高中校內培訓-中學數學]( 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，窮舉數列任兩數，只要兩數值差==序號差且，左數為區間最小值，右數為區間最大值即是一解 :::