Editorial for 轉盤得分 (APCS 2025-06 中級)
簡潔題意
\(m\) 個輪盤、每個 \(n\) 格,每格一個小寫字母(每個輪盤就是一條長度 \(n\) 的字串)。共 \(k\) 回合,每回合每個輪盤各轉一個距離 \(d\):\(d > 0\) 順時針轉 \(d\) 格(字串向右循環位移)、\(d < 0\) 逆時針轉 \(-d\) 格、\(0\) 不動;可能超過一圈,而且每回合接著上一回合的狀態繼續轉。轉完後對每個位置計分:\(m\) 個輪盤在這個位置對齊的字元裡,出現最多次的那個字母出現了幾次就是幾分;回合分數=\(n\) 個位置加總。輸出 \(k\) 回合的總分(\(1 \le m, n, k \le 30\)、\(-100 \le d \le 100\))。
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(60\) 分):\(m = 3\)。
- 子題組 2(\(40\) 分):無額外限制。
先拿下子題組 1(60 分):三個輪盤,同不同直接用 if 問
轉動。 順時針轉 \(d\) 格=字串向右循環位移 \(d\) 格=最後 \(d\) 個字元搬到最前面:w.substr(n - d) + w.substr(0, n - d)(10.8 的 substr+串接)。要先把 \(d\) 化成 \(0 \sim n - 1\):轉 \(n\) 格回到原狀,所以先對 \(n\) 取餘;但 C++ 的 % 對負數會得到負的餘數(上冊 2.6),逆時針 \(4\) 格的 -4 % 6 是 -4——再加 \(n\) 取一次餘 ((d % n) + n) % n,負的就變成等價的正數(逆時針 \(4\) 格=順時針 \(2\) 格)。轉完直接存回 w[j],下一回合從這裡繼續,不回到初始字串。
計分。 三個輪盤時每個位置只有三個字元,「出現最多的字母出現幾次」用 if 問就好:三個全同 \(3\) 分、任兩個相同 \(2\) 分、否則 \(1\) 分(上冊 3.3 的 &&/||)。三條字串用 string 陣列裝(10.7)。
#include <iostream>
#include <string>
using namespace std;
int main() {
int m, n, k;
cin >> m >> n >> k; // 子題組 1 保證 m = 3:剛好三個輪盤
string w[3];
for (int j = 0; j < 3; j++) cin >> w[j];
int total = 0;
for (int round = 0; round < k; round++) {
for (int j = 0; j < 3; j++) {
int d;
cin >> d;
d = ((d % n) + n) % n; // 轉幾圈都一樣、負的轉成等價的正數:0 ~ n-1
w[j] = w[j].substr(n - d) + w[j].substr(0, n - d); // 順時針轉 d 格=最後 d 個字元搬到最前面
}
for (int i = 0; i < n; i++) { // 三個輪盤對齊的字元:全同 3 分、兩個同 2 分、否則 1 分
if (w[0][i] == w[1][i] && w[1][i] == w[2][i]) {
total += 3;
} else if (w[0][i] == w[1][i] || w[1][i] == w[2][i] || w[0][i] == w[2][i]) {
total += 2;
} else {
total += 1;
}
}
}
cout << total << '\n';
return 0;
}
拿範例 1 對一次:第一回合 eapcsi/taiwan/daicpe 得 \(10\) 分、第二回合 \(7\) 分,總分 \(17\)。這份程式交上去,範例 2(四個輪盤)和子題組 2 會 WA——這是正常的,逐筆給分之下子題組 1 的 \(60\) 分穩穩到手。
從 60 分到 100 分:m 個輪盤,用計數陣列找最多的字母
輪盤變成 \(m\) 個,轉動的程式一字不改,只有計分不能再用 if 枚舉——改成計數陣列(上冊 6.7):對每個位置開 int count[26] = {},把 \(m\) 個輪盤在這個位置的字元用 ch - 'a' 換成 \(0 \sim 25\)(8.3)去計數,再打擂台找最大值(上冊 3.9)——那就是這個位置的分數。輪盤改用 vector<string> 裝(10.3)。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
int m, n, k;
cin >> m >> n >> k;
vector<string> w(m); // m 個輪盤,每個是一條長度 n 的字串
for (int j = 0; j < m; j++) cin >> w[j];
int total = 0;
for (int round = 0; round < k; round++) {
for (int j = 0; j < m; j++) {
int d;
cin >> d;
d = ((d % n) + n) % n; // 轉幾圈都一樣、負的轉成等價的正數:0 ~ n-1
w[j] = w[j].substr(n - d) + w[j].substr(0, n - d); // 順時針轉 d 格=最後 d 個字元搬到最前面
}
for (int i = 0; i < n; i++) {
int count[26] = {}; // 這個位置上 a~z 各出現幾次
for (int j = 0; j < m; j++) count[w[j][i] - 'a']++;
int best = 0;
for (int c = 0; c < 26; c++) {
if (count[c] > best) best = count[c]; // 出現最多次的那個字母出現了幾次
}
total += best;
}
}
cout << total << '\n';
return 0;
}
運算量:每回合轉 \(m\) 個輪盤(各抄一次 \(n\) 個字元)、計分 \(n\) 個位置各看 \(m\) 個字元加掃 \(26\) 格,\(30 \times 30 \times 30\) 再乘個常數,遠在一秒之內。
測過再交:範例沒有「全部相同」,也沒有只轉整圈的回合
兩個範例都有順轉、逆轉、超過一圈,也有跨回合接續。沒測到的是:某個位置 \(m\) 個全同(分數等於 \(m\))、轉的距離剛好是 \(n\) 的倍數、\(n = 1\)、只有一個輪盤。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
1 4 2 / abcd / 3 / -3 |
8 |
只有一個輪盤:每個位置都是 \(1\) 分,每回合 \(n\) 分 |
3 1 3 / a / b / a / 100 -100 7 / 0 0 0 / -1 1 -1 |
6 |
\(n = 1\) 怎麼轉都不動(\(\pm 100\) 取餘後是 \(0\));a b a 每回合 \(2\) 分 |
3 4 1 / abcd / abcd / abcd / 4 -4 8 |
12 |
轉整圈(\(4\)、\(-4\)、\(8\))=不動;三個全同,每個位置 \(3\) 分 |
4 2 1 / ab / ab / ab / ab / 1 1 1 1 |
8 |
四個全同:每個位置 \(4\) 分——子題組 1 版那種「三個同 \(3\) 分、兩個同 \(2\) 分」的 if 在 \(m = 4\) 就不夠用了 |
3 3 2 / abc / bca / cab / 0 1 2 / 1 1 1 |
18 |
第一回合轉完三個都變 abc(\(9\) 分),第二回合三個同步再轉一格、還是全同(\(9\) 分)。每回合從初始字串重新轉的程式印 12 |
五筆都親眼看過正確,這題就穩了。
常犯錯誤
- 轉的方向反了(寫成
substr(d) + substr(0, d),變成向左位移):範例 1 印16(該印17)。 - 負數取餘沒處理(只寫
d % n):範例 1 第一回合的 \(-4\) 讓substr的起點超出字串,程式直接當掉;把負號拿掉當正數轉的程式印14。 - 每回合從初始字串重新轉:範例 1 印
20;自測表第 5 列印12。 - 位置分數算成「不同字母的種類數」:範例 1 印
31。 - 只算最後一回合:範例 1 印
7。 - 沒有任何兩個相同時算 \(0\) 分(以為最大出現次數至少要 \(2\) 才計):三個都不同也是 \(1\) 分——範例 1 印
9。