APCS 2026/11 解題紀錄(C++)

2026 年 11 月 APCS 高級、中高級各三題的題解。高級包含第一題為什麼不寫遞迴,以及第二、三題在 ZeroJudge 和 AACPOJ 上的差別;中高級是營火競賽、火星探測資料、考拉茲距離。C++ 程式碼都有。

發布
更新
字數
4,699
閱讀
約 12 分鐘
瀏覽
56
本頁目錄
  1. 高級
  2. 建造堡壘
  3. 漫遊曼哈頓
  4. 切割相加
  5. 中高級
  6. 營火競賽
  7. 火星探測資料
  8. 考拉茲距離

這篇有高級和中高級各三題。

APCS 不公布題本,題目是 AA 競程照考生的回憶整理的。高級的三題 ZeroJudge 和 AACPOJ 都可以交,但兩邊有些地方不一樣,先整理在這裡:

題目 做法 兩邊的差別
建造堡壘 樹 DP,不用遞迴 沒有,同一份程式都能過
漫遊曼哈頓 一列一列 DP 結束的規則不同,答案的取法要改
切割相加 背包/折半枚舉 kk 的範圍不同,解法完全不同

高級

建造堡壘

ZeroJudge t192|AACPOJ

題目

nn 個城市用 n−1n-1 條路連在一起,也就是一棵樹。在城市 ii 蓋堡壘要花 CiC_i,每條路的兩端至少要有一端有堡壘,問最少要花多少。

想法

把城市 1 當根,每個點記兩個數字:

  • dp[1][u]\text{dp}[1][u]:uu 有蓋的時候,uu 這棵子樹最少花多少
  • dp[0][u]\text{dp}[0][u]:uu 沒蓋的時候,uu 這棵子樹最少花多少

看 uu 和小孩 cc 中間的那條路就知道怎麼算:

  • uu 沒蓋,cc 就一定要蓋。
    dp[0][u]=∑cdp[1][c]\text{dp}[0][u]=\sum_{c}\text{dp}[1][c]
  • uu 有蓋,cc 蓋不蓋都可以,選便宜的。
    dp[1][u]=Cu+∑cmin⁡(dp[0][c], dp[1][c])\text{dp}[1][u]=C_u+\sum_{c}\min(\text{dp}[0][c],\ \text{dp}[1][c])

答案是 min⁡(dp[0][1], dp[1][1])\min(\text{dp}[0][1],\ \text{dp}[1][1])。

不寫遞迴

這題用 DFS 遞迴寫最直覺。但考完我在脆上看到蠻多人第一題沒拿滿,我猜是遞迴太深爆掉了:nn 最大 10510^5,如果樹是一條直線,就要遞迴 10510^5 層。

所以我沒有用遞迴,改成這樣:

  1. 從城市 1 做 BFS,把走到的順序存在 q,順便記每個點的爸爸 p。
  2. 把 q 倒著跑,每個點把自己的值加給爸爸。

BFS 的順序裡爸爸一定排在小孩前面,倒過來就變成小孩一定先算完。

例如路是 1-2、1-3、2-4,BFS 的順序是 1 2 3 4。倒著跑就是 4 加給 2、3 加給 1、2 加給 1,輪到 2 的時候它的小孩 4 已經加完了。

時間複雜度 O(n)O(n)。

程式碼

C++
#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 t193|AACPOJ

題目

nn 列 mm 欄的路口,相鄰路口中間的街道各有一個分數,可能是負的。可以從任何一個路口出發,每一步只能往東、往西或往南,走過的不能再走,問最多可以拿幾分。

兩邊差在「在哪裡結束」:

  • ZeroJudge:一走到最南邊那一列就結束,不能在那一列橫著走。
  • AACPOJ:在哪個路口結束都可以。

我照 ZeroJudge 寫的程式丟到 AACPOJ 會 WA,就是因為這個。

想法

不能往北也不能重複走,所以在同一列裡只能一直往左或一直往右,走完再往下。跟 2020 年 10 月的「勇者修煉」是同一種做法。

一列一列往下算,每一列算三個東西:

  1. dp[j]:剛走進這一列第 jj 個路口時的最高分。可能是從正上方下來的,也可能是直接從這裡出發(0 分)。
    dp[j]=max⁡(0, best[j]+col[i−1][j])\text{dp}[j]=\max(0,\ \text{best}[j]+\text{col}[i-1][j])
  2. l[j]、r[j]:從左邊、從右邊一路走到 jj 的最高分。
    l[j]=max⁡(dp[j], l[j−1]+row[i][j−1])l[j]=\max(\text{dp}[j],\ l[j-1]+\text{row}[i][j-1])

    r[j]=max⁡(dp[j], r[j+1]+row[i][j])r[j]=\max(\text{dp}[j],\ r[j+1]+\text{row}[i][j])
  3. best[j] = max(l[j], r[j]):在這一列走完、停在 jj 的最高分,下一列的第 1 步會用到。

兩邊只差在最後答案怎麼取:

  • ZeroJudge:最後一列的 dp 取最大。到了最後一列就結束,不能再橫著走,所以不是取 best。
  • AACPOJ:每一列的 best 全部取最大。

以 AACPOJ 的範例一來說,最好的走法是到了第二列再往東走四段。用 ZeroJudge 的取法會漏掉這四段,輸出 14,正確答案是 23。

時間複雜度 O(nm)O(nm)。

程式碼(ZeroJudge)

C++
#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,其他都一樣。

C++
#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;
}

切割相加

ZeroJudge t194|AACPOJ

題目

給一個數字字串 SS,長度最多 40。數字和數字中間可以插加號,變成一個加法算式。在結果不超過 kk 的插法裡,找出最大的結果,還有幾種插法剛好等於它。

例如 S=1111S=1111、k=20k=20,最大只能湊到 13,插法有 1+1+11、1+11+1、11+1+1 三種,所以輸出 13 3。

兩邊差在 kk 的範圍,解法也跟著不一樣:

  • AACPOJ:k≤3×104k\le3\times10^4,可以用背包。
  • ZeroJudge:kk 沒有給上限,只保證答案在 int 範圍內,也就是可能到二十億左右。背包的陣列開不出來,要用折半枚舉。

解法一:背包(AACPOJ)

dp[i][t]:前 ii 個字元切完,總和剛好是 tt 的插法有幾種。一開始只有 dp[0][0] = 1。

每次決定下一段要拿多長。從第 ii 個字元拿到第 jj 個,這一段的數字是 xx,就做

dp[j+1][t]+=dp[i][t−x]\text{dp}[j+1][t]\mathrel{+}=\text{dp}[i][t-x]

例如 S=1111S=1111,前兩個字元可以切成 1+1 或 11,所以 dp[2][2] = 1、dp[2][11] = 1。

xx 超過 kk 就不用再往後拿了,所以一段最多五位數。

算完之後從 kk 往下找,第一個 dp[n][t] 不是 0 的 tt 就是最大的結果,dp[n][t] 就是插法數。

插法數要開 long long:題目只保證答案在 int 內,其他格子可能更大(全部的插法有 2392^{39} 種)。

時間複雜度大約是 40×5×3×104=6×10640\times5\times3\times10^4=6\times10^6。

C++
#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 個空隙,全部枚舉是 2392^{39},大約 5×10115\times10^{11},跑不完。但是分成兩半各自枚舉,一半最多 2202^{20},才一百萬左右,最後再把兩邊配起來就好。

前 h=⌊n/2⌋h=\lfloor n/2\rfloor 個空隙歸左半,剩下的歸右半。

麻煩的是跨過中間的那一段數字,兩邊都沒辦法自己算出來。所以兩邊都只算已經確定的部分,中間那段留到配對的時候再算。

用 S=1234567890S=1234567890 當例子(字元從 0 開始數),假設插成 1+23+4567+8+90:

  • 左半確定的是 1+23,和是 24。還沒結束的那一段從第 l=3l=3 個字元(4)開始。
  • 右半確定的是 8+90,和是 98。第一個加號在第 r=7r=7 個字元(8)前面。
  • 中間那段是第 ll 到第 r−1r-1 個字元,也就是 4567。

做法:

  1. 先算好 val[l][r],代表第 ll 到第 r−1r-1 個字元組成的數字。超過 kk 的都記成 k+1k+1,避免溢位。
  2. 枚舉左半的每種插法,算出確定的和跟 ll,把和丟進 a[l]。丟完之後每個 a[l] 排序。
  3. 枚舉右半的每種插法,算出確定的和 sum 跟 rr。
  4. 再枚舉 ll。中間那段是 val[l][r],所以左半的和最多只能是 k - sum - val[l][r],在 a[l] 裡二分搜出不超過它的最大值 xx。
  5. 這時的結果是 x + sum + val[l][r]。比答案大就換掉,插法數歸零;跟答案一樣大,插法數就加上 a[l] 裡 xx 的個數。

第 4 步的 ll 從 hh 往 0 跑,中間那段只會越來越大,超過 kk 就可以停。

時間複雜度最差大約是 O(2n/2⋅n2)O(2^{n/2}\cdot n^2),但中間那段通常十位數左右就超過 kk,實際上快很多。

C++
#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 有。

題目 做法
營火競賽 照著題目模擬
火星探測資料 枚舉字串的先後順序
考拉茲距離 從目標往回推,再二分搜

營火競賽

AACPOJ

題目

nn 個人圍成一圈,第 ii 個人是第 tit_i 隊,每個人手上都有一支點著的火把。滅火器一開始在第 1 個人手上,每一回合照這個順序做:

  1. 拿滅火器的人往順時針方向找,把第一個「火把還亮著、而且跟自己不同隊」的人的火把弄熄。
  2. 如果火把還亮著的人都是同一隊,比賽結束。
  3. 不然就把滅火器交給順時針方向第一個火把還亮著的人,同隊的也可以。

問總共熄了幾支火把,還有最後剩下哪一隊。n≤2000n\le 2000。

想法

nn 只有 2000,照著題目做就好。每一回合一定會熄掉一支,所以最多 n−1n-1 回合;每一回合找人最多繞一圈,總共 O(n2)O(n^2)。

要想一下的只有「怎麼知道只剩一隊」。我用 cnt 記每一隊還有幾支火把亮著,哪一隊變成 0,隊伍數 k 就減 1,k 剩 1 就結束。

繞圈用 % n 處理,所以編號改成從 0 開始。

程式碼

C++
#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 一定停在還亮著的人身上
}

火星探測資料

AACPOJ

題目

有 kk 個長度都是 nn 的字串,要找一個最短的字串 SS,讓每一個都是 SS 裡面連續的一段。一樣短的話,要字典序最小的那個。n≤8n\le 8、k≤9k\le 9。

例如 rock 和 ocks 可以疊成 rocks,不用寫成 rockocks。

想法

一樣的字串留一個就好,先去掉。

每個字串都一樣長,所以不會有哪個字串整個被包在另一個裡面,它們在 SS 裡面一定排得出先後順序。順序決定之後,SS 的長度就是 nn 加上後面每個字串多接出來的長度,所以相鄰兩個疊越多越好。

kk 最多 9,順序最多 9!=3628809!=362880 種,全部試一遍:

  1. 先算好 same[i][j],代表 sis_i 的結尾和 sjs_j 的開頭最多可以疊幾個字。例如 aaba 後面接 abaa,aba 這三個字可以疊,所以是 3。
  2. 用 next_permutation 枚舉順序。第一個字串整個放,後面每個只接沒疊到的部分。
  3. 接出來的字串比答案短,或一樣長但字典序比較小,就換掉。

時間複雜度 O(k!⋅k⋅n)O(k!\cdot k\cdot n),大約兩千六百萬。

程式碼

C++
#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;
}

考拉茲距離

AACPOJ

題目

對一個正整數做一次操作:奇數 nn 變成 3n+12\frac{3n+1}{2},偶數 nn 變成 n2\frac{n}{2}。

給目標 tt 和次數上限 mm。從 xx 開始,做不超過 mm 次操作可以變成 tt,xx 就是「可行的數」,tt 自己也算。

有 qq 筆詢問,每筆給一個 aa,問離 aa 最近的可行數跟它差多少。t≤109t\le 10^9、m<32m<32、q<104q<10^4、a≤1018a\le 10^{18}。

想法

xx 可以到 101810^{18},沒辦法每個都試,所以反過來從 tt 往回推。

一個數 yy 的上一步 xx 有兩種可能:

  • xx 是偶數:x2=y\frac{x}{2}=y,所以 x=2yx=2y,一定有。
  • xx 是奇數:3x+12=y\frac{3x+1}{2}=y,所以 x=2y−13x=\frac{2y-1}{3},要整除才有。2y−12y-1 是奇數,除以 3 之後還是奇數,不用另外檢查。

從 tt 開始往回推 mm 層,推出來的數全部存起來,就是所有可行的數。用範例 1(t=11t=11、m=3m=3)看:

往回推幾次 推出來的數
0 11
1 22、7
2 44、14
3 88、29、28、9

每個數最多推出兩個,看起來會有 2312^{31} 個,但第二種要整除才有,實際上少很多,m=31m=31 的時候大約幾萬個。

最大的數是 t⋅231t\cdot 2^{31},大約 2×10182\times 10^{18},要用 long long。

全部排序之後,每筆詢問二分搜第一個 ≥a\ge a 的數,它和它前面那個數,取比較近的。

同一個數可能被推出來不只一次(例如 t=1t=1 時 1→2→11\to 2\to 1 會繞回來),重複放進去不影響二分搜,所以沒有另外處理。

程式碼

C++
#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';
	}
}
最後更新 2026.11.18

Comments

留言

支援 Markdown、程式碼高亮(```cpp)與 LaTeX($E=mc^2$),Ctrl + Enter 送出。頭像會用你的 e-mail 去 Gravatar 找,e-mail 本身不會公開。

載入留言中…

Esc

輸入關鍵字,例如「線段樹」「Makefile」「面試」。

↑ ↓ 選擇Enter 開啟