笔试时间：2024年09月01日 秋招

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

第一题

题目：三字母辩论会

三个人面对面坐着交谈，每一个单位时间他们都会说出一个字母，当有任何两个人的字母相同时，他们两个都会觉得聊的很投机。机器人已经记录下了每个人在整个交谈期间说过的所有话，你需要统计他们每个人在交谈过程中会有多少个单位时间是觉得自己聊的很投机的。

输入描述

第一行输入一个整数 n（1<=n<=10^6） 代表交谈时长。

第二行输入一个长度为 n ，且只由小写字母构成的字符串 s 。

第三行输入一个长度为 n，且只由小写字母构成的字符串 t 。

第四行输入一个长度为 n ，且只由小写字母构成的字符串 u 。

输出描述

在一行上输出三个整数，代表第一个人、第二个人和第三个人觉得自己聊得很投机的次数。

样例输入

3

abc

abd

bbe

样例输出

2 2 1

说明

在第一个时刻，第一个人和第二个人都说了字母 a，他们会觉得聊得很投机，答案为 1,1,0 ；

在第二个时刻，三个人同时说了同一个字母 b ，他们都会觉得聊得很投机，答案为 2,2,1 ；

在第三个时刻，三个人说的字母不一样，没人会觉得聊的很投机。

参考题解

直接遍历每个字符串，判断当前字符是否与其他两个字符串中的任意一个相等即可。

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

#include <iostream>
#include <string>
using namespace std;
int main() {
    int n;
    string s, t, u;
    
    cin >> n;
    cin >> s >> t >> u;

    int r1 = 0, r2 = 0, r3 = 0;
    for (int i = 0; i < n; i++) {
        char a = s[i], b = t[i], c = u[i];
        if (a == b || a == c) r1++;
        if (b == a || b == c) r2++;
        if (c == a || c == b) r3++;
    }

    cout << r1 << " " << r2 << " " << r3 << 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();
        scanner.nextLine(); // 消耗换行符
        String s = scanner.nextLine();
        String t = scanner.nextLine();
        String u = scanner.nextLine();

        int r1 = 0, r2 = 0, r3 = 0;
        for (int i = 0; i < n; i++) {
            char a = s.charAt(i), b = t.charAt(i), c = u.charAt(i);
            if (a == b || a == c) r1++;
            if (b == a || b == c) r2++;
            if (c == a || c == b) r3++;
        }

        System.out.println(r1 + " " + r2 + " " + r3);

        scanner.close();
    }
}

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

n = int(input())
s = input()
t = input()
u = input()

r1,r2,r3 = 0,0,0
for i in range(n):
    a,b,c = s[i],t[i],u[i]
    if a==b or a==c: r1+=1
    if b==a or b==c: r2+=1
    if c==a or c==b: r3+=1

print(r1,r2,r3)

第二题

题目：小红的查询线段

小红有一根长度为 n-1 的绳子，她在绳子上均匀的画了 n 个点（包括端点），点的编号为 1~n ，这样绳子被均匀的分为 n-1 段。她现在提出 Q 次询问，每次询问会要求进行下述操作的其中一种：

操作一：在点 x(1<x<n)上画一条红线。

操作二：若把当前画红线的地方全部剪断，询问是否存在长度大于等于 k 的绳子；

不考虑绳子的损耗且每次询问二独立（即假设绳子剪断，但实际上并不真的剪断），请你回答小红的每次询问。

输入描述

第一行输入两个整数 n,Q(3<=n<=10^9; 1<=Q<=10^5) 代表绳子的长度、小红的操作询问次数。

接下来 Q 行，每行先输入一个整数 op(1<=op<=2) 表示操作询问的类型，随后：

当 op=1 ，在同一行输入一个整数 x(1<x<n) 表示在 x 处画一条红线:

当 op=2 ，在同一行输入一个整数 k(1<=k<=10^9) 查询若把当前的红线剪断，是否存在长度大于等于 k 的绳子线段。

输出描述

对于每个询问二，若把当前的红线剪断，会存在长度大于等于 k 的绳子，在一行上输出 YES ；否则，直接输出 NO 。

样例输入

8 7

2 7

1 4

2 4

2 5

1 6

2 3

2 4

样例输出

YES

YES

NO

YES

NO

说明

初始时绳子形象的表示为 1-2-3-4-5-6-7-8 ：对于第一次操作，由于此前没有画过红线，所以得到一根长度为 7 的绳子，符合询问；对于第二次操作，在第四个点的位置画一条红线，得到 1-2-3-[4]-5-6-7-8;对于第三次操作，切断后得到一根长度为 3 的绳子和一根长度为 4 的绳子， 1-2-3-4 和 4-5-6-7-8 ，符合询问；对于第四次操作，同上，不符合询问；对于第五次操作，在第六个点的位置画一条红线，得到 1-2-3-[4]-5-[6]-7-8 ；对于第六次操作，切断后得到一根长度为 3 的绳子和两根长度为 2 的绳子，1-2-3-4 、 4-5-6 和 6-7-8，符合询问。

参考题解

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

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

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

    set<int> red_lines;          // 存储红线的位置
    multiset<int> segments;      // 存储每段绳子的长度

    // 初始状态下整个绳子是一段
    red_lines.insert(1);
    red_lines.insert(n);
    segments.insert(n - 1);

    for (int i = 0; i < Q; ++i) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            cin >> x;

            // 找到插入位置前后的红线
            auto it_right = red_lines.lower_bound(x);
            auto it_left = prev(it_right);

            // 删除旧的段长
            int old_length = *it_right - *it_left;
            segments.erase(segments.find(old_length));

            // 插入新红线后，产生两个新的段长
            int left_segment = x - *it_left;
            int right_segment = *it_right - x;

            // 更新段长
            segments.insert(left_segment);
            segments.insert(right_segment);

            // 将新红线位置插入
            red_lines.insert(x);

        } else if (op == 2) {
            int k;
            cin >> k;

            // 获取当前段长的最大值
            auto max_length = *segments.rbegin();

            if (max_length >= k) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        }
    }

    return 0;
}

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

import java.util.*;

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