笔试时间：2023年9月17日 秋招

第一题

题目：小红的字符串

小红有一个字符串，仅包含a和b，她可以进行以下两种操作：

1、找到下标i，满足ai=b,ai+1 =a，并交换这两个字符；

2、找到下标i，满足ai=a, ai+1 =b，并删除这两个字符；

小红可以无限次进行操作2，但只能进行k次操作1。请问小红最后可以得到的长度最小的字符串是什么，并输出这个字符串，若可以全部删除，输出-1。

输入描述

第一行两个整数n,k，表示字符串长度和操作1的次数；

第二行一个字符串a，表示小红的字符串。

1 <= n <= 10^5

0 <= k<= 10^5

输出描述

输出一个字符串，表示小红最后可以得到的长度最小的字符串。

若可以全部删除，输出一1。

样例输入

7 1

ababbaa

样例输出

a

参考题解

利用栈来模拟删除操作2，最后我得到的子串一定为:bbbaaa形式，有k次操作1的机会，我们交换边界ba，得到ab，删除。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <string>

int main() {
    int n, k;
    std::string s;
    std::cin >> n >> k >> s;

    std::string t;
    for (char ch : s) {
        if (ch == 'a') {
            t += ch;
        } else {
            if (!t.empty() && t.back() == 'a') {
                t.pop_back();
            } else {
                t.push_back(ch);
            }
        }
    }

    int countA = 0, countB = 0;
    for (char ch : t) {
        if (ch == 'a') {
            ++countA;
        } else {
            ++countB;
        }
    }

    k = std::min(std::min(k, countA), countB);
    countA -= k;
    countB -= k;

    std::string u = std::string(countB, 'b') + std::string(countA, 'a');
    if (u.empty()) {
        u = "-1";
    }

    std::cout << u << std::endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        String s = scanner.next();

        StringBuilder t = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (ch == 'a') {
                t.append(ch);
            } else {
                if (t.length() > 0 && t.charAt(t.length() - 1) == 'a') {
                    t.deleteCharAt(t.length() - 1);
                } else {
                    t.append(ch);
                }
            }
        }

        int countA = 0, countB = 0;
        for (char ch : t.toString().toCharArray()) {
            if (ch == 'a') {
                countA++;
            } else {
                countB++;
            }
        }

        k = Math.min(Math.min(k, countA), countB);
        countA -= k;
        countB -= k;

        StringBuilder u = new StringBuilder();
        u.append("b".repeat(countB));
        u.append("a".repeat(countA));

        if (u.length() == 0) {
            u.append("-1");
        }

        System.out.println(u);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n, k = map(int, input().split())
s = input()

t = ""
for ch in s:
    if ch == 'a':
        t += ch
    else:
        if len(t) > 0 and t[-1] == 'a':
            t = t[:-1]
        else:
            t += ch

count_a = t.count('a')
count_b = len(t) - count_a

k = min(min(k, count_a), count_b)
count_a -= k
count_b -= k

u = 'b' * count_b + 'a' * count_a
if not u:
    u = "-1"

print(u)

第二题

题目：小红的好数

如果一个不含前导零的正整数中，所有数位中最多有两种数字，那么这是一个好数。例如，23,2323,9,111,101都是好数，小红想知道，在1到n中，有多少个好数。

输入描述

一行一个正整数n。

1 <= n <= 10^9

输出描述

一行一个正整数表示答案

样例输入

110

样例输出

102

提示

所有的一位数，两位数，以及三位数的100，101，100满足答案，一共有99+3=102个好数。

参考题解

位运算

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <unordered_set>

int main() {
    int n;
    int digits[2];
    std::cin >> n;
    std::unordered_set<int> uniqueNumbers;
    uniqueNumbers.insert(1000000000);

    for (int length = 1; length <= 9; length++) {
        for (digits[0] = 0; digits[0] < 10; digits[0]++) {
            for (digits[1] = 0; digits[1] <= digits[0]; digits[1]++) {
                for (int state = 0; state < (1 << length); state++) {
                    int number = 0;
                    for (int i = 0; i < length; i++) {
                        number = number * 10 + digits[(state >> i) & 1];
                    }
                    uniqu