题解：P16287 [蓝桥杯 2026 省 Python A 组] 单词合并

· · 题解

P16287 [蓝桥杯 2026 省 Python A 组] 单词合并

题目意思

统计有序对 (s_i,s_j) 满足 s_i 恰好一次插入或删除字符变成 s_j(i≠j)。

思路

  1. 把所有单词存入哈希集合，实现 O(1) 快速查找。
  2. 对每一个单词 s_i，生成它一次操作能得到的所有字符串（删字符 + 插字符）。
  3. 用临时unordered_set给生成的字符串去重，避免重复统计。
  4. 统计这些生成的字符串中，存在于总单词集合的数量，累加就是答案。

:::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
int n,ans;
string s[10010];
unordered_set<string> st;// 哈希集合：O(1)查找
unordered_set<string> t;// 临时set：去重，避免重复统计
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for (int i = 1;i <= n;i++){
        cin>>s[i];
        st.insert(s[i]);
    }
    for (int i = 1;i <= n;i++){
        // 操作1：删除任意一个字符（长度-1）
        for (int j = 0;j < s[i].size();j++)
            t.insert(s[i].substr(0,j) + s[i].substr(j + 1));
        // 操作2：在任意位置插入任意小写字母（长度+1）
        // 注意：必须是j <= s[i].size(),因为插入位置是 0 ~ s[i].size()
        for (int j = 0;j <= s[i].size();j++)
            for (char k = 'a';k <= 'z';k++)
                t.insert(s[i].substr(0,j) + k + s[i].substr(j));
        // 统计临时set中存在于总集合的数量，累加答案
        for (const string &x : t)
            if (st.count(x))
                ans++;
        // 删除t中的元素，保证下一次统计
        t.clear();
    }
    cout<<ans;
    return 0;
}

:::

AC记录