笔试时间：2025年8月9日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：字符串min-15

称一个字符串为「完全不协调」，当且仅当：对于任意一种字母，其在字符串中仅有大写或仅有小写形式；对于任意一种字母（不分大小写），其都在字符串中出现过。现在，给定一个长度为 ( n )、仅由大小写字母构成的字符串 ( s )。你需要求解使其变为「完全不协调」需要的最少操作轮数 ( x )。其中，每一轮操作从以下两个方法中选择一个执行：方法一：任选一个字母（大写或小写），将其插入到字符串的任意位置（包括开头和末尾）。方法二：选择一个位于字符串中的字符，将其删除。然而，小美对数字并不感兴趣，她想知道：通过 ( x ) 轮操作能得到的字典序最小的「完全不协调」字符串是什么？【名词解释】 从字符串的第一个字符开始逐个比较，直至发现第一个不同的位置，比较这个位置字符的 ASCII 码，ASCII 码较小（‘A’ < ‘B’ … < ‘Z’ < ‘a’ < … < ‘z’）的字符串字典序也较小；如果比较到其中一个字符串的结尾时依旧全部相同，则较短的字符串字典序更小。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 ( T )（( 1 \le T \le 10^5 )）代表数据组数，每组测试数据描述如下： 第一行输入一个整数 ( n )（( 1 \le n \le 10^5 )），表示原字符串长度； 第二行输入一个长度为 ( n ) 的字符串 ( s )，仅由大小写字母构成。 除此之外，保证单个测试文件的 ( n ) 之和不超过 ( 10^5 )。

输出描述

对于每一组测试数据，新起一行。输出一个字符串，表示 ( x ) 轮操作能得到的字典序最小的「完全不协调」字符串。

样例输入

5

26

abcdefGHIjklmnopqrstuvwxyY

8

CAECGEHG

10

MZbMwEyYdI

20

DTLCOUegMDByFWUrPwBp

19

LKGkheSppLQSsAImtll

样例输出

ZabcdefGHIjklmnopqrstuvwxY

BCADECFGEHGIJKLMNOPQRSTUVWXYZ

ACFGHJKLMNOPQRSTUVXZbMwEYdI

ADHIJKNQSTLCOUVXZegMDByFUrPwB

BCDFGJNORUVWXYZkheSppQSAImtll

说明：对于第一组测试数据，删除了 ( y ) 并在字符串首增加了 ( Z )。

参考题解

统计字母出现情况：首先统计字符串中每个字母的出现情况（大小写分开统计），并确定哪些字母已经存在（无论大小写）。 确定缺失字母：找出所有缺失的字母（即26个字母中未出现的字母）。 处理现有字母的大小写统一：对于每个已经存在的字母，统一成大写或小写。为了使字典序最小，优先选择小写字母，因为小写字母的ASCII码比大写字母大，但若该字母的大写形式在字符串中已经存在，则必须统一成大写。 插入缺失字母：将缺失的字母插入到字符串中。为了使字典序最小，插入的字母应尽可能放在前面，特别是大写字母（因为大写字母的ASCII码较小）。具体来说，插入的大写字母应放在比它大的字符前面，而小写字母应放在合适的位置以保持字典序最小。

C++：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

string solve(string s) {
    // 统计每个字母的大小写出现次数
    vector<int> upper(26, 0), lower(26, 0);
    
    for (char c : s) {
        if (c >= 'A' && c <= 'Z') {
            upper[c - 'A']++;
        } else {
            lower[c - 'a']++;
        }
    }
    
    // 决定每个字母使用大写还是小写
    vector<bool> useUpper(26);
    string result = "";
    
    for (int i = 0; i < 26; i++) {
        if (upper[i] == 0 && lower[i] == 0) {
            // 字母未出现，需要添加，优先使用大写（字典序更小）
            useUpper[i] = true;
        } else if (upper[i] > 0 && lower[i] > 0) {
            // 同时有大小写，保留数量多的
            if (upper[i] >= lower[i]) {
                useUpper[i] = true;
            } else {
                useUpper[i] = false;
            }
        } else {
            // 只有一种形式，保留现有的
            useUpper[i] = (upper[i] > 0);
        }
    }
    
    // 构建结果字符串
    // 先添加原字符串中需要保留的字符
    for (char c : s) {
        int idx;
        bool isUpper = (c >= 'A' && c <= 'Z');
        
        if (isUpper) {
            idx = c - 'A';
            if (useUpper[idx]) {
                result += c;
            }
        } else {
            idx = c - 'a';
            if (!useUpper[idx]) {
                result += c;
            }
        }
    }
    
    // 添加缺失的字母
    for (int i = 0; i < 26; i++) {
        if (upper[i] == 0 && lower[i] == 0) {
            result += (char)('A' + i);
        }
    }
    
    // 排序以获得字典序最小
    sort(result.begin(), result.end());
    
    return result;
}

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int n;
        string s;
        cin >> n >> s;
        cout << solve(s) << endl;
    }
    
    return 0;
}

Java：

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

public class Solution {
    
    public static String solve(String s) {
        // 统计每个字母的大小写出现次数
        int[] upper = new int[26];
        int[] lower = new int[26];
        
        for (char c : s.toCharArray()) {
            if (c >= 'A' && c <= 'Z') {
                upper[c - 'A']++;
            } else {
                lower[c - 'a']++;
            }
        }
        
        // 决定每个字母使用大写还是小写
        boolean[] useUpper = new boolean[26];
        StringBuilder result = new StringBuilder();
        
        for (int i = 0; i < 26; i++) {
            if (upper[i] == 0 && lower[i] == 0) {
                // 字母未出现，需要添加，优先使用大写
                useUpper[i] = true;
            } else if (upper[i] > 0 && lower[i] > 0) {
                // 同时有大小写，保留数量多的
                if (upper[i] >= lower[i]) {
                    useUpper[i] = true;
                } else {
                    useUpper[i] = false;
                }
            } else {
                // 只有一种形式，保留现有的
                useUpper[i] = (upper[i] > 0);
            }
        }
        
        // 构建结果字符串
        // 先添加原字符串中需要保留的字符
        for (char c : s.toCharArray()) {
            int idx;
            boolean isUpper = (c >= 'A' && c <= 'Z');
            
            if (isUpper) {
                idx = c - 'A';
                if (useUpper[idx]) {
                    result.append(c);
                }
            } else {
                idx = c - 'a';
                if (!useUpper[idx]) {
                    result.append(c);
                }
            }
        }
        
        // 添加缺失的字母
        for (int i = 0; i < 26; i++) {
            if (upper[i] == 0 && lower[i] == 0) {
                result.append((char)('A' + i));