最後更新日期 2024 / 01 / 01

APCS 2023 10 月題解

前言

這次 APCS 跟 ISSC 撞期
然後我就放掉 APCS 跑去打 ISSC : D
下一次要慢三天才能報了 qwq

一、機械鼠

https://zerojudge.tw/ShowProblem?problemid=m370

題意

數線上有一隻老鼠
且有 n 個食物散落在數線上
老鼠可以選擇一直往左或一直往右
求最多可以吃到幾個食物及最後吃食物的位置

想法

把問題轉換一下
就變成是在問老鼠左邊還是右邊食物比較多、最左邊或最右邊的食物在哪裡
於是只要簡單維護一下就可以幾個變數就可以解出來了

考點

基本語法

程式碼

#include <bits/stdc++.h>

using namespace std;

signed main() {
    int x, n, tmp;
    cin >> x >> n;
    int cntl = 0, cntr = 0; // 左邊與右邊食物數量
    int maxv = -1e5, minv = 1e5; // 用最大與最小值維護最後停在的食物位置
    while (n--) {
        cin >> tmp;
        if (tmp >= x) cntr++; // 如果食物在左邊
        if (tmp <= x) cntl++; // 如果食物在右邊
        maxv = max(maxv, tmp);
        minv = min(minv, tmp);
    }
    if (cntl > cntr) cout << cntl << " " << minv << endl; // 往做邊走解更優
    else cout << cntr << " " << maxv << endl; // 否則決定往右邊走
}

二、卡牌遊戲

https://zerojudge.tw/ShowProblem?problemid=m371

題意

在一個 n×m 大小的表格上每格裡都有一張牌
你可以水平或垂直消除數值為 x 的兩張牌並獲得 x 分,但中間不能有其他牌
求最多能獲得多少分

想法

枚舉每張牌,嘗試上或左匹配是否存在相同的牌即可
使用 1 紀錄已經匹配掉的牌

至於為什麼只要匹配左上不用考慮右下
是因為左跟右、還有上跟下是相對關係

我比較在意的地方是
本來以為這個動作需要重複多次才能匹配所有牌
結果竟然一次就過了,不知道是不是 ZeroJudge 測資太弱 🤔
或者其實有辦法證明這個作法最多只需要一次

[更新]
關於這個問題,感謝 M_SQRT 電神的補充
確實 Zerojudge 測資有疏失
已加強程式碼!

考點

二維陣列、模擬

程式碼

#include <bits/stdc++.h>

using namespace std;

int tb[50][50]; // 表格

signed main() {
    int n, m;
    cin >> n >> m;
    // 輸入資料
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tb[i][j];
        }
    }
    int ans = 0;
    // 重複執行匹配動作至少 n*m 次以配對所有卡牌
    for (int _ = 0; _ < 1000; _++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tb[i][j] == -1) continue;
                // 嘗試往上配對
                if (i > 0) {
                    int k = i-1;
                    while (k >= 0 && tb[k][j] == -1) k--;
                    if (tb[i][j] == tb[k][j]) {
                        // 配對成功
                        ans += tb[i][j]; // 增加分數
                        tb[i][j] = tb[k][j] = -1; // 將兩張牌紀錄乘已匹配
                        continue; // 匹配成功後即可忽略這張牌
                    }
                }
                // 嘗試往左配對
                if (j > 0) {
                    int k = j-1;
                    while (k >= 0 && tb[i][k] == -1) k--;
                    if (tb[i][j] == tb[i][k]) {
                        // 配對成功
                        ans += tb[i][j]; // 增加分數
                        tb[i][k] = tb[i][j] = -1; // 將兩張牌紀錄乘已匹配
                        continue; // 匹配成功後即可忽略這張牌
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

三、搬家

https://zerojudge.tw/ShowProblem?problemid=m372

題意

一個 n×m 的表格上每格有一個水管
水管分成 HIF7L 等類型
每種水管可能連接到上、下、左、右其中某些方向
求將水管連起來後最大連通塊

*本題詳細題意建議直接進 ZeroJudge 題目頁面查看

想法

簡單來說只要對整張圖做 DFS 並一邊維護連通塊大小即可
比較麻煩的地方就是建圖而已
這份程式碼部份參考了 dreamoon 老師的 code 才得以把它改得這麼乾淨的 ><

時間複雜度 O(nm)

考點

圖論、DFS / BFS

程式碼

#include <bits/stdc++.h>

using namespace std;

// 上 右 下 左
map<char, vector<int>> mask{
    {'X', {1,1,1,1}},
    {'I', {1,0,1,0}},
    {'H', {0,1,0,1}},
    {'L', {1,1,0,0}},
    {'7', {0,0,1,1}},
    {'F', {0,1,1,0}},
    {'J', {1,0,0,1}},
    {'0', {0,0,0,0}},
};

vector<int> graph[500000]; // 存圖
bool vis[500000]; // 紀錄造訪過的點
int ans = 0, cur = 0;
int n, m;

// 對每座標分配一個 id
int id (int x, int y) {
    return x * m + y;
}

// DFS 並維護連通塊大小
void dfs(int id) {
    cur++;
    vis[id] = true;
    for (auto &u : graph[id]) {
        if (vis[u]) continue;
        vis[u] = true;
        dfs(u);
    }
}

signed main() {
    cin >> n >> m;
    vector<string> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    // 建立整張圖
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 上配下
            if (i + 1 < n && mask[v[i][j]][2] && mask[v[i + 1][j]][0]) {
                graph[id(i, j)].push_back(id(i + 1, j));
                graph[id(i + 1, j)].push_back(id(i, j));
            }
            // 左配右
            if (j + 1 < m && mask[v[i][j]][1] && mask[v[i][j + 1]][3]) {
                graph[id(i, j)].push_back(id(i, j + 1));
                graph[id(i, j + 1)].push_back(id(i, j));
            }
        }
    }
    // 對每一個節點做 DFS
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cur = 0;
            dfs(id(i, j));
            ans = max(ans, cur); // 嘗試更新答案
        }
    }
    cout << ans << endl;
}

四、投資遊戲

https://zerojudge.tw/ShowProblem?problemid=m373

題意

題目廢話劇情就不多寫了
簡單來說就是求最大連續子序列合,但可以跳過 k 個元素

想法

在不考慮 k 的情況下
這是一個非常經典的問題
解法的話也非常多元
以現在這題來說 Kadane's Algorithm 應該會是比較好做的

那如果把 k 的條件加進去呢?
把測資範圍仔細讀過之後可以注意到 k20
考慮動態規劃的作法
我們定義 dp[i] 為考慮陣列前 i 個元素的最佳解
然後我們可以往前跳過不超過 k
因此 dp[i] 可以從 dp[i1]dp[i2]dp[ik1] 轉移過來取 max
但我們還需要紀錄總共已經使用了幾個金牌
所以再開一個維度來維護這個資訊

綜合以上幾點,我們可以推出這樣的轉移式
定義 dp[i][j] 為考慮前 i 個元素且使用 j 個金牌的最佳解
轉移的部份 dp[i][j]=max1lk(dp[il1][jl]+val[i])

最後照著轉移式把程式寫出來就好ㄌ

時間複雜度 O(n×k2)

[更新]

感謝 Colten 提出了 更好的作法
dp[i][j] 一樣是代表在第 i 天使用 j 個金牌的最佳解
不過轉移的部份只需要對 dp[i1][j1]dp[i1][j]+val[i]max 就可以
兩個狀態分別代表在第 i 天使用和不使用金牌
時間複雜度直接少了一個 k 降到 O(n×k)
下面程式碼也用這個寫法實現

然後根據 吳邦一教授的說法
原本 O(n×k2) 的作法如果使用 Python 的話時間應該不會過

考點

動態規劃

程式碼

#include <bits/stdc++.h>
#define int long long

using namespace std;

int v[200000];
int dp[200000][30];

signed main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) { // 第 i 天
        cin >> v[i]; // 因為只會依賴到之前的狀態所以可以邊讀入邊做
        for (int j = 0; j <= k; j++) { // 使用 j 個金牌
            if (j > 0) dp[i][j] = dp[i-1][j-1]; // 使用金牌
            dp[i][j] = max(dp[i][j], dp[i-1][j] + v[i]); // 不使用金牌
        }
    }
    int ans = 0;
    // 在所有合法狀態中取得最佳解
    for (int i = 0; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            ans = max({ans, dp[j][i], 0LL});
        }
    }
    cout << ans << endl;
}

結語

整體來說
這次 APCS 其實不算太難(?
第三題實做比較麻煩一點以外
最後一題 DP 轉移式也還算好推

推薦文章

APCS 實作滿級完全攻略

筆者只是一個滿級的考生 以下內容都是根據個人經驗給出的建議考試名額不多 很快就會被搶完 所以開放報名第一時間記得趕快上去搶然後第一次應考前一定要先下載官方的虛擬環境 並且留意自己習慣的編輯器、IDE 有沒有在環境裡面 如果沒有的話就要事先練習好其他軟體的操作方式APCS 的實作題每次考試總共會有 4 題 每題 20 筆測資 每筆測資只要對了就可以獲得 5 分 所以就算沒辦法拿滿分 寫多少算多少 一定要傳上去- 基本程式語法如果只是要拿二級的話 其實練習方式還蠻廣的 基本上所有"會寫程式的人"都可以達到這個等級 也就是說 不管你想去寫網頁、開發遊戲、刷題目都應該可以達到 2 級這個目標- 二維陣列- 複雜模擬APCS 的 3 級範圍非常吃實作能力 需要邏輯清晰且可以處理複雜的操作才能達到 3 級 一個比較複雜的例子:APCS 202210 貨運站 而且在第二題當中 二維陣列操作出現的的頻率非常高 必須非常熟悉二維陣列 最後建議想達到 3 級分的話可以多練歷屆 APCS 第二題不過如果你的目標是更高的級分 其實不需要刷太多歷屆第二題 通常隨著能力提升實作能力也會自然提升- 排序- 搜尋- 貪心- 遞迴- 動態規劃- 資料結構4 級跟 5 級的範圍其實差不多 不過最大的差別就是要拿到 4 級只需要知道比較淺的知識就行了 那想達到 45 級的話就非常吃演算法和資料結構的運用能力 非常推薦這份 AP325 講義題目的部分 很常出現經典題或者經典題稍微改編 所以也很建議去 CSES 這個很多經典題的 Judge 多刷點題 可以配合 CSES 寶典 一起讀集結了多位 APCS 滿級分的出題者與驗題者 我們在每個月都會辦一場 APCS 模擬賽 如果還不清楚自己練習方向或想測試實力的話 歡迎加入 Discord 群組 重點是完全免費!!

APCS

[題解] TIOJ 2195 粉刷護欄 (TOI 2021 初選 pC)

上下有個有一根木樑 然後中間有 n 條可能會相交的木板 找出最多可以釘上幾條木板並構造最大字典序的解 細節自己去 TIOJ 看 :因為這題看起來沒人寫題解 於是我就發了這篇文章 ouob仔細觀察問題 我們可以把問題轉換成 LIS 或 LCSLCS 的話應該不難理解 因為要釘最多木板其實就是要在上下兩條陣列各選一個共同的子序列 然後把每個數字一一對應釘起來 但是 LCS 需要 On^2 的時間複雜度才能計算 所以一定會 TLE接著是 LIS 的作法 仔細觀察題目的話可以發現 如果木板有"座標"的話 其實我們在做的事情就是"對木板做 LIS" 更精確一點的說 就是我們其實可以把木板在上樑的點跟下樑的點綁成一個 pair 做 LIS 我們說木板 A 的座標小於木板 B 代表 A 的下樑座標跟上樑座標都小於 B至於座標的部分大概就是這個意思: 以附圖為例 木板 3 的座標就是 2, 1 木板 4 的座標就是 5, 3 木板 5 的座標就是 4, 4如果用最普通的 DP 方式 就算能構造解也很難求最大字典序 於是我們修改一下計算方式 把轉移式改成 "定義 dpi 為把第 i 個元當頭素能構造出的 LIS" 其實就只是倒著做 LIS 然後 Increasing 改成 Decreasing 就好了做完 DP 之後 我們要從 dp 值大的開始構造 先找一個 dp 值跟最終 LIS 一樣長而且字典序最大的元素 接著往右找小一點的直到 1 為止關於上面提到的"座標" 實際上不需要真的把座標算出來 我們只需要把第二個陣列代表下梁座標的陣列每一個元素替換成該元素在第一個陣列出現的位置 並對第二個陣列做 LIS 就可以了 ~~原因的話講起來有點麻煩 自己想吧~~第一次傳 WA 了一片 然後 debug 的時後測出這樣的測資會出錯 如果你也找不到你的程式坐在哪裡的話 不仿測試看看這筆測資33 1 21 2 3cppusing namespace std;const int MAXN = 2e5 + 10; map 會超時,所以改 unorderedmapunorderedmapint, int rpos;unorderedmapint, int pos;vectorint lensMAXN;int vMAXN;bool cmpint a, int b { return rposva rposvb;}signed main { io; int n; cin n; for int i = 1; i = n; i++ { int tmp; cin tmp; 紀錄元素座標 postmp = i; } for int i = 1; i = n; i++ { int tmp; cin tmp; 將陣列的值設定為目前元素在上面陣列的出現位置 vi = postmp; 把坐標在映射回他的值,輸出的時候會用到 rpospostmp = tmp; } LIS 的部分 作法類似: int len = 0; vectorint dp; for int i = n; i = 1; i-- { int ans = 0; 儲存目前 dp 值:以 i 為開頭能構造出多長的 LIS if dp.empty || dp.back vi { dp.pushbackvi; 紀錄目前的 dp 值 ans = dp.size; } else { auto ite = upperboundalldp, vi, greaterint; ite = vi; 紀錄目前的 dp 值 ans = ite - dp.begin + 1; } len 維護最終 LIS 長度 len = maxlen, ans; 紀錄每個長度的解 lensans.pushbacki; } 構造解 int cur = 0; for int i = len; i = 1; i-- { 依照字典序做 sort sortalllensi, cmp; for auto j : lensi { 排除在目前選到的元素左邊的元素 if j = cur continue; 排除加入後會相交的元素 用於排除文章中寫的“一個小測資”那段的 Case if vj vcur continue; cur = j; 把 index 映射回去並輸出 cout rposvj " "; break; } }}

TIOJ

Dcard 實習計畫 2024

這次去 SITCON 玩大地遊戲的時候,剛好在 Dcard 攤位看到正在招募 2024 暑期實習計畫的實習生,於是我就過去了跟他們聊了一下,沒想到他們竟然說高中生只要有時間也可以來報名看看,身為自學生的我怎麼能錯過這樣的機會呢!按照實習計畫的說明,在投遞履歷的同時,還需要附上「作業」,而這次的作業內容大概就是要建立一個可登入、發文然後串 Github API 的 blog 網頁。alt text我在開始製作這個作業時,其實對於 React 的了解其實幾乎趨近於零,沒有抱持的太大的期待就開始做下去了,想說就透過這個作業邊寫邊學 React 和 Next.js。過程中其實遇到不少困難,起初就是 useEffect 用得太差,導致出現一堆問題,網路上查了許多資料都沒辦法完美的解決我遇到的困難,直到發現了 A Complete Guide to useEffect 這篇文章,對英文不是很好的我來說,這超長的文章大概也花了我兩天的時間才讀完。幸運的是,這篇文章寫得非常詳細而且解決了我遇到的問題,感覺我就是基礎很不扎實吧。alt text除了 useEffect 以外,還遇到另外一個更棘手的就是 Next.js 的快取問題,每當我發布 blog 文章之後,無論怎麼重新載入我的文章都不會顯示出來。翻了 Next.js 的文件才發現快取系統怎麼這麼複雜,總之後來又花了一些時間把 Next.js 的文件都好好讀一一讀,最終稍微解決了這個問題,但解法似乎不是非常優雅。繳交期限最後一週,我參考了之前 某個被錄取的實習生的作業 寫好了 README.md 文件就交上去了。如果有興趣的話,你可以在 這裏 看到我當時的作業,總共 320 個 commits,我花了整整一個月的時間在上面。作業繳交上去幾天後,很順利的收到了面試通知,那時候看到這個超開心!alt text距離面試時間,還有兩週多,首先我上網查了一些資訊,看看之前的 Dcard 面試到底都做了什麼。因為某篇文章說建議去讀 React 底層的東西,於是我就找了 React 技術揭密 這本電子書來讀,裡面真的提到了非常多很底層的東西,像是什麼 fiber node 之類的,不過最後還是看不太懂qwq,因此放棄了這本書。或許對我來說 React 底層太難了,但我至少可以繼續增進我對 React 的了解,根據前面 Next.js 的學習經驗,我決定要把 React 的文件全部讀過一遍!還在 Obsidian 整理了蠻多的筆記,感覺有機會可以公開出來。alt text大約一週的時間,我把 React 讀得差不多了,過程中其實發現了不少作業中可以優化的地方也改上去了。然後又再回去看一下之前面試的考古題,發現我對 Javascript 的了解似乎也不夠深,尤其時原型練之類的東西。最後根據 某 Javascript 大師 的推薦,讀了 這個系列 的文章,真的挺優質的,很多其他地方看不到的內容裡面都有。這部分我比較多的時間可能都還是在研究原型鏈。alt text接下來也花了一些時間學 git 更進階的指令,這個網站 真的挺有意思的,到後面感覺很像在玩解謎遊戲。alt textgit 的部分也整理了一些筆記,不過沒 React 那麼多就是了。alt text面試前兩三天,繼續查了一下考古題,看看 HR 面試的關卡會做什麼,但好像也沒查到什麼太有用的資訊。結果反而有點不知道要做什麼,於是就去處理了一些雜事,把之前 side project 想加的東西加上去、把還沒發佈的 chrome extension 給 publish 上去有的沒的。大概提前兩個多小時左右就先到了現場,看一下面試地點大概在什麼地方,然後去吃個午餐休息一下,本來想再複習一下結果好像來不及了。進公司之後,他們先跟我介紹了一下 Dcard 的歷史,然後參觀一下工作環境(看起來真的很舒服)。接著迎來的第一關就是 HR 面試。其實氛圍還算滿輕鬆的,不過我還是有點緊張。剛開始有跟他們聊了一下關於我現在自學生的身份和接下來的升學打算,後來還有提到問我是如何學習一項新的技術、以及程式學習的歷程,然後問我短中長期規劃之類的。因為我個人網站上面寫了很多比賽的經歷,他們也根據這個詢問了我一些相關問題,比如為什麼想參加這些比賽、跟隊友賽中的策略怎麼樣等等,在小組合作過程當中的協作模式、有沒有遇過衝突及如何化解有的沒的。這邊其實我覺得很多問題我都沒有回答得很好,或者是思考停頓了太久。alt text下一個階段是 Frontend Team 的面試,他們問了很多關於 React 的問題,包含 useMemo、useCallback、SSR、CSR、await async 跟 promise 差在哪、SSG、server component 跟 client component 的差別等等。比較令我印象深刻的是有一題他們問 server component 跟 server side rendering SSR 差在哪裡,第一瞬間幾乎沒什麼靈感,想說不就是 server component 才會 server rendering 這樣嗎,思考一小段時間之後突然有一點想法回想起來之前在看 Next build 結果的時候就連 client component 也被標示成 SSR,於是我就有點免強的回答說:「client component 也會用到 SSR... 對吧?」,似乎應該是正確答案,不過感覺回答的很不完整。另外一個也讓我思考了蠻久的問題就是「Suspense 在 server component 的運作原理是什麼?它是如何做到載入好後把 fallback 替換成取得到的資料的?」,這題我就真的幾乎完全沒頭緒了,雖然大概給了一點零散地回答剛好提到了 streaming 這個詞,他們就說算是有擦到一點邊,對於這個沒回答出來的問題他們也好心的跟我解釋了 Suspense 到底是怎麼是怎麼運作的。alt text剩下一些沒有回答的很好的問題還有,「有沒有自調整過 webpack 的 config」,我回答沒有,大多數情況下都是用 framework 的 default config。「web vitals 的評分項目」,雖然用過,但我幾乎忘光了。作業的部分他們也提到了我的 blog 頁面的 error handling 沒有做得很好,某個 promise 的 .catch 後面沒判斷就直接接了 notFound。然後 blog 頁面的 cache miss 掉以及我用 Map 實作了奇怪的小 cache 也被抓到,快取的部分真的被問得挺慘的ww還有因為之前的專案都是 Vue 寫的,所以他們也稍微問了一些關於 Vue 的問題,比如說你覺得 Vue 跟 React 差在哪、更喜歡哪個之類的,但其實我現在對 Vue 的了解度應該比 React 還低,這部分也挺慘的。面試最後我問他們我還有什麼地方是可以加強的,他們第一句話就是說我非常優秀,三年能學到這樣已經比很多 Junior 強了(這真的讓我很感動),鼓勵的部分結束後,他們給我的建議是應該再多了解 React、Next 的底層在做什麼,可以常常觀察 Devtools 裡面的 Network Tab 到底傳了什麼東西過來。面試結束後的下一週,他們就寄了審核結果的資訊到我的信箱。alt text打開來看到我沒有錄取,其實當初還蠻失望的,不過仔細這樣回過頭來看看這段時間發生的事,沒有錄取好像也挺合情合理的。至少在這個過程當中我真的學習到了非常多東西,了解到自己許多不足的地方,認識了所謂的「面試」到底是什麼,甚至還讓我從 0 學會了 React 跟 Next XD,再次感謝 Dcard 願意給我這次嘗試的機會 如果沒有 Dcard,我很難想像我可以在兩個月之內成長這麼多!統整一下這段時間發生的事情,首先我認為最明顯的缺點應該就是我對 React 和 Next 技術及經驗還不夠充足,尤其是關於偏底層的部分。再來就是技術面試以外的部分我幾乎不知道怎麼準備,感覺 HR 那關我幾乎都是在亂答,像是他們問說有沒有在合作過程當中遇到衝突然後怎麼處理,我回答幾乎沒有,可能藉由這個答案被判斷成我沒什麼合作經驗(雖然這確實),還有短中長期計畫那題也是想了蠻久的。無論如何,接下來這一年我希望可以:- 寫更多前端技術文章- 更深入了解 React Next 底層技術- 學習 webpack- 學習 redux- 累積更多合作開發的經驗希望明年就可以錄取 Dcard!!!

Journal