题解

题目描述

给定两个字符串 $A$ 和 $B$，以及一个转换数组 $X$，需要通过调整 $X$ 和 $B$ 的顺序，使得替换后的字符串 $A'$ 的字典序最小。替换规则为：遍历调整后的 $X$，将 $B$ 中的字符依次替换到 $A$ 的对应位置，最后一次替换的字符决定该位置的最终值。

思路分析

这道题的核心是通过调整转换数组 $X$ 和字符串 $B$ 的顺序，使得替换后的字符串 $A'$ 的字典序最小。具体步骤是：首先统计每个位置在 $X$ 中的出现次数，收集所有被替换的位置并按升序排列；然后将字符串 $B$ 的字符按升序排序，并将排序后的字符依次分配给被替换的位置，确保前面的位置使用更小的字符，从而保证最终字符串的字典序最小。

1. 统计替换次数：对于每个位置 $i$，统计其在 $X$ 中的出现次数 cnt[i]。
2. 收集被替换的位置：收集所有至少被替换一次的位置，并按升序排列。
3. 排序字符：将字符串 $B$ 的字符按升序排序。
4. 分配字符：将排序后的 $B$ 的前 $k$ 个字符依次分配给被替换的位置（按升序排列），确保前面的位置使用更小的字符，从而保证字典序最小。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T; // 读取测试用例数量
    while (T--) {
        int n, m;
        cin >> n >> m; // 读取字符串 A 和 B 的长度
        string A, B;
        cin >> A >> B; // 读取字符串 A 和 B
        vector<int> cnt(n + 1, 0); // 统计每个位置被替换的次数
        for (int i = 0; i < m; ++i) {
            int x;
            cin >> x; // 读取转换数组 X 的元素
            cnt[x]++; // 统计位置 x 被替换的次数
        }
        vector<int> positions; // 收集所有被替换的位置
        for (int i = 1; i <= n; ++i) {
            if (cnt[i] > 0) {
                positions.push_back(i); // 如果位置 i 被替换过，加入列表
            }
        }
        sort(positions.begin(), positions.end()); // 按升序排列被替换的位置
        string sorted_B = B;
        sort(sorted_B.begin(), sorted_B.end()); // 将字符串 B 的字符按升序排序
        int k = positions.size(); // 被替换的位置数量
        string res = A; // 初始化结果为 A
        for (int i = 0; i < k; ++i) {
            int pos = positions[i]; // 获取当前被替换的位置
            res[pos - 1] = sorted_B[i]; // 将排序后的 B 的字符分配给该位置
        }
        cout << res << '\n'; // 输出结果
    }
    return 0;
}

Python

import sys

def main():
    input = sys.stdin.read().split() # 读取所有输入
    ptr = 0
    T = int(input[ptr]) # 读取测试用例数量
    ptr += 1
    for _ in range(T):
        n = int(input[ptr]) # 读取字符串 A 的长度
        m = int(input[ptr+1]) # 读取字符串 B 的长度
        ptr += 2
        A = input[ptr] # 读取字符串 A
        ptr += 1
        B = input[ptr] # 读取字符串 B
        ptr += 1
        cnt = [0] * (n + 1) # 统计每个位置被替换的次数
        for i in range(m):
            x = int(input[ptr]) # 读取转换数组 X 的元素
            ptr += 1
            cnt[x] += 1 # 统计位置 x 被替换的次数
        positions = []
        for i in range(1, n + 1):
            if cnt[i] > 0:
                positions.append(i) # 如果位置 i 被替换过，加入列表
        positions.sort() # 按升序排列被替换的位置
        sorted_B = sorted(B) # 将字符串 B 的字符按升序排序
        k = len(positions) # 被替换的位置数量
        res = list(A) # 初始化结果为 A
        for i in range(k):
            pos = positions[i] # 获取当前被替换的位置
            res[pos - 1] = sorted_B[i] # 将排序后的 B 的字符分配给该位置
        print(''.join(res)) # 输出结果

if __name__ == "__main__":
    main()

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 读取测试用例数量
        while (T-- > 0) {
            String[] nm = br.readLine().split(" ");
            int n = Integer.parseInt(nm[0]); // 读取字符串 A 的长度
            int m = Integer.parseInt(nm[1]); // 读取字符串 B 的长度
            String A = br.readLine(); // 读取字符串 A
            String B = br.readLine(); // 读取字符串 B
            int[] cnt = new int[n + 1]; // 统计每个位置被替换的次数
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < m; i++) {
                int x = Integer.parseInt(st.nextToken()); // 读取转换数组 X 的元素
                cnt[x]++; // 统计位置 x 被替换的次数
            }
            List<Integer> positions = new ArrayList<>(); // 收集所有被替换的位置
            for (int i = 1; i <= n; i++) {
                if (cnt[i] > 0) {
                    positions.add(i); // 如果位置 i 被替换过，加入列表
                }
            }
            Collections.sort(positions); // 按升序排列被替换的位置
            char[] sortedB = B.toCharArray();
            Arrays.sort(sortedB); // 将字符串 B 的字符按升序排序
            int k = positions.size(); // 被替换的位置数量
            char[] res = A.toCharArray(); // 初始化结果为 A
            for (int i = 0; i < k; i++) {
                int pos = positions.get(i); // 获取当前被替换的位置
                res[pos - 1] = sortedB[i]; // 将排序后的 B 的字符分配给该位置
            }
            System.out.println(new String(res)); // 输出结果
        }
    }
}

题目内容

多多最新在研究一种神奇的字符串替换，该字符串可以通过一种方式进行替换，替换后可以得到另一种学符串。 假设给定两个由小写字母组成的字符串$A$和$B$，对应的字符串长度分别为$n$和$m$;另外，还有一个由$m$个元素组成的转换数组$X$={$index_1,index_2,....,index_m$}，数组的元素记录了字符串A中某些元素的下标(字符串中元素的下标从$1$到$n$)，这些元素可能是重复的，也就是$X$数组中任意元素满足:$1<= index_i <=n$。

多多可以通过随意调整数组$X$中元素的顺序，也可以随意调整字符串$B$中元素的顺序。调整顺序之后，多多需要从左向右遍历数组$X$中的元素，假设当前遍历到的是第$i$个元素，该元素的值为$index_i$，多多就会将字符串$A$中第$index_i$个元素替换为字符串$B$中第$i$个元素;就这样，多多一共会替换$m$次，替换后得到的字符串是$A$'

现在，多多想知道通过调整X中元素的顺序，再调整字符串$B$中元素的顺序后，在所有的可能情况下，如何让替换后得到的字符串 $A$'的字典序最小。

输入描述

第一行输入一个数字$T(1<=T<=10^5$) 表示总共有$T$ 组测试数据,对于每组数据，共有4行

第$1$行输入两个数字$n$和$m,(1<=n,m<=10^5)$，分别表示字符串$A$和$B$的长度

第$2$行输入一个长度为$n$的字符串$A$

第$3$行输入一个长度为$m$的字符串$B$

第$4$行输入一个由$m$个正整数组成的数组$X$，其中第$i$个元素是$index_i(1 <=index_i<=n)$

说明:$T$组测试数据的输入$n$的总和加起来不会超过$3*10^5$，$T$组测试数据的输入$m$的总和加起来也不会超过$3*10^5$

输出描述

对于每组测试数据，输出一行字符串，表示替换后字典序最小的字符串$A$'

补充说明

两个不相等的字符串$S1$和$S2$，$S1$比$S2$字典序小是指:

• $S1$是$S2$的子串
• 或者$S1$和$S2$依次对比每一个字母，出现第一个不相同的字母，并且$S1$中的该字母$<S2$中的该字母。

样例1

输入

3
1 1
a
a
1 
1 2
a
bc
1 1
3 6
pdd
testgo
1 2 3 3 2 1

输出

a
b
ego

说明

共有$3$组测试数据。

第一组测试数据，字符串$B$只有一个字母，数组$X$也只有一个元素，所以替换后的结果是：$a$

第二组测试数据，可以调整字符串$B=cb$,数组$X$={$1,1$}，字符串A的替换变化过程是：$a->c->b$,所以替换后的结果是$b$

第三组测试数据，可以调整字符串$B=tgtose$,数组$X$={$2,2,3, 3,1,1$},字符串$A$的替换过程是:$pdd->ptd -> pgd -> pgt -> pgo -> sgo -> ego$,当然可能也有别的替换方式，这里只列举了其中一种，但最终$A$'最小的是$ego$。