火星探測資料 題解｜APCS 2026 年 11 月中高級 第 2 題

前置知識

這題要把所有的順序都試一遍，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 枚舉所有排列：NTUCPC Guide〈枚舉〉的「排列」一節——next_permutation 搭配 do { … } while (…)，會照字典序走過全部的排列，但要從排好序的那一個開始，否則只會走到比起點大的那些；\(m\) 個東西有 \(m!\) 種排列。吳邦一《AP325》第 1 章的 P-1-9「N-Queen 解的個數」也用這個函式窮舉排列，另外示範了用遞迴窮舉的寫法（教材 PDF 第 29～31 頁；Python 版第 1 章；站上題目 ap325p109）。
• string 的常用操作：substr 取出一段、+= 接在尾巴、< 直接比字典序；vector<string> 也能直接用 sort 排序。

簡潔題意

給 \(k\) 筆探測結果，每筆都是長度 \(n\)、只含小寫英文字母的字串，可能有好幾筆一模一樣。找一個最短的字串 \(S\)，讓每一筆都是 \(S\) 的連續子字串；最短的不只一個時，輸出字典序最小的（\(1 \le n \le 8\)，\(1 \le k \le 9\)）。（APCS 逐筆給分。）

最短的 S 長什麼樣：排好順序，相鄰兩筆接上最大重疊

答案最長可能有 \(8 \times 9 = 72\) 個字母，不可能把所有字串都試一遍。先弄清楚最短的 \(S\) 一定長什麼樣子。

先去重：一模一樣的探測結果只要出現一次，所以先把重複的拿掉，剩下 \(m\) 筆互不相同的字串（\(m \le k \le 9\)）。

重疊：\(a\) 後面接 \(b\) 時，如果 \(a\) 的最後 \(L\) 個字母正好是 \(b\) 的前 \(L\) 個字母，這 \(L\) 個字母就能共用，只要再接上 \(b\) 剩下的 \(n - L\) 個字母。能共用的 \(L\) 可能不只一種（abab 後面接 baba，\(L\) 可以是 \(1\) 或 \(3\)），最大的那個叫做 \(a\) 接 \(b\) 的最大重疊，完全接不上就是 \(0\)。兩筆互不相同，所以最大重疊最多 \(n - 1\)。

拿一個最短的 \(S\)，每一筆挑一個它在 \(S\) 裡出現的位置（出現好幾次就隨便挑一個），照開始的位置由左到右排好。互不相同的兩筆不會從同一個位置開始（一樣長、又從同一格開始，就是同一個字串），而且大家一樣長，開始得早的也結束得早。接著看排好之後相鄰的兩筆：

• 中間有空隙：空隙裡的字母，排在前面的都結束得更早、排在後面的都開始得更晚，沒有任何一筆用到它。刪掉它，每一筆都還完整地在 \(S\) 裡，\(S\) 卻變短了——不可能。第一筆前面、最後一筆後面也一樣不能有多的字母（圖 1 ①）。
• 所以相鄰兩筆一定重疊（重疊 \(0\) 個就是剛好緊貼）：前一筆的最後 \(L\) 個字母和後一筆的前 \(L\) 個字母是 \(S\) 裡的同一段，\(L\) 是一種合法的重疊，不會超過最大重疊。\(S\) 就是從第一筆開始，一筆一筆接上「去掉重疊之後剩下的部分」。
• 重疊比最大重疊少：把這一對改成用最大重疊接（後面整段往左推），每一筆都還完整地在裡面，\(S\) 又變短了——也不可能（圖 1 ②）。

所以，最短的 \(S\) 一定是某個順序、相鄰兩筆都用最大重疊接起來的結果（圖 1 ③）。反過來，任何一個順序這樣接起來，每一筆都在裡面，都是合格的 \(S\)。於是只要把 \(m\) 筆的所有順序都試一遍、每一種都用最大重疊接起來：裡面最短的那些，就是全部的最短 \(S\)，再從中挑字典序最小的。\(k \le 9\) 很小，順序最多 \(9! = 362880\) 種，試得完。

全部順序都試一遍：先比長度，再比接出來的字串

1. 去重：讀入後排序，一模一樣的就會排在一起，和前一個相同的跳過。
2. 最大重疊先算好：ov[i][j] 是 w[i] 後面接 w[j] 的最大重疊。\(L\) 從 \(n - 1\) 往下試，第一個對上的就是最大的；都對不上就是 \(0\)。
3. 枚舉順序：order 從排好序的 \(0, 1, \ldots, m - 1\) 開始，用 next_permutation 走過全部 \(m!\) 種。第一筆也要試遍——範例 2 的答案是從 aaba 開始，不是從最小的 aaaa。每一種順序從 w[order[0]] 開始，之後每一筆只接上「去掉重疊之後剩下的部分」。
4. 比較：先比長度，一樣長才比字典序。

一樣長的時候，要比的是接出來的字串，不是順序本身。看三筆 aab、abb、bab，照 next_permutation 走到的先後：

最短的是前兩種。先走到的第一種接出 aabbab，第二種接出的 aababb 卻比較小（圖 2）：兩種接法露出來的都是 b 和 ab 兩段，只是先後不同，第 \(4\) 個字母一個是 b、一個是 a。順序排在前面，不代表接出來的字串比較小，所以留下第一個最短的順序會答錯。範例 1 比第一個字母就分出大小，範例 2 長度 \(9\) 的答案只有一個，兩個範例都測不出這件事。

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<string> raw(k);
    for (int i = 0; i < k; i++) cin >> raw[i];

    sort(raw.begin(), raw.end());                 // 一模一樣的會排在一起
    vector<string> w;                             // 去重後的探測結果
    for (int i = 0; i < k; i++)
        if (i == 0 || raw[i] != raw[i - 1]) w.push_back(raw[i]);
    int m = w.size();

    // ov[i][j]：w[i] 後面接 w[j]，最多能重疊幾個字母
    vector<vector<int>> ov(m, vector<int>(m, 0));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            for (int len = n - 1; len >= 1; len--)    // 從長的往短的試
                if (w[i].substr(n - len) == w[j].substr(0, len)) {
                    ov[i][j] = len;                   // 第一個對上的就是最多的
                    break;
                }

    vector<int> order(m);                         // 接的順序：w[order[0]]、w[order[1]]、……
    for (int i = 0; i < m; i++) order[i] = i;     // 從排好序的 0, 1, ..., m - 1 開始
    string best = "";                             // 目前最好的 S（空字串＝還沒有）
    do {
        string s = w[order[0]];
        for (int t = 1; t < m; t++)               // 後一筆只接上重疊以外的部分
            s += w[order[t]].substr(ov[order[t - 1]][order[t]]);
        if (best == "" || s.size() < best.size() || (s.size() == best.size() && s < best))
            best = s;                             // 先比長度，一樣長才比字典序
    } while (next_permutation(order.begin(), order.end()));

    cout << best << '\n';
    return 0;
}

\(9! = 362880\) 種順序，每一種最多接出 \(72\) 個字母，一共要接大約 \(362880 \times 72 \approx 2.6 \times 10^7\) 個字母；本站實測最慢的一筆約 \(0.2\) 秒。

測過再交：範例沒測到的

範例 1 的兩筆完全接不上，比第一個字母就分出大小；範例 2 的答案相鄰兩筆都重疊 \(3\) 個字母，長度 \(9\) 的答案也只有一個。沒蓋到的：一樣長的接法要比字串、先接重疊最多的反而吃虧、一對字串有兩種重疊、重疊不到 \(n - 1\) 個、重複的輸入、\(n = 1\)、最大的輸入。

七筆都親眼看過正確，這題就穩了。