這篇有高級和中高級各三題。
APCS 不公布題本,題目是 AA 競程照考生的回憶整理的。高級的三題 ZeroJudge 和 AACPOJ 都可以交,但兩邊有些地方不一樣,先整理在這裡:
| 題目 | 做法 | 兩邊的差別 |
|---|---|---|
| 建造堡壘 | 樹 DP,不用遞迴 | 沒有,同一份程式都能過 |
| 漫遊曼哈頓 | 一列一列 DP | 結束的規則不同,答案的取法要改 |
| 切割相加 | 背包/折半枚舉 |
高級
建造堡壘
題目
想法
把城市 1 當根,每個點記兩個數字:
: 有蓋的時候, 這棵子樹最少花多少 : 沒蓋的時候, 這棵子樹最少花多少
看
沒蓋, 就一定要蓋。
有蓋, 蓋不蓋都可以,選便宜的。
答案是
不寫遞迴
這題用 DFS 遞迴寫最直覺。但考完我在脆上看到蠻多人第一題沒拿滿,我猜是遞迴太深爆掉了:
所以我沒有用遞迴,改成這樣:
- 從城市 1 做 BFS,把走到的順序存在
q,順便記每個點的爸爸p。 - 把
q倒著跑,每個點把自己的值加給爸爸。
BFS 的順序裡爸爸一定排在小孩前面,倒過來就變成小孩一定先算完。
例如路是 1-2、1-3、2-4,BFS 的順序是 1 2 3 4。倒著跑就是 4 加給 2、3 加給 1、2 加給 1,輪到 2 的時候它的小孩 4 已經加完了。
時間複雜度
程式碼
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
IO;
int n;
cin >> n;
vector<vector<int>> v(n + 1);
// dp[1][i]:i 有蓋,dp[0][i]:i 沒蓋
vector<vector<int>> dp(2, vector<int>(n + 1));
for (int i = 1;i <= n;i++) cin >> dp[1][i]; // 花費直接讀進 dp[1]
for (int i = 1;i < n;i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
// 從 1 開始 BFS,q 是走到的順序,p 是每個點的爸爸
vector<int> p(n + 1), q;
vector<bool> vis(n + 1);
q.push_back(1);
vis[1] = 1;
for (int i = 0;i < (int)q.size();i++) {
for (auto nt : v[q[i]]) {
if (vis[nt]) continue;
p[nt] = q[i], vis[nt] = 1;
q.push_back(nt);
}
}
// 倒著跑,小孩一定比爸爸先算完;q[0] 是根,沒有爸爸所以不用跑
for (int i = q.size() - 1;i >= 1;i--) {
dp[1][p[q[i]]] += min(dp[1][q[i]], dp[0][q[i]]); // 爸爸有蓋:小孩蓋不蓋都行
dp[0][p[q[i]]] += dp[1][q[i]]; // 爸爸沒蓋:小孩一定要蓋
}
cout << min(dp[1][1], dp[0][1]);
}漫遊曼哈頓
題目
兩邊差在「在哪裡結束」:
- ZeroJudge:一走到最南邊那一列就結束,不能在那一列橫著走。
- AACPOJ:在哪個路口結束都可以。
我照 ZeroJudge 寫的程式丟到 AACPOJ 會 WA,就是因為這個。
想法
不能往北也不能重複走,所以在同一列裡只能一直往左或一直往右,走完再往下。跟 2020 年 10 月的「勇者修煉」是同一種做法。
一列一列往下算,每一列算三個東西:
dp[j]:剛走進這一列第個路口時的最高分。可能是從正上方下來的,也可能是直接從這裡出發(0 分)。
l[j]、r[j]:從左邊、從右邊一路走到的最高分。
best[j] = max(l[j], r[j]):在這一列走完、停在的最高分,下一列的第 1 步會用到。
兩邊只差在最後答案怎麼取:
- ZeroJudge:最後一列的
dp取最大。到了最後一列就結束,不能再橫著走,所以不是取best。 - AACPOJ:每一列的
best全部取最大。
以 AACPOJ 的範例一來說,最好的走法是到了第二列再往東走四段。用 ZeroJudge 的取法會漏掉這四段,輸出 14,正確答案是 23。
時間複雜度
程式碼(ZeroJudge)
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
IO;
int n, m;
cin >> n >> m;
// row[i][j]:(i, j) 和 (i, j+1) 中間的橫向街道
vector<vector<int>> row(n, vector<int>(m - 1));
for (auto &y : row) for (auto &x : y) cin >> x;
// col[i][j]:(i, j) 和 (i+1, j) 中間的直向街道
vector<vector<int>> col(n - 1, vector<int>(m));
for (auto &y : col) for (auto &x : y) cin >> x;
vector<int> dp(m), l(m), r(m), best(m);
for (int i = 0;i < n;i++) {
// 剛走進這一列:從上面走下來,或是直接從這裡出發
// 第一列上面沒東西,dp 維持 0
for (int j = 0;j < m and i;j++) dp[j] = max(0, best[j] + col[i - 1][j]);
l = dp, r = dp;
// l:從左邊走過來,r:從右邊走過來
for (int j = 1;j < m;j++) l[j] = max(l[j], l[j - 1] + row[i][j - 1]);
for (int j = m - 2;j >= 0;j--) r[j] = max(r[j], r[j + 1] + row[i][j]);
// 在這一列橫著走完、停在 j 的最大分數,給下一列用
for (int j = 0;j < m;j++) best[j] = max(l[j], r[j]);
}
// 走到最後一列就結束,所以看的是 dp 不是 best
cout << *max_element(dp.begin(), dp.end());
}程式碼(AACPOJ)
只多了一個 ans,其他都一樣。
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
IO;
int n, m;
cin >> n >> m;
// row[i][j]:(i, j) 和 (i, j+1) 中間的橫向街道
vector<vector<int>> row(n, vector<int>(m - 1));
for (auto &y : row) for (auto &x : y) cin >> x;
// col[i][j]:(i, j) 和 (i+1, j) 中間的直向街道
vector<vector<int>> col(n - 1, vector<int>(m));
for (auto &y : col) for (auto &x : y) cin >> x;
vector<int> dp(m), l(m), r(m), best(m);
int ans = 0; // 可以一步都不走,所以從 0 開始
for (int i = 0;i < n;i++) {
// 剛走進這一列:從上面走下來,或是直接從這裡出發
// 第一列上面沒東西,dp 維持 0
for (int j = 0;j < m and i;j++) dp[j] = max(0, best[j] + col[i - 1][j]);
l = dp, r = dp;
// l:從左邊走過來,r:從右邊走過來
for (int j = 1;j < m;j++) l[j] = max(l[j], l[j - 1] + row[i][j - 1]);
for (int j = m - 2;j >= 0;j--) r[j] = max(r[j], r[j + 1] + row[i][j]);
// 在這一列橫著走完、停在 j 的最大分數
// 在哪裡結束都可以,所以每個 best 都拿來更新答案
for (int j = 0;j < m;j++) best[j] = max(l[j], r[j]), ans = max(ans, best[j]);
}
cout << ans;
}切割相加
題目
給一個數字字串
例如 1+1+11、1+11+1、11+1+1 三種,所以輸出 13 3。
兩邊差在
- AACPOJ:
,可以用背包。 - ZeroJudge:
沒有給上限,只保證答案在 int 範圍內,也就是可能到二十億左右。背包的陣列開不出來,要用折半枚舉。
解法一:背包(AACPOJ)
dp[i][t]:前 dp[0][0] = 1。
每次決定下一段要拿多長。從第
例如 1+1 或 11,所以 dp[2][2] = 1、dp[2][11] = 1。
算完之後從 dp[n][t] 不是 0 的 dp[n][t] 就是插法數。
插法數要開 long long:題目只保證答案在 int 內,其他格子可能更大(全部的插法有
時間複雜度大約是
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
const long long INF = numeric_limits<int>::max();
signed main() {
string s;
int k;
cin >> s >> k;
int n = s.size();
// dp[i][t]:前 i 個字元切完,總和剛好是 t 的切法數
vector<vector<int>> dp(n + 1, vector<int>(k + 1));
dp[0][0] = 1;
// 下一段拿 s[i..j],數字是 x
for (int i = 0;i < n;i++) for (int j = i, x = 0;j < n;j++) {
x = x * 10 + (s[j] - '0');
if (x > k) break; // 再拿更長只會更大
for (int t = x;t <= k;t++) dp[j + 1][t] += dp[i][t - x];
}
// 從 k 往下找第一個湊得出來的總和
int ans = k;
while (!dp[n][ans]) ans--;
cout << ans << ' ' << dp[n][ans] << '\n';
}解法二:折半枚舉(ZeroJudge)
陣列開不出來,就只能枚舉插法。
40 個字元有 39 個空隙,全部枚舉是
前
麻煩的是跨過中間的那一段數字,兩邊都沒辦法自己算出來。所以兩邊都只算已經確定的部分,中間那段留到配對的時候再算。
用 1+23+4567+8+90:
- 左半確定的是
1+23,和是 24。還沒結束的那一段從第個字元( 4)開始。 - 右半確定的是
8+90,和是 98。第一個加號在第個字元( 8)前面。 - 中間那段是第
到第 個字元,也就是 4567。
做法:
- 先算好
val[l][r],代表第到第 個字元組成的數字。超過 的都記成 ,避免溢位。 - 枚舉左半的每種插法,算出確定的和跟
,把和丟進 a[l]。丟完之後每個a[l]排序。 - 枚舉右半的每種插法,算出確定的和
sum跟。 - 再枚舉
。中間那段是 val[l][r],所以左半的和最多只能是k - sum - val[l][r],在a[l]裡二分搜出不超過它的最大值。 - 這時的結果是
x + sum + val[l][r]。比答案大就換掉,插法數歸零;跟答案一樣大,插法數就加上a[l]裡的個數。
第 4 步的
時間複雜度最差大約是
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
const long long INF = numeric_limits<int>::max();
signed main() {
IO;
string s;
int k;
cin >> s >> k;
// h:左半管的空隙數,m:右半管的空隙數
int n = s.size(), h = n / 2, m = n - 1 - h;
// val[l][r]:s[l..r) 的數字,超過 k 的都記成 k + 1
// a[l]:左半插完之後,還沒結束的那一段從第 l 個字元開始的插法,放它們確定的和
vector<vector<int>> val(n + 1, vector<int>(n + 1)), a(h + 1);
for (int l = 0;l < n;l++) for (int r = l + 1;r <= n;r++) val[l][r] = min(val[l][r - 1] * 10 + s[r - 1] - '0', k + 1);
// 枚舉左半:第 j 個 bit 是 1,代表第 j 個字元後面插加號
for (int i = 0;i < (1 << h);i++) {
int sum = 0, l = 0; // l:還沒結束的那一段從哪裡開始
for (int j = 0;j < h;j++) if (i & (1 << j)) sum += val[l][j + 1], l = j + 1;
if (sum <= k) a[l].push_back(sum);
}
for (auto &v : a) sort(v.begin(), v.end());
int ans = 0, cnt = 0;
// 枚舉右半:第 j 個 bit 是 1,代表第 h + 1 + j 個字元前面插加號
for (int i = 0;i < (1 << m);i++) {
// r:右半第一個加號的位置(沒有就是 n),last:上一個加號的位置
int sum = 0, r = n, last = 0;
for (int j = 0;j < m;j++) if (i & (1 << j)) {
if (r == n) r = h + 1 + j;
else sum += val[last][h + 1 + j];
last = h + 1 + j;
}
if (r != n) sum += val[last][n]; // 最後一段
// 中間那段是 s[l..r),l 越小這段越長,超過 k 就停
for (int l = h;l >= 0 and val[l][r] <= k;l--) {
// 左半的和最多只能到 k - sum - val[l][r],找不超過它的最大值
auto it = upper_bound(a[l].begin(), a[l].end(), k - sum - val[l][r]);
if (it == a[l].begin()) continue; // 沒有能配的
int x = *--it, now = x + sum + val[l][r];
if (now > ans) ans = now, cnt = 0;
// a[l] 裡面有幾個 x,就多幾種插法
if (now == ans) cnt += it - lower_bound(a[l].begin(), a[l].end(), x) + 1;
}
}
cout << ans << ' ' << cnt;
}中高級
中高級的三題目前只有 AACPOJ 有。
| 題目 | 做法 |
|---|---|
| 營火競賽 | 照著題目模擬 |
| 火星探測資料 | 枚舉字串的先後順序 |
| 考拉茲距離 | 從目標往回推,再二分搜 |
營火競賽
題目
- 拿滅火器的人往順時針方向找,把第一個「火把還亮著、而且跟自己不同隊」的人的火把弄熄。
- 如果火把還亮著的人都是同一隊,比賽結束。
- 不然就把滅火器交給順時針方向第一個火把還亮著的人,同隊的也可以。
問總共熄了幾支火把,還有最後剩下哪一隊。
想法
要想一下的只有「怎麼知道只剩一隊」。我用 cnt 記每一隊還有幾支火把亮著,哪一隊變成 0,隊伍數 k 就減 1,k 剩 1 就結束。
繞圈用 % n 處理,所以編號改成從 0 開始。
程式碼
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
IO;
int n, k;
cin >> n >> k;
// cnt[x]:第 x 隊還有幾支火把亮著
vector<int> t(n), cnt(k + 1);
for (auto &x : t) cin >> x, cnt[x]++;
// out[i]:第 i 個人的火把熄了沒
vector<bool> out(n);
// now:現在拿滅火器的人(編號改成從 0 開始,繞圈比較好寫)
int now = 0, ans = 0;
// k 是還有火把亮著的隊伍數,剩一隊就結束
while (k > 1) {
// 往順時針找第一個還亮著、而且不同隊的人
int x = (now + 1) % n;
while (out[x] or t[x] == t[now]) x = (x + 1) % n;
out[x] = 1, ans++;
if (--cnt[t[x]] == 0) k--; // 這一隊全熄了
// 滅火器交給順時針第一個還亮著的人
now = (now + 1) % n;
while (out[now]) now = (now + 1) % n;
}
cout << ans << ' ' << t[now]; // now 一定停在還亮著的人身上
}火星探測資料
題目
有
例如 rock 和 ocks 可以疊成 rocks,不用寫成 rockocks。
想法
一樣的字串留一個就好,先去掉。
每個字串都一樣長,所以不會有哪個字串整個被包在另一個裡面,它們在
- 先算好
same[i][j],代表的結尾和 的開頭最多可以疊幾個字。例如 aaba後面接abaa,aba這三個字可以疊,所以是 3。 - 用
next_permutation枚舉順序。第一個字串整個放,後面每個只接沒疊到的部分。 - 接出來的字串比答案短,或一樣長但字典序比較小,就換掉。
時間複雜度
程式碼
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
IO;
int n, k;
cin >> n >> k;
// 用 set 把一樣的字串去掉,順便排好
set<string> st;
for (int i = 0;i < k;i++) {
string x;
cin >> x;
st.insert(x);
}
vector<string> s(st.begin(), st.end());
k = s.size();
// same[i][j]:s[i] 的結尾和 s[j] 的開頭最多可以疊幾個字
vector<vector<int>> same(k, vector<int>(k));
for (int i = 0;i < k;i++) for (int j = 0;j < k;j++) {
if (i == j) continue;
// 從長的開始試,第一個對上的就是最多
for (int len = n - 1;len >= 1;len--) if (s[i].substr(n - len) == s[j].substr(0, len)) {
same[i][j] = len;
break;
}
}
// p 是字串的先後順序,每一種都試
vector<int> p(k);
for (int i = 0;i < k;i++) p[i] = i;
string ans;
do {
string now = s[p[0]];
// 跟前一個疊到的部分不用再接
for (int i = 1;i < k;i++) now += s[p[i]].substr(same[p[i - 1]][p[i]]);
// 比較短,或一樣長但字典序比較小,就換掉
if (ans.empty() or now.size() < ans.size() or (now.size() == ans.size() and now < ans)) ans = now;
} while (next_permutation(p.begin(), p.end()));
cout << ans;
}考拉茲距離
題目
對一個正整數做一次操作:奇數
給目標
有
想法
一個數
是偶數: ,所以 ,一定有。 是奇數: ,所以 ,要整除才有。 是奇數,除以 3 之後還是奇數,不用另外檢查。
從
| 往回推幾次 | 推出來的數 |
|---|---|
| 0 | 11 |
| 1 | 22、7 |
| 2 | 44、14 |
| 3 | 88、29、28、9 |
每個數最多推出兩個,看起來會有
最大的數是 long long。
全部排序之後,每筆詢問二分搜第一個
同一個數可能被推出來不只一次(例如
程式碼
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
const long long INF = numeric_limits<int>::max();
signed main() {
IO;
int t, m, q;
cin >> t >> m >> q;
// v:所有可行的數,now:剛好往回推了幾次的那一層
vector<int> v = {t}, now = {t};
while (m--) {
vector<int> nt;
for (auto x : now) {
// 上一步是偶數:一定有
nt.push_back(x * 2);
// 上一步是奇數:要整除才有
if ((x * 2 - 1) % 3 == 0) nt.push_back((x * 2 - 1) / 3);
}
for (auto x : nt) v.push_back(x);
now = nt;
}
sort(v.begin(), v.end());
while (q--) {
int a, ans = INF;
cin >> a;
// it:第一個 >= a 的可行數
auto it = lower_bound(v.begin(), v.end(), a);
if (it != v.end()) ans = min(ans, *it - a); // 右邊最近的
if (it != v.begin()) ans = min(ans, a - *prev(it)); // 左邊最近的
cout << ans << '\n';
}
}
載入留言中…