--- # System prepended metadata title: 拿到APCS實作5後，回顧我神奇的程式經歷 --- # 序 大家好我是DnDA，我是一個高二下快結束才開始學C++的菜鳥，最近拿到了APCS檢定的觀念4級實作5級。 10個月前，我從完全沒有C++基礎開始學競程，而我的第一個目標就是在APCS中取得好成績。不過，當我想要了解它的難度、該如何準備等等的資訊時，我只在網路上找到各種補習班以招生為目的寫的文章，其中許多內容也令人懷疑。我又用不同的關鍵字搜尋，希望能找到學生以親身經驗寫的心得文，可是各路大神似乎都不認為考APCS是需要經驗傳承的活動，所有寫的都是全國賽、初選，甚至模考等對當時的我太過夢幻的東西。我還記得當時那個什麼都不知道、對什麼都沒概念的我。 因為這樣，這篇文章誕生了。我希望能藉由分享我身為一個初學者的經驗，來讓未來對競程有興趣的人有一份比較沒那麼遙遠的文章可以參考。同時，這也是一份給我自己的紀錄，讓我可以在未來某一天覺得有些迷茫時找回自己的初心。具體來說，**我的coding歷程** 這大段主要紀錄事件，而 **Q&A** 則存放我的一些感想。 不過，有個尷尬的點。我在學競程初期時，有很長一段時間把目標放在APCS實作五級上，我本來預計的感想也很多跟這個檢定相關。然而，聽說APCS要在今年(2025)年中大改版，不少經驗可能無法適用新制，因此篇幅就變得簡短許多。 不管怎樣，預祝看到這篇文章的讀者可以讀得開心並有所收穫。 # 我的coding歷程 ## 第一次想好好學C++ 我還記得，那天是2024年3月1日，高二下的我剛結束一場又一場的雀魂，被放學的鐘聲喚回現實世界。我幾乎每天都沉浸在電動中，從早上八點第一節課玩到五點放學。那天，可能算是某種新月新希望，我心裡突然有個想法：再過不久我就要高三、要考學測了，我是不是該戒電動了? 根據我之前戒電動的經驗，突然把遊戲刪掉是不可行的戒法，過不了幾天我一定會忍耐不住而又故態復萌。因此，我要找一個性質有點類似但不會沉迷的替代品。想來想去，最後決定來學高一時資訊課好像有教過的C++。當時我打的算盤是，從看手機變成看電腦應該也不會很難適應，而且我學個幾天應該就會覺得無聊而放棄了，到那個時候，電動的戒斷症狀應該會輕很多。 那個時候我問同學們要看什麼自學，我同學就推薦了[從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/)，我就開始把原本打電動的時間拿來看這份講義。 ## 從零到十之旅 一開始的幾個章節稱不上是特別有趣，但也不會枯燥到難以下嚥，因此我就姑且看著學著，練習題也順順的寫著。然而，當我寫到 **0-8迴圈** 練習題中 [TOJ 120 Counting Stars](https://toj.tfcis.org/oj/pro/120/) 時，我想破頭也想不出來有什麼辦法能夠避免**TLE**。看了題解後，我被強烈的震撼到了。解答中使用的||前綴和||實在是無比精妙，將耗時的工作經過聰明的轉換有效率地完成。那一刻，我對coding產生了濃厚的興趣，想獲得更多這方面的知識，成為能運用許多巧妙工具的人。 大概花了一個半月，我將從零到一的講義看完了。當中有些練習題難度實在很高(STL篇章中:star::star::star:以上的題目)，甚至看了題解也還是不太會，最後就暫時跳過。這時，我開始認真考慮是不是要繼續學下去，考個APCS檢定，甚至是準備難度更高的比賽。 從零到一的目錄有推薦AP325作為接下來的學習內容，因此我就接著讀。從這時候開始，我分一半讀教材的時間在zerojudge上刷APCS的考古題。雖然常常會遇到寫不出來的題目，不過我認為那段自己什麼都還沒學但還是盡量想題目的時間中，我的思考能力進度很多，為學習AP325無形中提供了不少幫助。其中，我最有印象的是[血緣關係](https://zerojudge.tw/ShowProblem?problemid=b967)，一道古老的APCS實作題p4考古，同時也是樹論中一個重要的例題。我當初刷到這題時，甚至不知道圖或樹這些概念，不過最後在畫一堆例子觀察後唬爛出||兩次dfs||的作法，並且實作完存圖與dfs等功能，終於成功拿到**AC**，開心了好幾天。順帶一提，我是在準備開始讀AP325的時候才終於下載了codeblocks，與之前一直使用的online GDB告別。 AP325是由吳邦一教授寫的，內容非常詳細，讀起來不太有看不懂的問題，其中的題目也幾乎都有辦法完成。花了一個多月，我將AP325讀完了，也練習到許多APCS考古題，我開始往下一個階段前進。 ## CSES, Atcoder, and Codeforces 由於看到很多人推薦，我開始寫[CSES](https://cses.fi/problemset/)上的題目。由於我自己感覺在看完AP325後對DP還是不太熟，因此我從Dynamic Programming開始寫。寫到差不多後，我又把Introductory Problems和Sorting and Searching補掉一些。CSES上的題目幾乎都是經典題，對於新手來說CP值很高，不會被很多奇怪的題目打亂學習進度。 另一方面，我開始接觸線上賽。目前線上賽最有名的平台應該是Codeforces與Atcoder，兩者都會幾乎每週舉辦比賽。不過，Codeforces是俄羅斯平台，由於時區關係，比賽大多是在台灣時間晚上十點以後開始。我因為自己的作息較難配合，大多是參加日本平台Atcoder的比賽。BTW，我在這兩個平台上的handle都是**dnnnda**。 在每個禮拜參加Atcoder比賽的期間，我的實作速度開始顯著變快，最後去寫APCS考古題時都能提早大約半小時寫完，不過有沒有滿分又是另外一回事了。 就這樣，時間默默地來到六月中，我人生中第一場APCS檢定到來。 ## 第一次考APCS 這次的APCS是在6月中，離我開始學寫程式已經有三個半月了。當時，我自認練習得相當充分，想要一舉拿下實作五級分，甚至還跟同學打賭，如果拿到實作五級就要來寫心得文紀錄。 考試分上下午，上午考觀念，下午考實作。考前，我有去官網上下載觀念題的參考試題，寫完後覺得觀念題要一起拿五級應該也有機會。不過，這樣的想法在第一節觀念題開考後就消失殆盡。之前有看過很多我覺得很厲害的人考APCS成績都是觀念4實作5，那時候我還覺得很疑惑，但在我看到觀念題的題目後才明白為什麼會這樣。 觀念題的題目比之前寫的參考試題更難，也更機車。不同於自己寫程式，觀念題需要看懂別人的coding邏輯，才有辦法快速知道一段程式執行後的結果。如果沒辦法由程式碼中的變數名稱等提示看出題目中程式的意義，考生就得化作機器，逐行執行程式碼，才有辦法得出正確答案。 最討厭的是，有些程式並沒有特定目的，單純就是要考倒考生，甚至很多題目都有兩個以上函式互相呼叫的遞迴，讓直接模擬程式執行窒礙難行。除此之外，很多題目中都會有故意寫得很醜甚至是寫錯的寫法，例如： ```c++ //正常人的寫法 swap(a,b); //考試中會見識到的寫法 void swap(int& a, int& b){ int c=a; int d=b; a=a*b; b=b*a; a=a/c; b=b/d; b=b/d; return; } //考試中會有的錯誤寫法 void swap(int a, int b){ int c=a; a=b; b=c; return; } ``` 連swap(a,b)這樣基本的操作都可以玩出這麼多花樣，各位讀者應該不難想像以各種被亂寫的基本操作組合而成的題目，惡意有多明顯。總而言之，當我親自進入到考場後，就知道為什麼許多學校的APCS組都不會對將觀念題成績篩選，而只要求基本門檻了。 在結束早上兩節莫名其妙的觀念題考試後，來到午餐時間。由於我和我同學考完後都會討論題目，往餐廳移動的速度較慢，我們來到餐廳區時早就沒位置了。我們選定了一間看起來排隊的隊伍比較短的餐廳，在外面焦急地等了一段時間後，總算是成功拿到吃的，並且成功在下午時做題開考前解決掉。 時間到，我們進入考場，實作題測驗開始。前幾分鐘，我刻意放慢速度，仔細看清楚題目之前寫的作答說明，希望保持冷靜。這時候，我發現一件預期之外的事情：題本上要求考生將交出去的C++檔案以P1.cpp~P4.cpp命名。我在家練習時寫不同的題目都會共用一個檔案，因此不會遇到檔名問題，而意外就此展開。 我的[P1](https://zerojudge.tw/ShowProblem?problemid=o076)和[P2](https://zerojudge.tw/ShowProblem?problemid=o077)都是新開一個檔案寫，寫完就儲存、上傳，大概共花了30分鐘。接著，我在寫[P3](https://zerojudge.tw/ShowProblem?problemid=o078)的時候，使用了substr這個函式來拿取S的各個子字串，搭配set來完成問題。這時，時間還剩下90分鐘，我感覺一切順利，應該可以穩穩拿到5分，打開了[P4](https://zerojudge.tw/ShowProblem?problemid=o079)的題本。在看到題目的當下我有點呆住，沒什麼方向，思考過程中有想過是不是Greedy, DP或其他東西，最後在想了20分鐘左右想到了一個Sliding Windows的解並開始在P3.cpp中實作。 實作過程算順利，在本地跑範測也都沒問題，準備存檔時，我發現我寫P4的時候忘記開新檔案了，我直接把P3.cpp裡面的code刪掉然後寫在那裡面。因此，我想要另存新檔成P4.cpp。然而，這時候我另存新檔不知道遇上什麼問題，反正就是在講說我不能把這個檔案存成P4.cpp。 由於我覺得codeblocks不能一次開兩個檔案，我就把P4的code複製下來，把檔案關掉，準備把code貼在新開的檔案中。結果，我要貼上時發現`ctrl`+`v`按了一直沒反應，試了幾次後，我意識到我剛剛可能沒有複製成功。但是，我剛剛並沒有將P4的code存下來，因為我覺得我有把它複製到剪貼簿了所以不需要。也就是說，我的一頓操作讓我丟失了一份寫好的code。我看向時間，還剩下50多分鐘。我快速重整了一下心情，開始在新開的檔案中重現我剛剛寫的P4 code。 寫著寫著，我發現我不小心切到半形全形了。悲劇的是，我自己練習時從來沒有不小心按到過`shift`+`空白`，因此根本不知道要怎麼切換回去。我舉手請監考人員過來，並且說明狀況。他看了看，請另外一位監考人員去隔壁教室帶某個人過來幫忙。我焦急地等著，終於一個看起來蠻專業的人出現了。我再說了一次我的問題，然而他似乎也不知道怎麼辦，只在我的筆電上嘗試各種按鍵組合。大概兩分鐘以後吧，他賽到了。我的電腦終於可以正常打出半形英文。我趕緊把握時間，以我最快的速度寫code。 P4的code寫完第二次了，不過這次範測怎麼樣都跑不過。由於電腦並沒有提供在平常可以輸入input的地方貼上的功能，因此每次我修改一個地方，看有沒有成功時，我都要手動輸入範測。禍不單行，在某次輸入範測時，我又手賤按到東西。這次是按到`insert`，切換成了[覆蓋模式](https://zh.wikipedia.org/zh-tw/%E6%8F%92%E5%85%A5%E9%94%AE)。我又舉手請到那位幫我解除全形的工作人員，然而，這次他在一陣亂按以後表示他也不知道怎麼辦，我就只能在這樣的模式中修改程式碼。如果不是在debug時戳到這個東西，情況或許還不會那麼糟。 又過了一陣子，我找到P4的bug了，在修好以後順利通過範測並上傳成功。這時，我再次看向之前寫的code，做最後的double check。當我看到P3的substr函式時，我突然想到之前有看過一個說法是substr的時間複雜度是 $O(原字串長)$ 而非 $O(取的字串長)$ ，因此我的作法會拿到**TLE**。那時，我又想到字串可能會將很多本來是 $O(1)$ 的操作變成 $O(length)$，我就開始懷疑我把所有東西丟到set這個操作的時間複雜度會不會是 $O(LK^Llog(LK^L))$。算一算如果真的是這樣的話就相當於是n開到4.8e6的 $O(nlogn)$，帶的log還是set的log。我那時候不知道師大的judge到底能不能在一秒內跑過這樣常數偏大的東西，因此我決定自己刻非10進位的整數系統，將字串轉成數字後再丟入set中，讓整體複雜度降到 $O(LK^L+K^Llog(K^L))$。 最後的時間中，我把舊的P3.cpp刪掉、新開了一個P3.cpp，火力全開開始寫code。這次寫的過程也還算順利，範測都一次就過，我把code存檔、上傳到系統上後，看到在時間剩下2秒的時候系統顯示上傳成功，我也鬆了一大口氣。 出來後，我開始與同學討論，努力回想自己的code有沒有地方燒雞。突然，我想到最後p3我在寫字串轉整數時，為了方便把進制固定為11進制，而且我還是1-based的位數算法，因此int會overflow。可是我在場內並沒有注意到這個問題。總而言之，我的P3吃爆overflow造成的**WA**。 最後，這場APCS就以4+4級分(72+320)告終。~~在此建議大家考APCS的時候#define int long long~~。 ## 暑假，大家都在讀學測 當初入坑時，我本來打算看能不能一次拿到APCS實作5級，接下來就專心準備學測，不過被深深吸引的我直接當作沒這回事，開始思考讀學測與繼續學程式並行的可能性。 二升三的暑假是準備學測的一段重要的時間，我不可能像以前一樣完全不管課業，每天只寫程式。六月底，我跟自己立下了一個約定：我要在七月把物理、化學、生物的複習講義寫完，把數學進度推到第一次模考範圍，並且同時認真讀英文補習班的東西。如果我七月的進度有達標，我的八月就要把時間分一半給coding(剩下一半讀地科)。 就這樣，為了能在八月時壓力比較小，我七月每天都到學校全天自習、爆刷複習講義。早上九點左右就到學校，自習到中午就和Alex, Max, 和 Arthur三個大捲王去買午餐。晚上的時候有時候會有人先走，但是我都會留到九點。那時候各科講義加起來每天都會寫大概7、80頁，雖然蠻累的但有設定一個目標就會很有動力。 最後，我七月的目標達成，八月的時候就開始繼續寫CSES，並且在TIOJ上開始寫校內能力賽初選考古題，為開學後的能力賽做準備。我學了線段樹和BIT，去寫了CSES的Range Queries，不過寫到Salary Queries和Prefix Sum Queries的時候發現我兩題都寫不出來，就先把Range Quries放到一邊，先去寫Graph Algorithms和Tree Algorithms。 Graph的題目我寫到一半覺得寫不下去，就跑去寫Tree了。Tree其實有很多都是dp，前一半的題目難度不大，寫完以後我戳了一些解，學會HLD和樹上啟發式後又做了剩下的一半，目前剩下兩題重剖還沒做。~~我好像應該先去學重剖而不是寫blog。~~ 開學前，我感覺有很多東西要學，但沒辦法全部在校內能力賽前學完，因此我就去問pacybwoah要先學什麼，當時他這樣跟我說：//待補 所以我就去繼續寫Range Quries，想說要寫到懶標的地方。最後只留下Increasing Array Queries, Polynomial Queries和Range Queries and Copies沒有做出來。 ## 校內能力競賽 :::warning :warning: :warning: :warning: 警告：前方將有113建中資訊能力賽初賽+複賽暴雷 :warning: :warning: :warning: ::: 分為初賽和複賽，題目是由已經可以外加進北市賽的pacybwoah和owoovo準備，我們學校總共可以選出11+2個人去打北市賽。 [初賽](https://tioj.ck.tp.edu.tw/contests/100)開始20分鐘後，我把AB拿走，開始看後面的題目。我先戳了CD，看了看覺得C拿走25分就差不多了，D感覺有機會拿49。我先寫比較簡單的25分C，順利拿到後開始想49分D。49分D的1D/1D寫完以後出了一點bug，一直找不到。大概寫了一個小時我出去上了個廁所，回來以後bug就神奇的被找到了。看了看計分板，我要進複賽應該很穩，就跑去看了E。雖然E的題目看起來很複雜，但有56分的subtask附帶了$a_i=b_i$ 這個很強的條件。有這個條件後這題就變成簡單的Dijkstra，最後我在原訂比賽結束時間前15分鐘做完，順利拿到56分。 初賽的線是200多分，我順利以第五名的成績進入複賽。 初賽結束後，我開始寫複賽考古，發現總共五題的比賽我基本上拿不到任何**AC**。不過後來我知道複賽的線其實大概都是100多分，也就是說如果子題有好好撈，就算拿不到**AC**也會過。這段期間，第一階段培訓展開，課我(應該)都有好好上，有一次owoovo還教會我之前一直寫不過的[Elevator Rides](https://cses.fi/problemset/task/1653)。 複賽前，我感覺自己應該穩了。在寫考古題的時候幾乎每年都有在線上，初賽也喇分喇到第五名。複賽前一天，我去考了高二時很想進但沒進的數學能力賽校內培訓最終選拔，考出來跟同學對一對分數我就知道我數學校隊應該會有，整個人開始膨脹。晚自習時，還跟cactus分享我寫考古題的時候發展出的做題策略： > 一開始先把所有題目看一遍，規劃好順序後再開始寫。看題目的時候，每題至少要停留五分鐘，因為我們常常看到很複雜的題敘就想跳過而沒注意到一些很好拿的分數。五分鐘的停留期間可以逼自己耐著性子理解題目並做出初步思考，接下來在規劃做題順序的時候會比較有方向。雖然開場就噴掉快半小時看題目，不過我覺得這樣花時間是值得的，因為這樣不太容易漏掉該蹭沒蹭到的分。 [複賽](https://tioj.ck.tp.edu.tw/contests/102)當天，我不知道哪來的想法，決定今天開場看題時間縮短到3分鐘以留更多時間給實作。各花3分鐘看完AB以後，我覺得我想到B滿分解了，就直接開始實作B而沒有去看C。那時候我寫線段樹的動作不算快，但我心裡想我做出這100分就穩了，因此整個人很chill。寫完跑範測以後，發現答案算錯了。我一步一步跟著算，才發現原來我一開始的想法是錯的！我整個人開始超級慌張，因為這時候已經過了快一個小時，而我這段時間內我還有3題沒看也沒有拿到任何分數。在勉強寫掉B的13分後，我開始繼續看題。 我開C出來看，看完只想到 $O(NM^4)$ 的dp和其他小子題。我開小算盤覺得$70^5$有點太大應該不會過，所以就先丟著。DE都是看完後幾乎沒什麼想就跳過了。我那時覺得，目前幾乎還沒拿到分，也沒什麼子題會寫，如果A沒想辦法拿滿可能很難進，於是目標訂成做出A的100分。 回去看了幾眼A，覺得應該怎麼樣都會用到隨機。可是，我那時候完全不會隨機的語法，只隱約記得time(0)好像可以吐出一個隨機數，因此我開始絞盡腦汁想要怎麼實作隨機的功能，後來，我用快速冪mod一個質數勉強算是實現了隨機，但是時間也逐漸流逝。 我發現我的目標是要找到0，在那之後感覺就很簡單了。後來，我想出一個很詭異的方法，有機會可以找到0，也想到可以問(a,a,b)來得知a和b的大小關係。不過我做法爛掉，不是一直把兩個數抓出來，然後把比較大的數字從0的候選名單中剔除，而是讓目前所有的0的候選位置跟某個random出來的基準比大小，如果比基準大就刪掉。但是，因為我的作法很爛、隨機數很爛，加上運氣不是特別好，我一直拿到**WA**20分，也就是一直沒蹭到後面大子題的分數。不過我太急、太緊張，沒有好好思考，發現其實有更簡單也更穩定的方法。接下來的一個小時，我就陷在debug pA的死胡同中。期間我有去撈pE的7分，然後吃爆WA就又跑回來A。 最後時間到了以後我只有61分，很明顯在線下:sob:。一個有好好撈分的例子是cactus，壓線進入校隊。說起來也是蠻可惜的，cactus這個要讀醫科的人主力拚的生物校隊沒進，意外進了資訊校隊；我努力想進的資訊校隊沒進，去考好玩的數學校隊反而進了$\dots\dots$ :::info ### 賽後檢討 這次有幾個燒雞點，照發生的時間列出如下： - 亂膨脹 - 做跟原定策略不一樣的時間分配 - 想完B以後沒先對範測而直接實作，導致浪費過多時間 - 由於時間浪費太多，策略又跟平常不同，整個人開始很慌張，接下來整場比賽直接降智 - C沒想到$70^5$有機會過 - D沒想到Dijkstra可以這樣用、對二分搜不敏感 - E沒好好看題目和子題，miss掉7+26分很好拿的分 - A大耍笨 我那時候的能力就有機會拿到但沒拿到的分數： A大概40 C 27分的$70^5$ D 21分二分搜 (0~21分Dijkstra) E 33分簡單分 然後B有27分竟然剛好是我之前寫CSES Range Queries跳過的Increasing Array Queries:sob: 從這個慘劇中，我知道了以後最好不要賽中亂改之前想好的策略、相信不會被卡常。 ::: ## 複賽後~~頹廢~~回復期 複賽死的這麼難看，我心裡當然不太高興，跑去看之前一直沒看的莉可麗絲回復能量(雖然後半的劇情其實get不太到)。遇到不愉快的事情時，似乎可以透過填充喜歡的東西或正能量的東西來暫時緩解情緒，但總是會有需要自己面對、治癒的部分。不過那個時候，我把這些暫時往後搬，畢竟莫名其妙進了數學校隊，當然開始準備數學北市賽，也趁這個機會沉澱一下。 北市賽結束，我拿了三等獎，對我來說很不錯。我自認有賽前盡全力準備比賽、賽中努力蹭分，不過如果去北市賽只拿個佳作甚至沒有獎感覺看起來很像只是來占名額的；如果我拿了二等獎，後面還有全國賽，而我不知道自己能不能在學測這個主線外，同時負荷數學和資訊兩個支線。 從我開始學C++以後，很多人都說我進步很快，而我自己也這麼認為。我覺得，我擁有不錯的資質，付出很多時間、心力在學習程式上，還身處一個有豐沛學習資源的環境。就算我起步比別人晚，應該也能打出不錯的成績。但是，我去考APCS沒拿到五級、比校內賽又被刷掉，讓我開始懷疑自己是不是不夠努力，有時候想這些的時候又會開始想自己是不是也沒有到那麼喜歡coding。 在我糾結這些時，接住我的是之前打日麻時鍛鍊出的心態。日麻是一個玩家就算擁有強大技術，也可能在短期內被運氣擊倒的遊戲。日麻圈中流傳著一句話：100個半莊都算是短期波動。就算自己不斷碰壁、選擇的策略或打法被結果否定，只要那是對的，我們都應該要堅持下去，如此才能在長期取得更好的結果。我跳出我的第一人稱視角，發現我的處境可能就像是一個剛入坑麻雀就連吃兩把四的新手玩家。如果我身邊有這樣的人，我一定會跟他解釋那是短期波動，並請他堅持下去。現在，我就是那個剛入坑就連吃兩把四的人，只要我有在失敗中找出問題，持續喜歡著這項活動並堅持下去，短期的結果就不那麼值得在意。雖然這其中可能有許多槽點，但我的感性接受了這樣子的說法。 我重新站了起來。 ## 第二次考APCS 這次考試前，我還是覺得這次我可以五級。這次沒什麼新奇的點，除了實作的P3把我嗆翻。我賽中想不到複雜度很好的實作方式，因此我寫了一個感覺常數有點危險的方法。因為不想被卡常，我在裡面加了幾個常數優化，但最後跑他的範測都吃爆**WA**。 明明在本地跑的時候範測都有過，為什麼傳上去就**WA**?我專注思考這個問題，一次又一次測試那些可能在不同環境會有不同行為的指令，但沒有找到。結束後，我同學告訴我這次題本中的範測跟他幫我跑的範測是不一樣的，而且這個資訊有寫在注意事項中。因為已經不是第一次來考，所以我就沒有好好看注意事項，沒想到兩次的內容竟然不一樣，而且還是差在一個這麼關鍵的地方。看來，我是有其他地方寫爛，但我沒找到，想當然耳，這次實作又沒拿到五級。 ## 啊啊啊要學測了啊啊啊 學測剩大概三個月，壓力漸漸變大，我雖然感覺自己還沒做足準備，但卻不願意放棄coding這個斜槓。我不像Arthur或Brian他們一樣，可以把自己逼得很緊來讀書，我需要可以轉換心情的活動。對以前的我來說，是電動；但對現在的我來說，是寫code。 讀書讀累了就去kenkoooo上戳一題1600左右的來想，是我、cactus和Steven一起享受的活動。 ## 第三次考APCS 這場APCS跟上一場時間間隔不大，因此幾乎是上一場公布成績後沒多久就開放本場報名了。之前考APCS我都是準時早上九點上去搶考場，不過這次是Andrew當天中午提醒我我才知道要報名，那時台北只受下銘傳大學(要爬一點山)的考場了，不過我和Steven還是決定去考。 這是我申請入學前最後一次APCS，我抱著一定要考到實作五級分的決心參加(：啊以前不是也這樣說？)總之我這次多學了random相關的東西，讓我可以在場內自己生測資對拍，希望可以把最後多出來的時間兌換成分數期望值。 這場的觀念題難度有明顯下降，沒那麼多噁心的東西，看起來終於像觀念題該有的樣子了。中午，我和Steven下山找東西吃，結果最後也是吃捷運站的麵包店和便利商店，早知道應該多帶一點肉乾之類的東西。 實作題一二題還是不難，大概花了十分鐘寫掉。看[第三題](https://zerojudge.tw/ShowProblem?problemid=q183)的時候花了一點時間才理解題目在講什麼，理解以後也還沒什麼想法，想了一陣子以後就先去寫第四題。第四題不難，寫掉以後再回來第三題時，我右上角的倒數時間還有100多分鐘。在有這麼多時間的情況下只要寫出一題，我瞬間感覺放鬆不少。 由於真的沒什麼想法，我就先猜複雜度。由於 $n\le25$，我就先猜了比較有可能是 $O(2^n)$、$O(n\cdot2^n)$，備取複雜度是$O(n^4C)$ 之類的。一頓觀察後，我找到一個可能會讓複雜度裡面出現$2^n$的性質，我就開始繼續往這方面想。這時候我眼前的倒數時間已經從100多、90多，緩慢下降為80多了。 後來，我想出一個感覺蠻好時做的辦法。理論複雜度可能是$O((n+C)\cdot 2^n)$，不過我感覺要跑滿應該很難，就加了一些剪枝下去寫，我覺得寫的還算乾淨： ```cpp=1 #include using namespace std; int cnt[105], n, k; vector v, mn, mx; void solve(int t){ if(v.size()==n){ vector temp=v; sort(temp.begin(),temp.end()); mn=min(mn,temp); mx=max(mx,temp); return; } while(cnt[t]==0) t--; for(int T=0, u=t ; T<2 ; T++, u=k-t){ bool ok=1; for(int i:v) if(--cnt[abs(i-u)]<0) ok=0; if(ok){ v.push_back(u); solve(t); v.pop_back(); } for(int i:v) cnt[abs(i-u)]++; } } signed main(){ cin >> n; if(n==1){ cout << "0\n0\n"; return 0; } vector small(n,100), big(n,0); mn=small, mx=big; for(int i=1 ; i> u; cnt[u]++; } cin >> k; v.push_back(0); v.push_back(k); solve(100); for(int i=0 ; i10000的題目，有時間再上zerojudge搜尋APCS把考古題刷一刷。這些都做完基本上就能五級了。當然，不用全部做也有機會有五級分，但就做越多越有機會。 ### 關於zerojudge 可能有一些人會推薦/被推薦zerojudge這個網站，不過我個人不建議新手去上面刷題。zerojudge上的題目品質參差不齊，容易戳到沒營養或難度過低或過高的題目。不過有時候，有些講義開出題單有一部份的題目會在zerojudge上面，這種時候上去寫挑過的題就沒什麼關係。然而，送完解答以後可能會看到其他人在嘗試的題目，就會想要試試看，不過我覺得這通常沒什麼意義。如果想要有闖關、一題一題刷滿某個題庫的感覺，我強烈推薦[CSES](https://cses.fi/problemset/list/)。 ## (某個年紀)才開始學會不會太晚? 不會。只要有興趣，什麼時候開始都不嫌晚。當然，越晚起步會越辛苦，畢竟時間會比別人少，可以參加的比賽也比別人少，但是，只要有興趣，就跟他拚了吧! ## 要怎麼平衡課業與程式 這是個好問題。我們一天如果睡八小時，醒來的時間就有十六小時。扣掉吃飯、洗澡之類的不可利用時間，至少還會剩下十二小時。如果這些時間都能夠被好好利用，那顧好課業和程式應該綽綽有餘。當然，現實中可能會遇到不能體諒你上課做其他課的老師、你想要進行一些休閒娛樂之類的，那這就要看個人的造化以及願意付出的心力了。