APCS 實作滿級完全攻略

APCS 2023 10 月題解

這次 APCS 跟 ISSC 撞期然後我就放掉 APCS 跑去打 ISSC : D 下一次要慢三天才能報了 qwq數線上有一隻老鼠且有 n 個食物散落在數線上老鼠可以選擇一直往左或一直往右求最多可以吃到幾個食物及最後吃食物的位置把問題轉換一下就變成是在問老鼠左邊還是右邊食物比較多、最左邊或最右邊的食物在哪裡於是只要簡單維護一下就可以幾個變數就可以解出來了基本語法cppusing 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 = maxmaxv, tmp; minv = minminv, tmp; } if cntl cntr cout cntl " " minv endl; 往做邊走解更優 else cout cntr " " maxv endl; 否則決定往右邊走}在一個 n times m 大小的表格上每格裡都有一張牌你可以水平或垂直消除數值為 x 的兩張牌並獲得 x 分，但中間不能有其他牌求最多能獲得多少分枚舉每張牌，嘗試上或左匹配是否存在相同的牌即可使用 -1 紀錄已經匹配掉的牌至於為什麼只要匹配左上不用考慮右下是因為左跟右、還有上跟下是相對關係我比較在意的地方是本來以為這個動作需要重複多次才能匹配所有牌結果竟然一次就過了，不知道是不是 ZeroJudge 測資太弱 🤔或者其實有辦法證明這個作法最多只需要一次更新關於這個問題，感謝 MSQRT 電神的補充確實 Zerojudge 測資有疏失已加強程式碼！二維陣列、模擬cppusing namespace std;int tb5050; 表格signed main { int n, m; cin n m; 輸入資料 for int i = 0; i n; i++ { for int j = 0; j m; j++ { cin tbij; } } int ans = 0; 重複執行匹配動作至少 nm 次以配對所有卡牌 for int = 0; 1000; ++ { for int i = 0; i n; i++ { for int j = 0; j m; j++ { if tbij == -1 continue; 嘗試往上配對 if i 0 { int k = i-1; while k = 0 tbkj == -1 k--; if tbij == tbkj { 配對成功 ans += tbij; 增加分數 tbij = tbkj = -1; 將兩張牌紀錄乘已匹配 continue; 匹配成功後即可忽略這張牌 } } 嘗試往左配對 if j 0 { int k = j-1; while k = 0 tbik == -1 k--; if tbij == tbik { 配對成功 ans += tbij; 增加分數 tbik = tbij = -1; 將兩張牌紀錄乘已匹配 continue; 匹配成功後即可忽略這張牌 } } } } } cout ans endl;}一個 n times m 的表格上每格有一個水管水管分成 H、I、F、7、L 等類型每種水管可能連接到上、下、左、右其中某些方向求將水管連起來後最大連通塊本題詳細題意建議直接進 ZeroJudge 題目頁面查看簡單來說只要對整張圖做 DFS 並一邊維護連通塊大小即可比較麻煩的地方就是建圖而已這份程式碼部份參考了 dreamoon 老師的 code 才得以把它改得這麼乾淨的時間複雜度 Onm圖論、DFS BFScppusing namespace std; 上右下左mapchar, vectorint 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}},};vectorint graph500000; 存圖bool vis500000; 紀錄造訪過的點int ans = 0, cur = 0;int n, m; 對每座標分配一個 idint id int x, int y { return x m + y;} DFS 並維護連通塊大小void dfsint id { cur++; visid = true; for auto u : graphid { if visu continue; visu = true; dfsu; }}signed main { cin n m; vectorstring vn; for int i = 0; i n; i++ cin vi; 建立整張圖 for int i = 0; i n; i++ { for int j = 0; j m; j++ { 上配下 if i + 1 n maskvij2 maskvi + 1j0 { graphidi, j.pushbackidi + 1, j; graphidi + 1, j.pushbackidi, j; } 左配右 if j + 1 m maskvij1 maskvij + 13 { graphidi, j.pushbackidi, j + 1; graphidi, j + 1.pushbackidi, j; } } } 對每一個節點做 DFS for int i = 0; i n; i++ { for int j = 0; j m; j++ { cur = 0; dfsidi, j; ans = maxans, cur; 嘗試更新答案 } } cout ans endl;}題目~~廢話~~劇情就不多寫了簡單來說就是求最大連續子序列合，但可以跳過 k 個元素在不考慮 k 的情況下這是一個非常經典的問題解法的話也非常多元以現在這題來說 Kadane's Algorithm 應該會是比較好做的那如果把 k 的條件加進去呢？把測資範圍仔細讀過之後可以注意到 k leq 20 考慮動態規劃的作法我們定義 dpi 為考慮陣列前 i 個元素的最佳解然後我們可以往前跳過不超過 k 個因此 dpi 可以從 dpi-1、dpi-2 cdots dpi-k-1 轉移過來取 max 但我們還需要紀錄總共已經使用了幾個金牌所以再開一個維度來維護這個資訊綜合以上幾點，我們可以推出這樣的轉移式定義 dpij 為考慮前 i 個元素且使用 j 個金牌的最佳解轉移的部份 dpij = max{1 leq l leq k}dpi-l-1j-l + vali最後照著轉移式把程式寫出來就好ㄌ時間複雜度 On times k^2更新感謝 Colten 提出了更好的作法 dpij 一樣是代表在第 i 天使用 j 個金牌的最佳解不過轉移的部份只需要對 dpi-1j-1 和 dpi-1j + vali 取 max 就可以兩個狀態分別代表在第 i 天使用和不使用金牌時間複雜度直接少了一個 k 降到 On times k 下面程式碼也用這個寫法實現然後根據吳邦一教授的說法原本 On times k^2 的作法如果使用 Python 的話時間應該不會過動態規劃cppusing namespace std;int v200000;int dp20000030;signed main { int n, k; cin n k; for int i = 1; i = n; i++ { 第 i 天 cin vi; 因為只會依賴到之前的狀態所以可以邊讀入邊做 for int j = 0; j = k; j++ { 使用 j 個金牌 if j 0 dpij = dpi-1j-1; 使用金牌 dpij = maxdpij, dpi-1j + vi; 不使用金牌 } } int ans = 0; 在所有合法狀態中取得最佳解 for int i = 0; i = k; i++ { for int j = 1; j = n; j++ { ans = max{ans, dpji, 0LL}; } } cout ans endl;}整體來說這次 APCS 其實不算太難（? 第三題實做比較麻煩一點以外最後一題 DP 轉移式也還算好推

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

題解 CSES Permutations

給予一個數字 n 你要使用數字 1 sim n 構造一個陣列使得不存在任意兩個相鄰數字的差為 1把 n 個數字分成 1 sim lfloor frac{n}{2} rfloor 和 lfloor frac{n}{2}+1 rfloor sim n 兩堆並穿插構造 ans 陣列就可以保證任兩數的差大約為 lfloorfrac{n}{2}rfloor 最後跑過整個陣列驗證是否合法即可cppusing namespace std;signed main { iosbase::syncwithstdiofalse;cin.tie0; int n; cin n; vectorint arrn; dequeint ans; int mid = n2; for int i = 1; i = n2; i ++ { int leftVal = i; int rightVal = mid + i; ans.pushbackrightVal; ans.pushbackleftVal; } if n 1 == 1 { ans.pushfrontmid + n2 +1; } for int i = 0; i n-1; i++ { if absansi+1 - ansi == 1 { cout "NO SOLUTION" endl; return 0 ; } } for int i = 0; i n; i ++ { cout ansi " "; } cout endl;}

CSES

前言

考前注意事項

評分方式

實作第 2 級

出題範圍

練習方式

實作第 3 級

出題範圍

練習方式

實作第 4 ~ 5 級

出題範圍

練習方式

更多的練習

推薦文章

APCS 2023 10 月題解

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

題解 CSES Permutations