题解：P11482 [NordicOI 2021] Pearls

zhangshiyan · 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;
}