###### tags: `選修` # APCS(大學程式設計先修檢測)程式實作(V2) :::success ### 零、評量、學習歷程 ::: ### 1. 評量方式 + 上課基本練習(遲交期限：1週) **40%** + 作業題數 **20%** (期中10%+期末10%) - 作業登記表：[117](https://docs.google.com/spreadsheets/d/1iFnhELs0zlr7zcNqY7KdF6OWMro9O7bsL5ruQwA9KII/edit?usp=drive_link)、[118](https://docs.google.com/spreadsheets/d/1j4WhWu4BnuSd6YjuuWp_eoRQAYg1knAR4Ah1t5WsrkI/edit?usp=drive_link)、[高一多元選修](https://docs.google.com/spreadsheets/d/17Xi5ZwFBrD3YJIZBadRi_Uf8aZh-r1Elq5BHs29QuZs/edit?usp=sharing) - [歷年作業登記表](https://hackmd.io/@cube/r1Cw2JgDT) - 每寫完一題作業，請將程式碼連結登錄於作業登記表，以統計作業題數。請小心不要改到別人的資料。惡意編刪別人的資料，視情節扣分或校規處理。 - 作業原始分數：解題數 $*$ 6 (最高120分) ``` if 上機考分數>=60 作業實得分數=作業原始分數 else 作業實得分數=作業原始分數*(上機考成績/60) ``` - 不要為了衝題數，做複製貼上、不求甚解這種沒意義的事。上機考0分，全部都寫也是0分。 - 不寫作業，除了無作業成績，上機考時網路會斷線，沒有任何參考資料，也必定寫不出來，請每個單元至少完成 5 題作業，熟練基本語法。**(不寫作業被當的機會很高，除非你有本事上機考2次都及格)** - 不要考前才寫作業，初學程式會有很多錯誤，要花時間除錯。請自我要求每週至少要寫 2 題作業，上機考才會比較保險。 - 不會的可以去參考網路上的程式碼、解法，同學也可以互相討論，而且是鼓勵的。不論如何，都要在了解解法後，不看別人的程式碼，自己親自寫一遍。 - 有做作業，考差了才有補救的機會，作業題為期末解題報告的題目。 + 期中上機考(迴圈教完後 1 週) **20%** + 期末上機考(倒數第 2 週) **20%** + 期末解題報告 **10%** - 非必要，想高分或不及格的同學請保握最後機會。 - 繳交期限：最後一週上課前 1 天。 - 分數：每一題 10 分。每個單元至多可放 2 題 (不可以都寫同一單元的題目) - 報告格式： * 第1頁為解題目錄(單元、題號、題目、頁碼)。 * 每題的子標題為 (1) 單元、題號、題目、題目簡述 (2) 解題動態、評分結果截圖 (3) 解題思路 (4) 程式碼 (5) 反思(遇到的錯誤、修正的地方、更好的方法…) (6) 錯誤程式碼 - 檢核方式： * 有交解題報告者，最後一週會請你在沒有網路的狀態下重寫一題當做檢核(題目由老師挑選)，寫不出來作業直接作廢不算分，請務必自行思考完成。 * 不要為了分數直接複製貼上別人的程式碼，那是無意義的行為，檢核時你就會現出原形，就不用做這種白工了。 - 可整合上課內容後完成課程學習成果，上傳至學習歷程檔案平台。請儘量挑選一開始有錯，然後修正的題目，將修正的想法寫出來更能顯示出反思的能力。 + 本課程的目標為考APCS檢定，請多寫作業多練習，實作題才有機會考到 3 級以上。 + 117 下學期選修從「貳、TOI 線上練習賽 潛力組範圍」開始上。 ### 2. [TOI推廣計畫-線上練習賽](https://tpmso.org/toi/index.php/reg/) + 成績計算：分數/100直接加在總成績。(117下學期：新手組分數/300，潛力組分數/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 =150x )](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/) - 「+ Create Repl」 可新增一個 Repl (專案) - Template 欄選擇 「C++」 或 「Python (with Prybar)」，Title 欄填入專案標題如 a001， 再按「+ Create Repl」鈕，就會進入專案編輯的頁面。 - My Repls：專案管理 New folder：建立分類資料夾，如 class、homework …。 專案.../Move：將專案移至分類資料夾。 - Themes：VS Code Dark/Use Theme - Indentation Size 調為4：側邊欄/Tools/User Settings/Indentation size:4。 - AI Code Completion：關閉。 + [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) ``` c= #include <iostream> using namespace std; int main() { string str; // 變數宣告 cin >> str; // cin >> 變數名; cout << "hello, " << str << "\n"; } ``` ::: :::info EX_1_2:[d060: 還要等多久啊？](https://zerojudge.tw/ShowProblem?problemid=d060) + 3元運算子。 + (條件式 ? 條件式為 True 時要執行的敘述 : 條件式為 False 時要執行的敘述) ::: :::info EX_1_3:[d485: 我愛偶數](https://zerojudge.tw/ShowProblem?problemid=d485) + /：整數除法。 + %：取餘數，2個運算元必需都為整數。 + 複合指定運算子。 ``` c x=x+1; x+=1; y=y-1; y-=1; b=b-5; b-=5; m=m+100; m+=100; ``` + 將a,b調整成偶數(a如果是奇數+1,b如果是奇數-1)，計算2個偶數間的偶數。 a=a+a%2; a+=a%2; ::: :::info EX_1_4:[b004: 繩子上吃草的牛](https://zerojudge.tw/ShowProblem?problemid=b004) + while(cin >> D >> L) // 不可加分號 + 半長軸(hl)：hl=L/2; + 半短軸(hs)：hd=D/2; hs=sqrt(hl\*hl-hd\*hd); + sqrt()、acos(0)，需含入 cmath + const double pi= ... ; + Q：int D,L？ A：形態轉換(double) + C++小數點位數控制 ``` c #include <iomanip> cout << fixed << setprecision(3); // setprecision(n) 會將輸出的數值控制為 n 位數，如果加上 fixed 表示只控制小數點以下的位數。 ``` + 萬能標頭檔案 #include <bits/stdc++.h> // Replit 無法使用 + `Ctrl+Shift+v`：Replit 測資貼上。或右鍵／貼上。 ::: :::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.a861: 1.Secure the Perimeter + 2h+2w(*不能省略)，(h+w)*2 ``` c #include <iostream> using namespace std; int main() { int h, w; while (cin >> h >> w) { cout << 2 * h + 2 * w << "\n"; } } ``` + [縮排風格](https://ncyuweb.ncyu.edu.tw/files/site_content/cc/coding%20style.pdf) 2.d053: Big Chocolate + 3x4巧克力需要11刀 + m-1+m*(n-1) (why?) 3.h215: 客製金莎巧克力金字塔 + [平方和級數公式](https://www.youtube.com/watch?v=_cQ0Mh_DB7U) 4.d489: 伏林的三角地 + 海龍公式計算三角形面積 + s=(a+b+c)/2 + $area=\sqrt{(s(s-a)(s-b)(s-c))}$ 5.d827: 買鉛筆 + /、\%、(( )) 6.b681: 1. 山洞探險 + 3元運算子 + 向北公式為2L-1，向南為？ + long long int 7.d127: 二、牧場面積 + 接近正方型面積會最大 + long long int 8.d096: 00913 - Joana and the Odd Numbers + long long int + 有N個奇數為第(N+1)/2列 + 找出此列最後3個數字與第(N+1)/2列的關係 9.c776: 106北二1.六邊形屋瓦 + 扣掉重覆的白色屋瓦。公式？ 10.d549: 矩形中的几何 + PA^2^ + PC^2^ = PB^2^ + PD^2^ (畢氏定理，why?) + sqrt()，需含入 cmath 標頭檔 + 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 + 測資：100 100 99 ::: :::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+D』(Replit)、『Ctrl+Z』(CodeBlocks)暫停程式執行後，答案才會一次顯示出來。 } } ``` ::: :::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.d058: BASIC 的 SGN 函數 + 巢狀if + 比較運算子 > >= < <= == != 3.a053: Sagit's 計分程式 + 多項選擇 + 錯誤：if(11<=n<=20)，正確：if(n>=11 && n<=20) 4.g496: 彗星列車 (Comet) 5.g497: 電梯 (Elevator) 6.d066: 上學去吧！ + 亦可將時化為分 7.e286: 籃球比賽 8.a006 一元二次方程式 + sqrt()，需含入 cmath 標頭檔 9.h660: 躲避球 (DodgeBall) 10.c461: apcs 邏輯運算子(Logic Operators) + 位元運算子&(AND)、|(OR)、(^)XOR + 將a、b以位元運算子運算後和c比較 ::: ## 三、迴圈 :::info EX_3_1:[a824: 2.藏寶問題](https://zerojudge.tw/ShowProblem?problemid=a824) + 先完成 for 迴圈，迴圈內印出 i - Q1：i 宣告為區域變數，迴圈完再多一行印出。i=10 時，i 為多少？ - Q2：i=10 時，還會回到上面的 for 嗎？ - 逐行除錯示範迴圈如何運作。 - 區塊變數 vs. 區域變數 + 型別轉換：[ASCII](https://zh.wikipedia.org/zh-tw/ASCII) + sum 變數歸零 (逐行除錯看sum的值。最基本的除錯方法 → 把變數的值印出來看看) + Bonus：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> :mega: 逐行除錯 [Replit](https://docs.replit.com/programming-ide/workspace-features/debugging) (1) 執行目前程式(Ctrl+Enter)後發現錯誤。 (2) 打開除錯視窗(Debugger)，並將其拖曳至適當位子(不要和Console在同一窗格)。 (3) 設定中斷點(可跳過沒問題的程式)。 (4) 按除錯視窗的『RUN』。 (5) 使用『Next Step』或『Skip Step』或『Next Breakpoint』逐行執行，並觀察變數的變化。 (6) 發現錯誤按『Stop』停止除錯，修正程式。 CodeBlocks (1) 設中斷點 (2) Debug (F8) (3) Debugging windows/Watches (4) Next line (F7) (5) Stop debugger :::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) 除錯示範 + 除錯作業：以除錯觀察為何輸入a=10, b=34時，程式還是正確。 ::: :::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.d490: 我也愛偶數 + for + 變數初值 2.f605: 1. 購買力 + 找出3物品最大值和最小值，可使用if或max、min函式。 + max 若要傳入三個以上的參數，須用大括號包住，並含入 algorithm 標頭檔。 3.f312: 1.人力分配 + 以for迴圈窮舉所有可能的工人分配方法。 + 最大值可用max函式或if。 4.i428: 1. 巴士站牌 + 最大值、最小值可用max、min函式。 + 絕對值可abs函式。 5.j605. 1. 程式考試 6.c299: 1. 連號或不連號 + 輸入數列時，找出其最大和最小值(可使用if或max、min函式) + 最大-最小+1==n，表示這個數列是連續的 7.e622: 虛擬寵物大師 (Master) + 計算寵物成長後最終CP值，記錄最大值。 8.g498: 兔子跳躍 (Rabbit) + 每次d先-n，再看看剩下的d%m是否為0，亦即試試看所有的組合方式。 9.c561: Bert 愛搗蛋 + 將數值反轉的方法，假設a為原數值，rvs為反轉後的數值(預設值為 0) rvs=rvs*10+(a%10); a/=10; // 讓個位數消失 10.f063: The Strongest Chain + 巢狀迴圈 ::: ## 四、陣列 ### 1. 陣列宣告 ``` c int a[5]; // 宣告一個大小為5的int陣列 a[0]=80; // 陣列的索引值由0開始 a[5]=90; // 錯誤，索引值0~4 int a[5]={1,3,5,7,9}; // 宣告陣列時設定初值 for(int i=0;i<5;i++) { // 以 for 迴圈來控制陣列的 index 輸出 cout << a[i] << " "; } 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) + 不斷追蹤下一位朋友，直到他已經被紀錄過。 + 先完成 - 從 0 開始的循環，印出 0 4 6 8 5 0。 - 沒有 vis 陣列(會造成重復算)。 ::: ### 2. 二維陣列 :::info EX_4_4:[m371. 2. 卡牌遊戲](https://zerojudge.tw/ShowProblem?problemid=m371) + 二維陣列 + 檢定時如果沒有把握二維陣列的解法，可以先做n=1時的子題，會簡化為1維陣列，拿到一半的分數。 ::: :::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.g595: 1. 修補圍籬 3.c067: Box of Bricks + 一維陣列 4.i399: 1. 數字遊戲 5.f579: 1. 購物車 + 商品編號為陣列的索引值。 + 不用陣列亦可。 6.i071: 風景 (Landscape) + 1-based indexing + 從小明家往左、往右檢查>小明家樓高的數量，錯誤的原因為？ + 以變數(LMax、RMax)記錄小明家左邊、右邊最高樓高(初值為小明家高度)。從小明家往左、往右檢查，如果檢查的樓高>LMax、RMax，則答案+1，並調整LMax、RMax。 7.g797: 洗牌 (Cards) 8.d563: 等值首尾和 + 以迴圈讓prefix由前往後加，suffix由後往前加 + 如果prefix(前段和)==suffix(後段和)則答案加1，同時往前、後各加一個元素 + 如果prefix<suffix，則prefix往後加一個元素 + 如果prefix>suffix，則suffix往前加一個元素 9.a693: 吞食天地 + 每次都重算會TLE + 前綴和 10.a015: 矩陣的翻轉 + 二維陣列 11.a694: 吞食天地二 + 二維陣列 + 前綴和 + [C++ I/O加速](http://chino.taipei/note-2016-0311C-的輸出入cin-cout和scanf-printf誰比較快？/) 12.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 做數字、字串間的轉換。需含入 sstream 標頭檔 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) + [讓你融會貫通使用 C++ 的 string 初級篇](https://tigercosmos.xyz/post/2023/06/c++/std-string-beginner/?fbclid=IwAR2xjn9vdrgL4JSzx9MC95PAzvXaI84KI9jHRUHIysjmEVagLBtjwQOP6h8) :::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) + 需含入 sstream 標頭檔 ::: :::warning 1.a009: 解碼器 2.d124: 3的倍数 + 3的倍數判別法：各個數字和為3的倍數 + [1～13的倍數判別法](https://leestar2013.pixnet.net/blog/post/45638266) 3.c290: APCS 2017-0304-1秘密差 + string類別 + str.size() + abs()可求絕對值，需含入 cstdlib 標頭檔 4.h033: 雜訊移除 (Noise) 5.d086: 態度之重要的證明 + toupper()將字元變大寫或tolower()將字元變小寫 + A的ASCII值為65，a的ASCII值為97 6.a224: 明明愛明明 + 統計每個字母出現的次數 + 迴文的條件為：只有一個字母出現的次數是奇數或全部都是偶數 + 每筆測資統計的陣列要歸零 + isalpha()判斷字元是否為英文字母 + toupper()將字元變大寫 7.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) + [解題參考](https://www.youtube.com/watch?v=qHlGmilwooA) 8.a275: 字串變變變 + 使用陣列儲存兩字串各別字母出現的次數(以字母的ascii為陣列索引) + 如果各別字母出現次數一樣，表示可經由調整順序後，讓兩字串一樣 9.j606. 2. 造字程式 + string s[21]; + [s[i].resize(k);](https://cplusplus.com/reference/string/string/resize/)：先將新字串擴充為長度k的空字串，才能依索引值放入。 10.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/) + 測資 | ![](https://i.imgur.com/PqOBL6H.png =140x) | ![](https://i.imgur.com/oQ5mLc9.png =140x) |![](https://i.imgur.com/GDhJApH.png =140x) |![](https://i.imgur.com/cvJNgmb.png =250x)| | :--- | :--- | :--- | :--- | | 1<br>8<br>ans=64<br>| 20101<br>8<br>ans=32<br>| 202010101<br>8<br>ans=24<br>|| + 函式除錯 - CodeBlocks(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.a623: Combination + 將n!寫成函式，在主程式呼叫3次 2.b112: 5.高中運動會 + 寫一個求gcd的函式 + 多個數的最大公因數 3.d237: 質數合 + 以質數函式測試是否需加此數 + 檢測因數到 $\sqrt{n}$ 才不會TLE + 不可直接輸出142913828922 4.c015: 10018 - Reverse and Add + 將數字反轉寫成函式 + 迴文的檢查為數字反轉後和原數字相等即是 --- 遞迴 --- 5.c002: 10696 - f91 + 遞迴 6.j124: 3. 石窟探險 7.[TCFSH CIRC Judge d007: 習題 Q-1-8. 子集合的和 (APCS201810, subtask)](https://judge.tcirc.tw/ShowProblem?problemid=d007) + [解題參考](https://yuihuang.com/tcirc-d007/) 8.a227: 三龍杯 -> 河內之塔 + [河內塔|樂和遊戲](http://www.novelgames.com/zh-HK/tower/) + [河內塔程式參考](http://notepad.yehyeh.net/Content/DS/CH02/4.php) 9.a469. 10063 - Knuth's Permutation + [解題參考](https://alan23273850.github.io/Online-Judge-Problems/zerojudge/a469/) 10.k733. 3. 磁軌移動序列 + [解題參考](https://hackmd.io/@o2sU2kaQTFW6FIkUj2M-xQ/HJ0v-Nn82?fbclid=IwAR2kzaSicbdb8vrN93nyBPz8ewuY_vm_vK2PWKC6cZTv7ub8pef7h9R33so) ::: <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.f408: 迷你蘋菓鎮 + sort 自訂比較函式 abs(a)<abs(b) + 排序後相鄰2數字為不同符號則+1 2.b051: 2. 排列最大值 + sort 自訂比較函式 s1+s2>s2+s1 3.c230: 松鼠旅行 + [TIOJ 1419 . 飛天李晴(?) (Sunny)](https://tioj.ck.tp.edu.tw/problems/1419) + 將距離原點的距離由近到遠排序。依距離順序，找出高低差最多的樹。 4.d534: 1. 戰艦謎題 + next_permutation 5.g005: 倒置文章 (Inversion) + reverse(s.begin(), s.end()) ::: ### (二) 循序式容器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:[k740. 楊輝三角形](https://zerojudge.tw/ShowProblem?problemid=k740) + [圖示](https://blog.devgenius.io/leetcode-118-pascals-triangle-b2b1d600de49) [![](https://i.imgur.com/ZMweZPz.png =30x)](https://i.imgur.com/ZMweZPz.png) + 2維 vector 固定大小，vector<vector<int>> v(n, vector<int>(n,1)); + 2維 vector 每列大小可變，vector<vector<int>> v(n); v[i].resize(i+1); // 使用前調整每列 vector 的大小。vector.resize(空間); ::: :::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.b005: 布林矩陣的等價短陣 + 分別計算每行、每列的和為奇數的個數，若沒有奇數為等價，若行、列中各有一個奇數則Change bit (該行,該列)，其餘情況均為Corrupt ::: ### (三) 關聯式容器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.c122: 00443 - Humble Numbers + 類似d129 + typedef long long ll; + vector<ll> v(s.begin(),s.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.f929: 程式老師的作業 + 以set記錄0的index，因為set會自動排序，每次操作只要處理s.begin()即可。 5.c421: pA 雲端列印 + multiset同set會自動排序，但允許重複 + set: size、empty、begin、end(指向最後一個元素之後的位置iterator)、erase ::: ### (四) 關聯式容器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.d517: 文字抄寫 I + map<string,int> + C++ IO加速 3.g796: 檔案分類 (Files) + 以s%1000/10為map的key 4.e289: 美麗的彩帶 + 顏色編號介於0~10^150，以string儲存顏色代號。map<string,int>記錄顏色的數量。(離散化觀念 discretization) + 因為順序不重要，可用unordered map查詢會更快。 + 因為n最大只到20萬，可以將所有的彩帶顏色讀入陣列，再以L、R代表要出去、進來的顏色索引。 + C++ IO加速。 + [解題參考](https://www.youtube.com/watch?v=cvAX9vtjFY8) 5.k464. 收購土地 (Land) + 雙指標，並可使用 unordered map 紀錄不同地主的數量。 + [解題參考](https://tpmso.org/toi/wp-content/uploads/question/202304/land.odp) ::: ### (五) 容器配接器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()會錯誤 + cin.ignore() 將換行字元讀掉(或 scanf("%d\n",&n) ) + 輸入有空字串，要輸出 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 + 以stack記錄除3的餘數 + stack:push、pop、top 3.b838: 104北二2.括號問題 + 遇「(」push + 遇「)」檢查stack是否是空的，如果不空pop，如果空，則括號不正確。 4.f698: 後序運算式 5.h028: 202001_3 砍樹 + [解題參考](https://www.youtube.com/watch?v=OdUS1kYxvjg&list=PLpmg1QLbgMuRQXHRkX9iDHyAVIW1D6OJF&index=18) ::: ### (六) 容器配接器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.f816: TOI_y21m4_a02Youtube + priority_queue + 前綴和(累積的下降度) + C++ I/O加速。 + [解題參考](https://www.youtube.com/watch?v=lpPhi25Md1c) 5.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) ::: ### (七) 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加速。 ::: <br/> ## 三、枚舉（enumeration）(Brute Force) :::info EX_3_1:[k732. 2. 特殊位置](https://zerojudge.tw/ShowProblem?problemid=k732) ::: :::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.a364: 2.神秘的進位問題 + 枚舉a,b,c，檢查 C(a, 3) + C(b, 2) + C(c, 1) 是否等於n 3.d914 2. 圍棋資料庫比對 + 枚舉比較棋盤上每個點的狀況 4.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.d150: 11369 - Shopaholic + 將商品價格降序排序，再取每三個內的最小值。 + reverse + i+=3 2.d501: 第二題：數列最小值 + 中位數 + 如果有兩個中位數，介於其中的所有整數都是答案。 3.b966: 第 3 題 線段覆蓋長度 + 開10^7^bool陣列，讀一筆線段就從L標計到R，最後計算標計的數量。時間O(n)*O(10^7^)可行嗎？ 空間？ + 將輸入線段依左端點座標排序。則前後兩線段的關係只可能為重疊(包含相連)或不重疊(新線段) - 如果下一線段的左端點 > 前一線段的右端點，表示前一線段已結束，計算並加總覆蓋長度。 - 如果下一線段的左端點 <= 前一線段的右端點，表示前一條線段可延續，調整前一線段右端點位置即可。 + [掃描線演算法(sweep line algorithm)](http://web.ntnu.edu.tw/~algo/Point2.html) 4.d555: 平面上的極大點 + 點的x由小到大序列時，極大點的y是嚴格遞減的。 + [寻找平面上的极大点](https://blog.csdn.net/cqyz_holiday/article/details/52495567) 5.e809: 1.字母排序 (Letters) + 1<=Q<=10^2^、1<=S<=5×10^6^ + counting sort + 前綴和 + 2分搜 lower_bound ::: ## 五、搜尋 + [要定義好搜尋的區間是\[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.g640: 璽羽的壽司 + 二分搜可用lower_bound 2.f815: TOI_y21m4_a01遊戲升等 + 以二分搜找出符合條件的最大等級。 3.h084: 4. 牆上海報 + 若海報能張貼的最高高度為 h，則所有 >h 都不能張貼，<=h 都能張貼。(單調性)。使用二分搜在1~10^9^裡找一個可成功的最大值。 + 以 Greedy 檢查指定高度能否張貼，如果有區間寬度比現在要張貼的海報還寬，則把海報對齊區間的最左邊(可留更多空間給下一張海報)。 4.e616: Aggressive cows + [最小值最大化](https://blog.csdn.net/qq_43690454/article/details/104020240) + 對答案二分搜。假設一個答案，檢查這個答案是不是符合條件限件，以二分搜尋的方式逼進最大值。 5.[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}); ::: ## 六、模擬 :::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.c296: APCS-2016-1029-3定時K彈 + 約瑟夫斯問題 + 模擬的時間為O(n*k)，當n,k很大時會TLE + [遞迴解](https://www.itread01.com/content/1504374014.html) 2.c292: APCS2017-0304-3數字龍捲風 3.c297: APCS-2016-1029-4棒球遊戲 + [解題參考](https://ithelp.ithome.com.tw/articles/10197956?sc=pt) 4.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 d043: 例題 P-4-2. 笑傲江湖之三戰](https://judge.tcirc.tw/ShowProblem?problemid=d043) 2.g544: 美味漢堡 (Hamburger) + int 陣列區域變數無法超過50萬，要宣告成全域變數，或用vector。 + 針對每一段有相同屬性編號的連續區間，取最大的美味程度來加總。 - 當第 i 個配料的屬性和第 i-1 個配料的屬性不一樣，則加上第 i-1 個配料的美味度。 - 當第 i 個配料的屬性和第 i-1 個配料的屬性一樣，則記錄相同屬性配料的美味度中最大者。 3.f627: 1. 礦砂採集 + Fractional knapsack + 依單位重量價值由大到小排序。 + 不斷將單位重量價值最大的礦砂放入背包，直到背包已滿或沒有礦砂可放入。 4.g597: 3. 生產線 + 先計算各機器所要產出的資料量(亦即給若干線段計算每一點有多少線段經過)(差分+前綴和)，再以 greedy 配對，最小工作量配最大時間，第二小配第二大… + [前綴和與差分 - WiwiHo 的競程筆記](https://cp.wiwiho.me/prefix-sum/) + [解題參考](https://hackmd.io/@peienwu/APCS1107) 5.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) ::: ## 八、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.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/) 4.[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 以內的點，作為右端點。 5.[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.c129: 00572 - Oil Deposits + 可以在地圖外包一層0，則不用檢查邊界 + 可以使用陣列儲存要走的方向 2.a290: 新手訓練系列 ~ 圖論 3.b967: 第 4 題 血緣關係 + 類似c463 4.e287: 機器人的路徑 + [TCFSH CIRC Judge d092: P-7-3. 機器人走棋盤 (APCS 201906)](https://judge.tcirc.tw/ShowProblem?problemid=d092) 5.f161: 3. 尋寶之旅 + 在 DFS 過程中，每次走到一個節點，就將該點顏色數量加一。當 DFS 返回父節點時，把該點顏色數減一，以表示回復到沒有走到此點的狀態。 + 在拜訪每個節點時，檢查該點的顏色數量有沒有超過最大值。 + 寶石的顏色號碼不超過10^9^，記錄每一顏色的寶石數用陣列會太大，離散化可以用 [STL map](http://larry850806.github.io/2016/06/06/STL1/#map)。 ::: ### (二) 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.d406: 倒水時間 + BFS，以 queue 實作。 3.i177: 小畫家 (Painter) + vector二維陣列指定大小與初值：vector<vector<int>> p(h,vector<int>(w,0)); + [解題參考](https://tpmso.org/toi/wp-content/uploads/question/202204/Painter.odp) 4.b059: 4. 靈犬尋寶 + BFS 5.c117: 00439 - Knight Moves + 騎士L走法有八個方向 :::
Last changed by  
 
cube lin
2578
Published on HackMD