航空拍照圖 題解|APCS 2025 年 10 月中級 第 2 題


簡潔題意

兩張 \(R \times C\) 的灰階照片 \(A\)、\(B\)(\(R, C \le 200\),灰階值 \(0 \sim 255\))。兩張可以各自順時針轉 \(0^\circ\)、\(90^\circ\)、\(180^\circ\) 或 \(270^\circ\);轉完大小不同,相似度是 \(0\%\);大小相同時,若相同位置灰階值相同的格子有 \(S\) 個,相似度是 \(\left\lfloor \dfrac{100S}{RC} \right\rfloor\%\)。輸出最高的相似度。

依正確通過的測試資料筆數給分,其中:

  • 子題組 1(\(60\) 分):\(R = 1\)。
  • 子題組 2(\(40\) 分):無額外限制。

先想清楚:只要轉 \(B\)

兩張照片轉同一個角度,對到的格子還是同一對,相似度不變。所以「\(A\) 轉 \(x\) 度、\(B\) 轉 \(y\) 度」和「\(A\) 不轉、\(B\) 多轉 \(y - x\) 度」一樣——只要讓 \(B\) 轉 \(0^\circ\)、\(90^\circ\)、\(180^\circ\)、\(270^\circ\) 四種,各算一次相似度,取最大的。

轉 \(90^\circ\) 或 \(270^\circ\) 會讓大小從 \(R \times C\) 變成 \(C \times R\),所以照片不是正方形時,這兩種一定是 \(0\%\)。

相似度用整數算:100 * same / (R * C) 的整數除法本身就是無條件捨去(2.6)。照片最多 \(40000\) 格,分子最多是 \(400\) 萬,int 放得下。

先拿下子題組 1(60 分):只剩不轉和左右顛倒

只有一列的照片轉 \(180^\circ\) 就是左右顛倒:\(B\) 的第 \(j\) 格換成第 \(C - 1 - j\) 格。轉 \(90^\circ\)、\(270^\circ\) 會變成 \(C \times 1\),除了 \(C = 1\)(那時四種轉法都一樣)之外都是 \(0\%\)。所以只要比兩種。

#include <bits/stdc++.h>
using namespace std;

int A[200], B[200];

int main() {
    int R, C;
    cin >> R >> C;  // 子題組 1 保證 R = 1
    for (int j = 0; j < C; j++) cin >> A[j];
    for (int j = 0; j < C; j++) cin >> B[j];
    int same0 = 0, same180 = 0;
    for (int j = 0; j < C; j++) {
        if (A[j] == B[j]) same0++;            // 不轉
        if (A[j] == B[C - 1 - j]) same180++;  // B 轉 180 度=左右顛倒
    }
    int best = max(same0, same180);
    cout << 100 * best / C << "%" << endl;
}

範例是 \(6 \times 5\),這個版本對範例會 WA 是正常的;它對子題組 1 的 \(12\) 筆全對,穩拿 \(60\) 分。

從 60 分到 100 分:寫一個「順時針轉 \(90^\circ\)」的函式

順時針旋轉的公式:\(R \times C\) 的舊圖第 \(i\) 列第 \(j\) 欄,搬到新圖的第 \(j\) 列、第 \(R - 1 - i\) 欄。新圖大小是 \(C \times R\),要另外開一張新的表,不能在原地轉。把它寫成函式 rotateB,每比完一次就把 \(B\) 轉一次,迴圈跑四次正好比到 \(0^\circ\)、\(90^\circ\)、\(180^\circ\)、\(270^\circ\)。大小和 \(A\) 不同的那幾次直接跳過(相似度 \(0\%\))。

照片用全域的二維陣列存(6.9),rotateB 直接改全域的 B:先把轉好的圖寫進另一張表 tmp,再抄回 B。\(B\) 轉完列數、欄數會對調,所以另外用 rowsB、colsB 記它現在的大小。四次比對加四次旋轉(每次旋轉寫一遍 tmp、再抄回一遍),總共不到 \(5 \times 10^5\) 次運算。

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 205;  // R、C 都不超過 200
int A[MAX_N][MAX_N], B[MAX_N][MAX_N], tmp[MAX_N][MAX_N];
int rowsB, colsB;  // B 現在的大小:轉 90 度之後列數、欄數會對調

void rotateB() {  // B 順時針轉 90 度:舊圖 (i, j) 搬到新圖 (j, rowsB - 1 - i)
    for (int i = 0; i < rowsB; i++) {
        for (int j = 0; j < colsB; j++) {
            tmp[j][rowsB - 1 - i] = B[i][j];
        }
    }
    swap(rowsB, colsB);  // 新圖是 colsB 列、rowsB 欄
    for (int i = 0; i < rowsB; i++) {  // 轉好的圖抄回 B
        for (int j = 0; j < colsB; j++) {
            B[i][j] = tmp[i][j];
        }
    }
}

int main() {
    int R, C;
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) cin >> A[i][j];
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) cin >> B[i][j];
    }
    rowsB = R;
    colsB = C;
    int best = 0;
    for (int t = 0; t < 4; t++) {  // B 依序轉 0、90、180、270 度
        if (rowsB == R && colsB == C) {  // 大小不同=0%,不用比
            int same = 0;
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (A[i][j] == B[i][j]) same++;
                }
            }
            best = max(best, 100 * same / (R * C));
        }
        rotateB();
    }
    cout << best << "%" << endl;
}

測過再交:範例的答案是轉 \(180^\circ\)

範例不是正方形,答案又剛好是轉 \(180^\circ\):「不轉」「轉 \(90^\circ\)」「轉 \(270^\circ\)」「無條件捨去」全部沒測到。下面三種錯法範例都會過(見常犯錯誤),自己補這幾筆:

輸入 正確輸出 這一筆在測什麼
1 3/1 2 3/1 2 4 66% 不轉就是最好的;\(200 / 3\) 無條件捨去
2 2/1 2/3 4/3 1/4 2 100% \(B\) 要轉 \(270^\circ\) 才對得上
2 2/1 2/3 4/2 4/1 3 100% \(B\) 要轉 \(90^\circ\) 才對得上
2 2/1 2/3 4/2 1/4 3 50% \(B\) 是 \(A\) 左右翻轉,翻轉不是旋轉

四筆都親眼看過正確,這題就穩了。

常犯錯誤
  • 只試了轉過的,忘了不轉也是一種:範例全過,自測表第 1 列印 33%;本站 \(20\) 筆掛 \(3\) 筆。
  • 正方形時沒試 \(90^\circ\) 和 \(270^\circ\),只比不轉和 \(180^\circ\):範例不是正方形,所以全過;自測表第 2、3 列都印 0%,本站 \(20\) 筆掛 \(3\) 筆。只漏了 \(270^\circ\) 也會掛 \(2\) 筆,自測表第 2 列抓得到。
  • 把左右翻轉也當成一種轉法:範例全過,自測表第 4 列印 100%;本站 \(20\) 筆掛 \(1\) 筆。