自动搬运

查看原文

来自洛谷，原作者为

	zhangshiyan 这个家伙很勤劳，什么也没有留下 | ENFJ-A | 可互关 （信誉良好）| CS2 完美D+ | IP属地: 福建 | 现役 OIer，服役 FZSZ

搬运于2025-08-24 23:07:45，当前版本为作者最后更新于2025-01-04 17:09:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P11482 [NordicOI 2021] Pearls

R197070983 记录详情

Solution

思维题

暴力 16pts

先考虑暴力怎么做。

暴力遍历每一个 $a_i$ 和 $b_j$，判断它们如果不是一对丑陋对，就将 $a_i$ 和 $b_j$ 分别加入字符串 $ans$ 中，对于每一个查询输出 $ans_{t_i}$。

这样的时间和空间复杂度为 $O(la\times lb)$。

伪代码：

int main()
{
	ll la = read(), lb = read(), k = read(), q = read();
	string a, b;
	cin >> a >> b;
	bool vis[256][256] = {0}; //判断每个丑陋对
	for(ll i = 1; i <= k; i++)
	{
		char a, b;
		cin >> a >> b;
		vis[a][b] = 1;
	}
	string ans;
	for(ll i = 0; i < la; i++)
	{
		for(ll j = 0; j < lb; j++)
		{
			if(!vis[a[i]][b[j]])
			{
				ans += a[i];
				ans += b[j];
			}
		}
	}
	while(q--)
	{
		ll t = read();
		cout << ans[t] << endl;
	}
	return 0;
}

正解 100pts

在暴力的基础上考虑怎么优化。

题目中保证了字符串 $a$ 和 $b$ 只存在小写字母，而且 $1\le la \le 200000$，不难发现暴力存储的字符串 $ans$ 中就会有很多重复的字串。

我们就可以采用分块的思想，对于每一个字符 $a$ 到 $z$ 与每一个 $b_j$，判断是否是丑陋对，如果不是就加入字符串 $ans[i]$ 中，表示对于字符 $a$ 到 $z$ 与字符串 $b$ 组成的项链，然后再用前缀和和二分查找优化查询，这样就大大优化了时间和空间复杂度为 $O(26\times lb)$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF (ll)1e18

ll read()
{
	ll x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-')
		{
			f = -1;
		}
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

bool vis[256][256];//判断每个丑陋对
string ans[400005];
ll sum[200005];

int main()
{
	ll la = read(), lb = read(), k = read(), q = read();
	string a, b;
	cin >> a >> b;
	for(ll i = 1; i <= k; i++)
	{
		char a, b;
		cin >> a >> b;
		vis[a][b] = 1;
	}
	for(ll i = 'a'; i <= 'z'; i++)
	{
		for(ll j = 0; j < lb; j++)
		{
			if(!vis[i][b[j]])
			{
				ans[i] += i;
				ans[i] += b[j];
			}
		}
	}
	sum[0] = ans[a[0]].size();
	for(ll i = 1; i < la; i++)
	{
		sum[i] = sum[i - 1] + ans[a[i]].size();
	}
	while(q--)
	{
		ll t = read();
		ll i = upper_bound(sum, sum + la, t) - sum;
		if(i)
		{
			t -= sum[i - 1];
		}
		cout << ans[a[i]][t] << endl;
	}
	return 0;
}