题解：P12838 [蓝桥杯 2025 国 B] 子串去重

· · 题解

题目传送门

观察到 |\Sigma|=26（\Sigma 为字符集），所以去完重后两个串最多长 |\Sigma|，我们可以暴力比较。于是问题转移到了如何给一个子串去重。我们可以记录一个数组 idx_i，第 i 位为一个 vector，表示第 i 个字母在串中出现的下标。这样我们枚举字母，然后用二分求出第一次出现的位置，最后给下标排序就可以了。时间复杂度 O(|\Sigma|m\log n)，可以通过。

#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef long long ll;
const int N = 1e5 + 10;
priority_queue<pair<int, int> > q;
vector<int> idx[26];
string s;
il string calc(int tl, int tr)
{
    for(int i = 0;i < 26;++i)
    {
        if(idx[i].empty()) continue;
        int l = 0, r = idx[i].size() - 1;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(idx[i][mid] >= tl) r = mid;
            else l = mid + 1;
        }
        if(idx[i][l] > tr || idx[i][l] < tl) continue;
        q.push(make_pair(-idx[i][l], i));
    }
    string ans = "";
    while(q.size())
    {
        ans.push_back((char)(q.top().second + 'a'));
        q.pop();
    }
    return ans;
}
il int solve(string a, string b)
{
    int cnt = 0;
    for(int i = 0;i < min(a.size(), b.size());++i) cnt += (a[i] != b[i]);
    return cnt + max(a.size(), b.size()) - min(a.size(), b.size());
}
int main()
{
    cin >> s;
    int n = s.size(), m;
    s = " " + s;
    cin >> m;
    for(int i = 1;i <= n;++i) idx[s[i] - 'a'].push_back(i);
    while(m--)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        cout << solve(calc(l1, r1), calc(l2, r2)) << "\n";
    }
    return 0;
}