专栏文章

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

AA7F3jK9pR0xf_
P12838题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minkl071
此快照首次捕获于
2025/12/02 03:56
3 个月前
此快照最后确认于
2025/12/02 03:56
3 个月前
查看原文

题目传送门

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...