笔试时间：2025年9月23日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

Tk有一个仅由字符'0'和'1'构成的字符串s，长度为n。Tk希望通过以下两种操作，每次操作二选一，使得字符串中所有的0都不在1之后：

• 操作1：选择两个相邻的字符s[i]和s[i+1]，当且仅当s[i]='0'且s[i+1]='0'时，将它们同时修改为'1'
• 操作2：选择两个相邻的字符s[i]和s[i+1]，当且仅当s[i]='1'且s[i+1]='0'时，将它们修改为'0'和'1'

请计算使字符串满足"所有的0都不在1之后"这一条件的最少操作次数。

输入描述

输出描述

输出一个整数，表示使字符串满足条件的最少操作次数。

样例输入

5

10001

样例输出

2

第一个操作使用操作1，将字符串"10001"中第3、4位的"00"变为"11"，得到"10111"； 第二个操作使用操作2，将字符串"10111"中第1、2位的"10"变为"01"，得到"01111"，此时所有的1均位于0之后。

参考题解

解题思路：

目标是让所有0在前，所有1在后。核心观察：

1. 操作1：消除一对相邻的0（减少0的总数）
2. 操作2：将0向左移动（调整0的相对位置）

使用动态规划：

• dp[i]表示处理前i个0的最小代价
• 可以单独处理第i个0，或将第i-1和第i个0配对处理
• 状态转移：dp[i] = min(dp[i-1] + 前缀1数量, dp[i-2] + 两0间1数量 + 1)

C++：

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

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    
    vector<int> zero_indices;
    vector<int> prefix_ones(n + 1, 0);
    
    for (int i = 0; i < n; i++) {
        prefix_ones[i + 1] = prefix_ones[i];
        if (s[i] == '0') {
            zero_indices.push_back(i);
        } else {
            prefix_ones[i + 1]++;
        }
    }
    
    int num_zeros = zero_indices.size();
    
    if (num_zeros < 2) {
        cout << 0 << endl;
        return;
    }
    
    vector<int> dp(num_zeros + 1, 0);
    
    int first_zero_index = zero_indices[0];
    dp[1] = prefix_ones[first_zero_index];
    
    for (int i = 2; i <= num_zeros; i++) {
        int current_zero_index = zero_indices[i - 1];
        int prev_zero_index = zero_indices[i - 2];
        
        int cost_singleton = dp[i - 1] + prefix_ones[current_zero_index];
        
        int ones_between = prefix_ones[current_zero_index] - prefix_ones[prev_zero_index];
        int cost_pair = dp[i - 2] + ones_between + 1;
        
        dp[i] = min(cost_singleton, cost_pair);
    }
    
    cout << dp[num_zeros] << endl;
}

int main() {
    solve();
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        solve(sc);
    }
    
    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        String s = sc.next();
        
        List<Integer> zeroIndices = new ArrayList<>();
        int[] prefixOnes = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            prefixOnes[i + 1] = prefixOnes[i];
            if (s.charAt(i) == '0') {
                zeroIndices.add(i);
            } else {
                prefixOnes[i + 1]++;
            }
        }
        
        int numZeros = zeroIndices.size();
        
        if (numZeros < 2) {
            System.out.println(0);
            return;
        }
        
        int[] dp = new int[numZeros + 1];
        
        int firstZeroIndex = zeroIndices.get(0);
        dp[1] = prefixOnes[firstZeroIndex];
        
        for (int i = 2; i <= numZeros; i++) {
            int currentZeroIndex = zeroIndices.get(i - 1);
            int prevZeroIndex = zeroIndices.get(i - 2);
            
            int costSingleton = dp[i - 1] + prefixOnes[currentZeroIndex];
            
            int onesBetween = prefixOnes[currentZeroIndex] - prefixOnes[prevZeroIndex];
            int costPair = dp[i - 2] + onesBetween + 1;
            
            dp[i] = Math.min(costSingleton, costPair);
        }
        
        System.out.println(dp[numZeros]);
    }
}

Python：

import sys

def solve():
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().strip()
    
    zero_indices = []
    prefix_ones = [0] * (n + 1)
    
    for i in range(n):
        prefix_ones[i + 1] = prefix_ones[i]
        if s[i] == '0':
            zero_indices.append(i)
        else:
            prefix_ones[i + 1] += 1
    
    num_zeros = len(zero_indices)
    
    if num_zeros < 2:
        print(0)
        return
    
    dp = [0] * (num_zeros + 1)
    
    first_zero_index = zero_indices[0]
    dp[1] = prefix_ones[first_zero_index]
    
    for i in range(2, num_zeros + 1):
        current_zero_index = zero_indices[i - 1]
        prev_zero_index = zero_indices[i - 2]
        
        cost_singleton = dp[i - 1] + prefix_ones[current_zero_index]
        
        ones_between = prefix_ones[current_zero_index] - prefix_ones[prev_zero_index]
        cost_pair = dp[i - 2] + ones_between + 1
        
        dp[i] = min(cost_singleton, cost_pair)
    
    print(dp[num_zeros])

solve()

第二题

我们所熟知的按位异或可以等价为二进制下的不进位加法；在本题中，我们将其称为2进制异或。

当在任意进制b下(2≤b≤10)，我们定义一种无进位加法，也称b进制异或。其操作过程为：先将两个十进制数转换为b进制表示，然后将它们的对应数位相加并对b取模，作为结果的对应位，不产生向高位的进位。所有位数计算完成后，将得到的b进制结果转换回十进制。

给定长度为n的十进制数组a。

对任意子区间[l,r]，先计算该区间在每个进制(b=2,3,...,10)下的异或和，再取这9个值的最大值与最小值之差，作为该子区间的权值。

现在需要处理m次查询，每次给定子区间[l,r]，请计算并输出该子区间的权值。

输入描述

输出描述

对于每次查询，新起一行，输出一个整数，表示该子区间的权值。

样例输入

14 2

2 5 15 19 4 7 9 12 15 20 20 18 19 12

6 6

3 12

样例输出

0

92

参考题解

解题思路：

使用前缀和技巧处理区间查询。对每个进制b(2到10)：

1. 预计算前缀异或和数组
2. 区间[l,r]的异或和 = prefix[r] - prefix[l-1]（在b进制下的无进位减法）
3. 收集9个进制下的结果，求最大值与最小值的差

C++：

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

long long b_ary_xor(long long n1, long long n2, int b) {
    long long result = 0;
    long long power_of_b = 1;
    while (n1 > 0 || n2 > 0) {
        int digit1 = n1 % b;
        int digit2 = n2 % b;
        int sum_digit = (digit1 + digit2) % b;
        result += sum_digit * power_of_b;
        n1 /= b;
        n2 /= b;
        power_of_b *= b;
    }
    return result;
}

long long b_ary_subtract(long long n1, long long n2, int b) {
    long long result = 0;
    long long power_of_b = 1;
    while (n1 > 0 || n2 > 0) {
        int digit1 = n1 % b;
        int digit2 = n2 % b;
        int diff_digit = (digit1 - digit2 + b) % b;
        result += diff_digit * power_of_b;
        n1 /= b;
        n2 /= b;
        power_of_b *= b;
    }
    return result;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vector<vector<long long>> prefix_xors(11, vector<long long>(n + 1, 0));
    
    for (int b = 2; b