Pearls 题解

题目分析

Laura 有两条项链 A 和 B，她想用它们制作一条新项链。制作规则如下：

• 对于 A 中的每个珠子，与 B 中的每个珠子组合
• 如果组合 A[i]B[j] 不在丑陋组合列表中，就将这个双字符添加到新项链末尾
• 有 q 个查询，每个查询问新项链中第 t 个位置的字符是什么

关键难点：

• LA, LB 最大 2×10⁵，总组合数可能达到 4×10¹⁰，无法显式构造新项链
• k < 676 (26²)，丑陋组合数量较少
• q 最大 10⁵，需要高效回答查询

解题思路

核心观察

新项链由若干长度为 2 的"组合"拼接而成。对于位置 t：

• 组合索引 = t / 2
• 在组合内的偏移 = t % 2

我们需要找到第 comb_idx 个合法组合，然后根据偏移输出 A 字符或 B 字符。

高效算法

1. 预处理合法矩阵

   • 建立 allowed[26][26] 数组
   • 初始全 1，对每个丑陋组合设为 0

2. 统计 B 中字符频率

   • cntB[26] 记录 B 中每种字符出现次数

3. 计算每个 A 字符的合法组合数

   • valid_count[c] = Σ(allowed[c][d] × cntB[d])

4. 计算前缀和

   • prefix_count[i] 表示 A 的前 i 个字符能产生的合法组合总数
   • 用于快速定位组合对应的 A 字符

5. 预处理累积计数

   • cum[c][d] 表示字符 c 的合法 B 字符中，前 d 个字母的累积数量
   • 用于快速找到第 k 个合法的 B 字符

6. 回答查询

   • 二分查找找到对应的 A 字符
   • 在合法 B 字符中找到对应的 B 字符
   • 根据偏移输出相应字符

C语言实现

#include <stdio.h>
#include <string.h>

#define MAXL 200005
#define ALPHA 26

int LA, LB, k, q;
char A[MAXL], B[MAXL];
int allowed[ALPHA][ALPHA];
int cntB[ALPHA];
long long valid_count[ALPHA];
long long prefix_count[MAXL];
int cum[ALPHA][ALPHA + 1];

int main() {
    // 读取输入
    scanf("%d %d %d %d", &LA, &LB, &k, &q);
    scanf("%s %s", A, B);
    
    // 初始化允许矩阵
    for (int i = 0; i < ALPHA; i++) {
        for (int j = 0; j < ALPHA; j++) {
            allowed[i][j] = 1;
        }
    }
    
    // 读取丑陋组合
    for (int i = 0; i < k; i++) {
        char x[3], y[3];
        scanf("%s %s", x, y);
        allowed[x[0] - 'a'][y[0] - 'a'] = 0;
    }
    
    // 统计B中字符频率
    for (int i = 0; i < LB; i++) {
        cntB[B[i] - 'a']++;
    }
    
    // 计算每个A字符的合法组合数
    for (int c = 0; c < ALPHA; c++) {
        valid_count[c] = 0;
        for (int d = 0; d < ALPHA; d++) {
            if (allowed[c][d]) {
                valid_count[c] += cntB[d];
            }
        }
    }
    
    // 计算前缀和
    prefix_count[0] = 0;
    for (int i = 0; i < LA; i++) {
        int c = A[i] - 'a';
        prefix_count[i + 1] = prefix_count[i] + valid_count[c];
    }
    
    // 预处理累积计数
    for (int c = 0; c < ALPHA; c++) {
        cum[c][0] = 0;
        for (int d = 0; d < ALPHA; d++) {
            cum[c][d + 1] = cum[c][d];
            if (allowed[c][d]) {
                cum[c][d + 1] += cntB[d];
            }
        }
    }
    
    // 处理查询
    while (q--) {
        long long t;
        scanf("%lld", &t);
        
        long long comb_idx = t / 2;
        int offset = t % 2;
        
        // 二分查找找到对应的A字符
        int low = 0, high = LA;
        while (low < high) {
            int mid = (low + high) / 2;
            if (prefix_count[mid] > comb_idx) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        
        int a_idx = low - 1;
        char a_char = A[a_idx];
        int a_code = a_char - 'a';
        
        // 在该A字符的合法组合中找第local_idx个
        long long local_idx = comb_idx - prefix_count[a_idx];
        
        // 找到对应的B字符
        char b_char = 'a';
        for (int d = 0; d < ALPHA; d++) {
            if (local_idx < cum[a_code][d + 1]) {
                b_char = 'a' + d;
                break;
            }
        }
        
        // 输出结果
        if (offset == 0) {
            printf("%c\n", a_char);
        } else {
            printf("%c\n", b_char);
        }
    }
    
    return 0;
}

算法复杂度分析

• 预处理阶段：

  • 初始化允许矩阵：O(26²)
  • 统计B字符频率：O(LB)
  • 计算合法组合数：O(26²)
  • 计算前缀和：O(LA)
  • 预处理累积计数：O(26²)
  • 总预处理复杂度：O(LA + LB + 26²)

• 查询处理：

  • 每个查询：二分查找 O(log LA) + 遍历26个字母 O(26)
  • 总查询复杂度：O(q × (log LA + 26))

关键点说明

1. 合法矩阵：利用 k < 676 的特点，用小型矩阵记录所有可能组合的合法性。

2. 前缀和：通过前缀和快速确定某个组合对应的 A 字符。

3. 累积计数：对每个 A 字符，预先计算合法 B 字符的累积数量，便于快速查找第 k 个合法 B 字符。

4. 二分查找：在前缀和数组上使用二分查找，快速定位组合对应的 A 字符索引。

样例验证

样例1

输入：
4 2 1 2
abcb
cc
c a
3
12
输出：
c
b

样例2

输入：
4 2 2 2
cbaa
ac
b c
a a
7
7
输出：
c
c

该解法充分利用了题目条件，在预处理阶段完成大部分计算，使得每个查询都能在常数时间内完成，完美满足大数据量的要求。