數位占卜 題解｜APCS 2022 年 1 月中高級 第 3 題

前置知識

這題的核心推導（一對籤長什麼樣子）下面會從頭講；要先會的是：

• string 的切割與比較：s.substr(起點, 長度) 取一段、==／!= 直接比兩個字串、+ 接起來。
• set 查「某個字串在不在裡面」：NTUCPC Guide〈Set 與 Map〉——insert 放進去、count(x) 問有沒有，各 \(O(\log m)\) 次字串比較；想更快可以換成同一份教材裡的 unordered_set，用法一樣。

簡潔題意

籤筒裡有 \(m\) 支籤，每支是一個互不相同的小寫字母字串。抽出兩支不同的籤 \(S\)、\(T\)，把兩個字串接起來，如果能拆成左右兩半完全一樣（寫成 \(XX\)，\(X\) 非空），這兩支就是一對「聖筊」。題目保證：如果 \(S + T\) 是聖筊，\(T + S\) 也一定是，所以一對只算一次。問 \(m\) 支籤裡有幾對（\(1 \le m \le 5 \times 10^4\)，每支籤長度 \(1\) 到 \(100\)）。

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

• 子題組 1（\(20\) 分）：\(2 \le m \le 100\)，字串長度只會是 \(10\) 或 \(20\)。
• 子題組 2（\(20\) 分）：字串長度只會是 \(10\) 或 \(20\)。
• 子題組 3（\(60\) 分）：無額外限制。

先拿下 20 分：每一對都接起來看

子題組 1 最多 \(100\) 支籤、\(4950\) 對，每一對接起來、檢查長度是偶數而且前半等於後半就好。題目說兩種順序同時成立或同時不成立，所以每一對只要接一種順序。

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

bool isDouble(string s) {                    // s 能不能寫成 XX
    int len = s.size();
    if (len % 2 != 0) return false;
    return s.substr(0, len / 2) == s.substr(len / 2);
}

int main() {
    int m;
    cin >> m;
    vector<string> w(m);
    for (int i = 0; i < m; i++) cin >> w[i];
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {        // 每一對只看一次
            if (isDouble(w[i] + w[j])) count++;
        }
    }
    cout << count << endl;
    return 0;
}

\(m = 5 \times 10^4\) 時有 \(1.25 \times 10^9\) 對，每對都要接字串、比字串，本站實測 \(90\) 到 \(120\) 秒，時限 \(2\) 秒。子題組 1 的 \(20\) 分穩穩到手。

一對籤長什麼樣：長的那支是 \(UVU\)，短的那支是 \(V\)

兩支籤接起來是 \(XX\)，先看長度：兩支一樣長的話，\(X\) 就是前一支、也是後一支，兩支相同——題目保證籤互不相同，所以一對裡一定一長一短。設長的那支是 \(A\)（長度 \(a\)）、短的是 \(B\)（長度 \(b\)），\(A + B = XX\)，\(X\) 的長度 \(k = (a + b) / 2\)，比 \(a\) 短。\(A\) 的前 \(k\) 個字就是 \(X\)；\(A\) 剩下的後 \(a - k\) 個字是第二個 \(X\) 的開頭，也就是 \(A\) 自己的前 \(a - k\) 個字；\(B\) 則是第二個 \(X\) 剩下的部分。令 \(d = a - k = (a - b) / 2\)，整理起來就是（圖 1）：

• \(A\) 的前 \(d\) 個字等於後 \(d\) 個字——這一段叫它 \(U\)；
• \(A\) 去掉前後各 \(d\) 個字剩下的中間那段，就是 \(B\)——叫它 \(V\)。

所以 \(A = UVU\)、\(B = V\)。反過來，只要 \(A = UVU\) 而且 \(V\) 也在籤筒裡，\(A + V = UVUV = (UV)(UV)\)、\(V + A = VUVU = (VU)(VU)\) 都是聖筊——這也解釋了為什麼題目敢說「順序反過來也成立」。

從 20 分到 100 分：對每支籤枚舉 \(U\) 的長度

把每支籤 \(s\) 都當成「一對裡長的那支」：枚舉 \(U\) 的長度 \(d\)（\(d \ge 1\)，而且中間至少要留一個字，所以 \(2d < |s|\)），檢查前 \(d\) 個字是否等於後 \(d\) 個字，是的話把中間那段切出來，到 set 裡查它是不是一支籤。每一對只會被長的那支數到一次；同一支籤不同的 \(d\) 切出來的中間段長度不同，也不會重複數。

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

int main() {
    int m;
    cin >> m;
    vector<string> w(m);
    set<string> all;                             // 所有的籤，查「某個字串在不在裡面」
    for (int i = 0; i < m; i++) {
        cin >> w[i];
        all.insert(w[i]);
    }
    int count = 0;
    for (int i = 0; i < m; i++) {
        string s = w[i];                         // 把 s 當成一對裡比較長的那支
        int len = s.size();
        for (int d = 1; 2 * d < len; d++) {      // U 的長度 d，中間 V 至少要留一個字元
            if (s.substr(0, d) != s.substr(len - d)) continue;   // 前 d 個和後 d 個要一樣
            if (all.count(s.substr(d, len - 2 * d))) count++;    // 中間那段 V 是另一支籤
        }
    }
    cout << count << endl;
    return 0;
}

每支籤最多枚舉 \(49\) 個 \(d\)，每次比較前後綴、切中間、查 set，單次最多幾百次字元比較；\(5 \times 10^4\) 支籤粗估上界是幾億次，但前後綴的比較絕大多數第一個字就分出勝負、set 裡的比較也很少比到底，最大測資本站實測 \(0.4\) 秒。答案最多 \(5 \times 10^4 \times 49 \approx 2.5 \times 10^6\)，int 夠用。

子題組 2 的字串長度只有 \(10\) 或 \(20\)，一對只可能是「\(20\) 配 \(10\)」、\(d\) 只能是 \(5\)——滿分解直接涵蓋，不用另外寫。

測過再交：範例裡每支籤最多只配到一對

兩個範例裡，長的那支只有一個 \(d\) 會成功；沒蓋到的是：只有一支籤、兩支「看起來很像」但接起來不是 \(XX\)（驗判斷不能只看重複）、\(V\) 比 \(U\) 長、同一支籤有兩個 \(d\) 都成功、以及最大的 \(m\)（驗速度）。

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