笔试时间：2025年10月11日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

小铭有一个长度为n的字符串s，该字符串由m种小写英文字母组成，该字符串会经过q轮迭代，每一轮迭代前会先给出字符集的排列，字符在排列中出现的位置越靠前，则表明该字符在该轮迭代中优先级更高。每一轮迭代中，优先级更高的字符会同时"消灭"右侧优先级更低的相邻字符。

你需要回答经过q轮迭代后，字符串是否只剩下一种字符。如果是，输出一行"YES"，然后输出最早第几轮迭代后字符串只剩下一种字符、迭代结束后字符串的长度；否则，输出一行"NO"，然后输出一行迭代结束后的字符串。

输入描述

输入包括多组测试数据。 输入第一行有一个正整数T，表示测试数据的组数。 每组测试数据的第一行有两个正整数n和m(1≤n≤10^5, 2≤m≤26)，表示字符串的长度和字符集的大小； 接下来一行有一个由不重复小写英文字母组成的字符串，表示构成题目给定字符串的字符集； 接下来一行有一个由小写英文字母组成的字符串s，表示题目给定的字符串； 接下来一行有一个正整数q(1≤q≤10^5)，表示迭代的轮数； 接下来q行每行有一个字符集的排列，表示每一轮迭代中各个字符的优先级。 保证每个测试点的所有测试数据的n的和不超过10^5、q的和不超过10^5，保证题目给定字符串至少由两种字符构成。

输出描述

对于每组测试数据，如果迭代结束后字符串只剩下一种字符，则输出一行"YES"，然后在第二行分别输出最早第几轮迭代后字符串只剩下一种字符、迭代结束后字符串的长度；否则输出一行"NO"，然后在第二行输出迭代结束后的字符串。

样例输入

2

8 6

ceilov

iloveice

2

ievolc

loveci

5 2

ab

aaabb

2

ab

ab

样例输出

NO

ioe

YES

2 3

样例说明： 对于第一组样例，第一轮迭代后字符串变成iovsie，第二轮迭代后字符串变成ioe，包含三种字符，输出一行"NO"； 对于第二组样例，第一轮迭代后字符串变成aaab，第二轮迭代后字符串变成aaa，仅剩一种字符，最早第二轮迭代后只剩下一种字符，迭代结束后字符串长度为3，输出一行"YES"、一行2和3。

参考题解

解题思路： 每轮迭代中，遍历字符串，根据给定的优先级顺序，标记需要删除的字符（优先级高的字符会消灭右侧相邻的优先级低的字符）。然后重新构建字符串，删除被标记的字符。记录是否在某轮迭代后只剩一种字符。

C++：

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

void solve() {
    int n, m;
    cin >> n >> m;
    string charset;
    cin >> charset;
    string s;
    cin >> s;
    int q;
    cin >> q;
    
    int ans = -1;
    for (int r = 1; r <= q; r++) {
        string p_str;
        cin >> p_str;
        
        if (s.length() > 1) {
            map<char, int> mp;
            for (int i = 0; i < p_str.length(); i++) {
                mp[p_str[i]] = i;
            }
            
            vector<int> rm(s.length(), 0);
            int i = 0;
            while (i < s.length() - 1) {
                if (mp[s[i]] < mp[s[i + 1]]) {
                    rm[i + 1] = 1;
                }
                i++;
            }
            
            string ns = "";
            for (int i = 0; i < s.length(); i++) {
                if (!rm[i]) {
                    ns += s[i];
                }
            }
            s = ns;
            
            if (ans == -1) {
                set<char> uniqueChars(s.begin(), s.end());
                if (uniqueChars.size() <= 1) {
                    ans = r;
                }
            }
        }
    }
    
    if (ans != -1) {
        cout << "YES\n";
        cout << ans << " " << s.length() << "\n";
    } else {
        cout << "NO\n";
        cout << s << "\n";
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        String charset = sc.next();
        String s = sc.next();
        int q = sc.nextInt();
        
        int ans = -1;
        for (int r = 1; r <= q; r++) {
            String pStr = sc.next();
            
            if (s.length() > 1) {
                Map<Character, Integer> mp = new HashMap<>();
                for (int i = 0; i < pStr.length(); i++) {
                    mp.put(pStr.charAt(i), i);
                }
                
                boolean[] rm = new boolean[s.length()];
                int i = 0;
                while (i < s.length() - 1) {
                    if (mp.get(s.charAt(i)) < mp.get(s.charAt(i + 1))) {
                        rm[i + 1] = true;
                    }
                    i++;
                }
                
                StringBuilder ns = new StringBuilder();
                for (int j = 0; j < s.length(); j++) {
                    if (!rm[j]) {
                        ns.append(s.charAt(j));
                    }
                }
                s = ns.toString();
                
                if (ans == -1) {
                    Set<Character> uniqueChars = new HashSet<>();
                    for (char c : s.toCharArray()) {
                        uniqueChars.add(c);
                    }