题解：P13867 [SWERC 2020] Unique Activities

题目传送门

首先让我们来理解一下题意，其实题目就是让我们输出最短的只出现了一次的子串。

那么我们可以考虑暴力，枚举起点和长度，然后算一下哈希值，看有没有出现过即可。

CPP

#include <bits/stdc++.h>
#define ull unsigned long long
#define int long long
using namespace std;
const int N = 3e5 + 5;
map<ull, int> mp;
int hs[N], pw[N];
ull get_hash(int l, int r)
{
    return hs[r] - hs[l - 1] * pw[r - l + 1];
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin >> s;
	int len = s.size();
	s = " " + s;
	pw[0] = 1;
	for (int i = 1; i <= len; i++)
	{
		hs[i] = hs[i - 1] * 131 + (s[i] - 'a' + 1);
		pw[i] = pw[i - 1] * 131;
	}
	for (int L = 1; L <= len; L++)
	{
		for (int l = 1; l + L - 1 <= len; l++) //枚举起点，统计子串
		{
			int r = l + L - 1;
			ull num = get_hash(l, r); //提取出哈希值
			mp[num]++;
		}
		for (int l = 1; l + L - 1 <= len; l++) //枚举起点，看这个字串有没有出现过
		{
			int r = l + L - 1;
			ull num = get_hash(l, r);
			if (mp[num] == 1) //如果只出现过一次
			{
				cout << s.substr(l, L); //输出答案
				return 0;
			}
		}
	}
	return 0;
}

然而

75

分。

但是我们看到

n

的范围最大能达到

300000

，所以我们换一种思路。

不难发现，重复的子串长度具有单调性，长度为

len

的子串只出现了一次，那么长度大于

len

的字串肯定最多出现一次。

既然有单调性，那么我们可以考虑二分答案。枚举所有长度为

mid

的子串，截取这一段的哈希值，用桶维护起来，如果这个哈希值之前已经出现过了，说明这个子串在之前出现过。将长度调大，否则就减小。

那么代码就非常好写了。

CPP

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N = 3e5 + 5;
string s;
int n, id;
ull hs[N], pw[N];
map<ull, int> mp;
ull get_hash(int l, int r) 
{
	return hs[r] - hs[l - 1] * pw[r - l + 1];
}
bool check(int mid) //判断长度为mid的子串是否能只出现一次
{
	mp.clear();
	for (int i = 1; i + mid - 1 <= n; i++)
	{
		int j = i + mid - 1;
		mp[get_hash(i, j)]++;
	}
	for (int i = 1; i + mid - 1 <= n; i++) 
	{
		int j = i + mid - 1;
		if (mp[get_hash(i, j)] == 1) 
		{
			id = i; //存储可行的起点
			return 1;
		}
	}
	return 0;
}
signed main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> s;
	n = s.size();
	s = ' ' + s;
	pw[0] = 1;
	for (int i = 1; i <= n; i++) 
	{
		hs[i] = hs[i - 1] * 131 + (s[i] - 'A' + 1);
		pw[i] = pw[i - 1] * 131;
	}
	int l = 0, r = n + 1;
	while (l + 1 < r) 
	{
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid;
	}
	cout << s.substr(id, r);
	return 0;
}

题解：P13867 [SWERC 2020] Unique Activities

文章操作

题目传送门

相关推荐

评论

题解：P13867 [SWERC 2020] Unique Activities