笔试时间：2024年10月15 秋招

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

第一题

题目

整数1~n，计算选择k个数最多能获得多少积分。计分规则:初始积分为 0，对于被选取的整数，如果i+1没选，则积分加1。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数T(1 ≤T ≤ 10^5)代表数据组数，每组测试数据描述如下:

在一行上输入两个整数 n,k(1 ≤ n,k ≤ 10^12;k≤ n)，含义和题面描述一致。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表最多能获得的积分。

样例输入

2

1 1

4 2

样例输出

1

2

参考题解

为了最大化积分，我们需要尽可能多地选择那些满足 i+1 没有被选取的整数。换句话说，我们希望尽可能多地选择那些不与下一个数连续的数。

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

#include <iostream>
#include <algorithm>
#include <sstream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int T;
    cin >> T; // 读取测试用例数量
    
    while (T--) {
        long long n, k;
        cin >> n >> k; // 读取n和k
        
        // 计算最大积分
        long long max_points = min(k, n - k + 1);
        
        // 输出结果
        cout << max_points << "\n";
    }
    
    return 0;
}

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

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用BufferedReader读取输入，提高I/O效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 使用BufferedWriter输出结果，提高I/O效率
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        // 读取测试用例数量T
        int T = Integer.parseInt(br.readLine());
        
        while (T-- > 0) {
            // 读取每组测试数据的n和k
            st = new StringTokenizer(br.readLine());
            long n = Long.parseLong(st.nextToken());
            long k = Long.parseLong(st.nextToken());
            
            // 计算最大积分
            long max_points = Math.min(k, n - k + 1);
            
            // 将结果写入输出缓冲区
            bw.write(String.valueOf(max_points));
            bw.newLine();
        }
        
        // 刷新并关闭输出缓冲区
        bw.flush();
        bw.close();
        br.close();
    }
}

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

import sys

# 使用sys.stdin和sys.stdout提高I/O效率
input = sys.stdin.read
output = sys.stdout.write

def main():
    data = input().splitlines()
    T = int(data[0])  # 读取测试用例数量
    result = []
    
    for i in range(1, T + 1):
        n, k = map(int, data[i].split())  # 读取n和k
        # 计算最大积分
        max_points = min(k, n - k + 1)
        result.append(str(max_points))
    
    # 输出结果
    output("\n".join(result) + "\n")

if __name__ == "__main__":
    main()

第二题

题目

长度为 n 只包含小写字母的字符串 S，下标1开始。进行n次操作，第i次操作将 Si移动到字符串末尾。输出,n次操作后的字符串。例如字符串"abqde"，第一步"bqdea"，第二步"bdeaq"，第三步，第四步"bdaeq""bdage"，第五步"bdaeq"。

输入描述

在一行上输入一个由小写字母构成的字符串，长度记为n(1 ≤ n < 10^6)。

输出描述

在一行上输出一个字符串，表示操作后的字符串。

样例输入

abqde

样例输出

bdeaq

参考题解

初始化二叉搜索树：我们将字符串中的每个字符的位置映射到 二叉搜索树中，并初始化二叉搜索树以表示每个位置上都有一个字符。

模拟操作：对于每次操作 i，使用 BIT 查找当前字符串的第 i 个字符的位置。将该字符记录为被移动到末尾的字符。更新 BIT，将该位置标记为空，并在末尾追加该字符。构造最终字符串：将未被移动的字符按照原始顺序放在最终字符串的前部。将被移动的字符按照它们被移动的顺序放在最终字符串的后部。

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

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>

using namespace std;

class BIT {
public:
    int size;
    vector<int> tree;

    BIT(int size) : size(size) {
        tree.assign(size + 2, 0);
    }

    // 更新BIT树，index位置加delta
    void update(int index, int delta) {
        while (index <= size) {
            tree[index] += delta;
            index += index & (-index);
        }
    }

    // 查询前缀和[1, index]
    int query(int index) {
        int res = 0;
        while (index > 0) {
            res += tree[index];
            index -= index & (-index);
        }
        return res;
    }

    // 查找第k个存在的字符的位置
    int findKth(int k) {
        int idx = 0;
        int bitMask = 1 << (31 - __builtin_clz(size));
        while (bitMask != 0) {
            if (idx + bitMask <= size && tree[idx + bitMask] < k) {
                idx += bitMask;
                k -= tree[idx];
            }
            bitMask >>= 1;
        }
        return idx + 1;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string S;
    cin >> S;
    int n = S.length();

    vector<int> lastMoveTime(n, 0);
    vector<int> chars(2 * n + 2, 0);
    for (int pos = 1; pos <= n; pos++) {
        chars[pos] = pos - 1;
    }

    BIT bit(2 * n + 1);
    for (int pos = 1; pos <= n; pos++) {
        bit.update(pos, 1);
    }

    int end = n;

    for (int i = 1; i <= n; i++) {
        if (i > bit.query(bit.size)) {
            continue;
        }

        int pos = bit.findKth(i);
        int c = chars[pos];
        lastMoveTime[c] = i;

        bit.update(pos, -1);
        end++;
        chars[end] = c;
        bit.update(end, 1);
    }

    vector<char> finalMovedChars(n + 1, 0);
    for (int c = 0; c < n; c++) {
        if (lastMoveTime[c] > 0) {
            finalMovedChars[lastMoveTime[c]] = S[c];
        }
    }

    stringstream sb;

    for (int c = 0; c < n; c++) {
        if (lastMoveTime[c] == 0) {
            sb << S[c];
        }
    }

    for (int i = 1; i <= n; i++) {
        if (finalMovedChars[i] != 0) {
            sb << finalMovedChars[i];
        }
    }

    cout << sb.str() << "\n";
    return 0;
}

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

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

public class Main {
    // 二叉索引树（Fenwick Tree）实现
    static class BIT {
        int size;
        int[] tree;

        BIT(int size) {
            this.size = size;
            tree = new int[size + 2];
        }

        // 更新BIT树，index位置加delta
        void update(int index, int delt