笔试时间：2024年09月22日 秋招 测开

历史笔试传送门：2023秋招笔试合集

第一题

题目：小苯的01串

小苯有一个长为n的只由0和1组成的串s，他需要恰好对s执行k次转置操作。小苯想要使得s的字典序最小, 请你帮帮他求出最小字典序的s吧。将任意一个位置的0变成1或1变成0称为一次转置，使用数学的方式描述，即选择任意。

字典序的比较方法为, 从字符串的第一个字符开始,逐字符比较直到找到第一个不同的字符, 通过比较这个字符决定, 例如 " 0110 " 的字典序大于 " 0010", 因为第二个位置上的字符不同。

输入描述

第一行输入两个整数n和k代表s的长度和操作次数。

第二行输入一个长为n，且只由'0'和'11'组成的字符串s。

输出描述

在一行上输出一个长度为n, 且只由'0'和'1'组成的字符串, 代表进行了怡好k次操作后字典序最小的s。

样例输入

6 4

011110

样例输出

000000

说明：选择操作：s2, s3, s4, s5 即可得到，显然不存在字典序更小的方案。

参考题解

模拟。

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

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    vector<int> f(n, 0); // 用于存储翻转标志
    int sum_f = 0;       // 记录当前翻转操作的次数

    // 初始化翻转标志
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == '1')
        {
            f[i] = 1;
            sum_f += 1;
        }
    }

    // 如果翻转次数超过k，进行调整
    if (sum_f > k)
    {
        for (int i = n - 1; i >= 0; --i)
        {
            if (f[i] == 1)
            {
                f[i] = 0;
                sum_f -= 1;
                if (sum_f == k)
                {
                    break;
                }
            }
        }
    }

    // 如果需要，调整奇偶性
    if ((k - sum_f) % 2 == 1)
    {
        f[n - 1] = 1 - f[n - 1];
        sum_f += (f[n - 1] == 1) ? 1 : -1;
    }

    // 剩余的翻转次数
    int rem = k - sum_f;
    if (rem < 0 || rem % 2 != 0)
    {
        // 剩余的翻转可以通过偶数次翻转来调整
        // 不需要执行额外操作
    }

    // 应用翻转并输出结果
    string result;
    for (int i = 0; i < n; ++i)
    {
        int s_i = s[i] - '0';       // 将字符转换为整数
        int s_i_prime = s_i ^ f[i]; // 通过异或操作进行翻转
        result += to_string(s_i_prime);
    }

    cout << result << 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();

        int[] f = new int[n];  // 用于存储翻转标志
        int sum_f = 0;         // 记录当前翻转操作的次数

        // 初始化翻转标志
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                f[i] = 1;
                sum_f += 1;
            }
        }

        // 如果翻转次数超过k，进行调整
        if (sum_f > k) {
            for (int i = n - 1; i >= 0; i--) {
                if (f[i] == 1) {
                    f[i] = 0;
                    sum_f -