跳至正文

1 条题解

  • 0
    @ 2026-10-7 20:23:14

    【本题解由站长编写】

    预处理两个单词间最短的合法重叠,重叠必须非空且短于两个单词。深搜时每个输入单词最多用两次。相同拼写的输入行可以合并计数;用剩余次数和末尾单词记忆化,拒绝重复到达且长度更短的状态,并用仍可到达单词的最大增量作为上界剪枝,避免大量重复单词导致重复搜索。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    int n, best = 0;
    vector<string> w;
    int available[25], maxGain[25], ovl[25][25];
    unsigned long long radix[25];
    bool reachable[25][25];
    unordered_map<unsigned long long, int> memo;
    int overlap(const string &a, const string &b) {
        int lim = min(a.size(), b.size()) - 1;
        for (int l = 1; l <= lim; l++) {
            bool ok = true;
            for (int i = 0; i < l; i++) if (a[a.size()-l+i] != b[i]) { ok = false; break; }
            if (ok) return l;
        }
        return 0;
    }
    void dfs(int len, int last, unsigned long long state) {
        best = max(best, len);
        int upper = len;
        for (int j = 0; j < n; ++j) if (reachable[last][j]) upper += available[j] * maxGain[j];
        if (upper <= best) return;
        unsigned long long key = state * n + last;
        auto found = memo.find(key);
        if (found != memo.end() && found->second >= len) return;
        memo[key] = len;
        for (int j = 0; j < n; j++)
            if (available[j] && ovl[last][j] > 0) {
                available[j]--;
                dfs(len + (int)w[j].size() - ovl[last][j], j, state - radix[j]);
                available[j]++;
            }
    }
    int main() {
        int count; cin >> count;
        map<string, int> frequencies;
        for (int i = 0; i < count; ++i) { string s; cin >> s; frequencies[s] += 2; }
        for (const auto &entry : frequencies) { available[w.size()] = entry.second; w.push_back(entry.first); }
        n = w.size();
        char st; cin >> st;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            ovl[i][j] = overlap(w[i], w[j]);
            reachable[i][j] = ovl[i][j] > 0;
            if (ovl[i][j]) maxGain[j] = max(maxGain[j], (int)w[j].size() - ovl[i][j]);
        }
        for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j)
            reachable[i][j] = reachable[i][j] || (reachable[i][k] && reachable[k][j]);
        unsigned long long state = 0, product = 1;
        for (int i = 0; i < n; ++i) { radix[i] = product; state += available[i] * product; product *= available[i] + 1; }
        for (int i = 0; i < n; i++)
            if (w[i][0] == st) {
                available[i]--;
                dfs(w[i].size(), i, state - radix[i]);
                available[i]++;
            }
        cout << best << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4258
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者