笔试时间：2025年04月26日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：行李

小美准备出游，她有n个行李物品，每个行李物品用小写字母表示。 现在规定每种行李物品携带不能超过个，求小美最多可以带多少个行李物品。

输入描述

第一行两个整数n, k（1 ≤ n≤ 10^5，1≤k≤n）表示行李物品个数和每种物品限带的个数。

第二行一个长度为n的字符串，表示 n个行李物品，输入保证仅由小写字母组成。

输出描述

一个整数，表示最多可以带的行李物品总数。

样例输入

3 1 aab

样例输出

2

参考题解

统计每种行李物品的数量：需要对输入的行李物品字符串进行统计，明确每种行李物品（用小写字母表示）出现的次数。计算可携带的行李物品数量：根据每种物品限带的个数 k，对每种行李物品的数量进行限制，即取该物品实际数量和 k中的较小值。求和得到总数：将所有经过限制后的物品数量相加，得到小美最多可以携带的行李物品总数。

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

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

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

    unordered_map<char, int> counts;
    for (char c : s) {
        counts[c]++;
    }

    int total = 0;
    for (const auto& pair : counts) {
        total += min(pair.second, k);
    }

    cout << total << endl;
    return 0;
}

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

import java.util.HashMap;
import java.util.Map;
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();
        scanner.nextLine(); // 消耗掉换行符
        String s = scanner.nextLine().trim();

        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }

        int total = 0;
        for (int v : counts.values()) {
            total += Math.min(v, k);
        }

        System.out.println(total);
    }
}

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

from collections import Counter

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

counts = Counter(s)
total = sum(min(v, k) for v in counts.values())

print(total)

第二题

题目：退化

小美有一些运算：他定义一个整数2的退化运算Back_x为自己按位与自己的负数，形式化的说，Back_x= （x）and（一x）；一次成功的退化后，x变为x - Back_x；消耗为 max ｛0, Back_x一1｝。退化是可以持续的进行的，例如，当=37时：•第一次退化，x = 37，Backg_37 = （37） and（-37）=1，退化为37- Backg_37 =36，消耗0；• 在刚刚的基础上进行第二次退化，x = 36，Back_36 = （36） and（-36） =4，退化为36- Back_36 = 32，消耗3；• 在刚刚的基础上进行第三次退化，=32，....我们记数字x退化过程中的总消耗Cost_x为：初始的x与每一次退化的消耗 按位或后得到的结果。例如 Cost_37 = 37 or 0 or 3 or ....。现在，你已经完全掌握小美的运算了，你需要计算的是，1～n中，全部数字退化总消耗之和，即SUM{Cost_i},i->[1,n]。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数T （1≤T≤2×10^5）代表数据组数，每组测试数据描述如下：在一行上输入一个整数n（1 ≤ n ≤ 10^9）代表运算的上界。

输出描述

对于每一组测试数据，在同一行上连续输出一个整数，代表1～n中全部数字退化总消耗之和。

样例输入

5

1

2

3

4

11451

样例输出

1 4 7 14 98139631

说明：Cost₁ = 1，Cost₂ = 3，Cost₃ = 3，Cost₄ = 7。

参考题解

退化运算中的关键操作 Back_x = x & (-x) 实际上获取的是数字二进制中最右侧的1（即lowbit）。每次退化后，消耗值为 max(0, Back_x - 1)，而总消耗 Cost_x 是所有中间消耗值和初始值按位或的结果。通过观察发现，Cost_x 的值等于该数字最高有效位对应的全1数（例如，数字5的二进制最高位是4，对应的全1数为7）。1.区间划分：每个区间由 [2^k, 2^{k+1}-1] 构成，区间内的所有数的 Cost_x 均相同，为 2^{k+1}-1。2.贡献计算：对每个区间计算其贡献，即区间长度乘以对应的全1数。3.总和累加：遍历所有可能的区间，累加贡献值。

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

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

ll compute_sum(ll n) {
    ll total = 0;
    ll k = 0;
    while ((1LL << k) <= n) {
        ll s = 1LL << k;
        ll e = min((1LL << (k+1)) - 1, n);
        ll cnt = e - s + 1;
        ll value = (1LL << (k+1)) - 1;
        total += cnt * value;
        k++;
    }
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    vector<ll> results;
    
    for (int i = 0; i < T; i++) {
        ll n;
        cin >> n;
        results.push_back(compute_sum(n));
    }
    
    for (int i = 0; i < T; i++) {
        cout << results[i];
        if (i != T - 1) cout << ' ';
    }
    
    return 0;
}

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static long compute_sum(long n) {
        long total = 0;
        long k = 0;
        while ((1L << k) <= n) {
            long s = 1L << k;
            long e = Math.min((1L << (k+1)) - 1, n);
            long cnt = e - s + 1;
            long value = (1L << (k+1)) - 1;
            total += cnt * value;
            k++;
        }
        return total;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int T = Integer.parseInt(st.nextToken());
        long[] results = new long[T];
        
        for (