HDU 2651 Spring festival couplets：對聯配對計數與模式匹配

題目大意

給定 n (≤110,000) 條春聯，每條由大寫字母組成，長度 ≤8。
兩條春聯可配對，若它們的「字符模式」相同。
模式定義：將字串中每個字符替換為其首次出現的位置索引。
例：AABBCCDD → 00112233，BBDDEEFF → 00112233，兩者可配對。
求最多可組成多少對（每條春聯最多用一次）。

模式標準化

string normalize(const string& s) {
    int map[26]; fill(begin(map), end(map), -1);
    string pat; int idx = 0;
    for (char c : s) {
        int id = c - 'A';
        if (map[id] == -1) map[id] = idx++;
        pat.push_back('0' + map[id]);
    }
    return pat;
}

AABBCCDD → 00112233、AABCCD → 001223、AAA → 000

計數配對

使用 unordered_map 統計每種模式出現次數，每種模式可組成 cnt/2 對。
總對數 = Σ cnt_i / 2。

完整解法

#include 
using namespace std;

string normalize(const string& s) {
    int mp[26]; fill(mp, mp+26, -1);
    string r; int nxt = 0;
    for (char c : s) {
        int id = c - 'A';
        if (mp[id] == -1) mp[id] = nxt++;
        r.push_back(char('0' + mp[id]));
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    while (cin >> n) {
        unordered_map cnt;
        string s;
        for (int i = 0; i < n; ++i) {
            cin >> s;
            ++cnt[normalize(s)];
        }
        long long ans = 0;
        for (auto& [pat, c] : cnt) ans += c / 2;
        cout << ans << "\n";
    }
    return 0;
}

複雜度

• 時間：O(n × L)，L ≤ 8 為字串長度
• 空間：O(n) 儲存模式計數

測試樣例

輸入:
6
ABCCCDA
LLLMNNO
DEZZZBF
AAABCCD
KKKXPPQ
AAA

輸出:
4

模式分析：
ABCCCDA → 0122230
LLLMNNO → 0001233
DEZZZBF → 0122234
AAABCCD → 0001223
KKKXPPQ → 0001223 ← 與上同模式，可配 1 對
AAA → 000
另有 3 對其他模式各自配對，共 4 對。