笔试时间：2025年5月8日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：Y串

对于给定的字符串 S1S2…Sn​，将其全部奇数位置的字符删除，得到新的字符串 S′，随后将 S′ 反转，得到新的字符串 S′′，最后，将 S′′中的所有小写字母转换为大写字母。

你需要输出最终得到的字符串 S′′。

输入描述

第一行输入一个长度为 1≤len(S)≤105，由大小写字母混合构成的字符串 S。

输出描述

输出最终得到的字符串 S′′。

样例输入

WhilE

样例输出

LH

第一步，删除奇数位置的字符，得到新的字符串S'="hl";

第二步，反转字符串，得到新的字符串S''="lh";

第三步，将S''中的所有小写字母转换为大写字母，得到最终的字符里S''="LH"

参考题解

签到题，模拟即可。先删除奇数位置，得到新字符串，之后将其反转，最后小写转大写即可。

C++：

#include<bits/stdc++.h>
usingnamespacestd;
int main() {
    string s;
    cin >> s;
    string t;
    for (int i = 1; i < s.length(); i += 2) {
        t += s[i];
    }
    reverse(t.begin(), t.end());
    for (char& c : t) {
        if (islower(c)) {
            c = toupper(c);
        }
    }
    cout << t;
}
 

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        StringBuilder t = new StringBuilder();

        // 提取每隔一个字符
        for (int i = 1; i < s.length(); i += 2) {
            t.append(s.charAt(i));
        }

        // 反转字符串
        t.reverse();

        // 转换小写字母为大写
        for (int i = 0; i < t.length(); i++) {
            if (Character.isLowerCase(t.charAt(i))) {
                t.setCharAt(i, Character.toUpperCase(t.charAt(i)));
            }
        }

        System.out.println(t);
    }
}

Python：

def main():
    s = input()
    t = ''

    # 提取每隔一个字符
    for i in range(1, len(s), 2):
        t += s[i]

    # 反转字符串
    t = t[::-1]

    # 转换小写字母为大写
    t = ''.join([char.upper() if char.islower() else char for char in t])

    print(t)

if __name__ == "__main__":
    main()

第二题：小红的查询线段

小红有一根长度为 n 的绳子，她在绳子上均匀地画了 n 个点（包括端点），点的编号为 1 ~ n，这样绳子被均分为 n 段。

她现在提出 Q 次查询，每次查询要进行下列操作的其中一种：

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

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

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

输入描述

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

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

当 op = 1，在后续一行输入一个整数 a (1 ≤ a ≤ 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，符合询问。

参考题解

set+map，利用set维护所有红线的位置，利用map维护每种长度绳子出现的数量。对于操作一，在x处画一条红线，假如x已在set中，说明之前画过红线则跳过。否则在set中二分小于x且最大的红线位置记作lc，大于x且最小的红线记作rc。那么原来的长度rc-lc会被切断成x-lc和rc-x两段，在map中更新对应数量。对于操作二，直接看map中最大的那个长度是否大于等于k即可。

C++：

#include <bits/stdc++.h>
usingnamespacestd;
int main() {
    int n, q;
    cin >> n >> q;
    set<int> st;
    map<int, int> mp;
    mp[n - 1] = 1;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            x--;
            if (st.find(x) != st.end()) {
                continue;
            }
            int lc = 0;
            auto it_lc = st.upper_bound(x);
            if (it_lc != st.begin()) {
                --it_lc;
                lc = *it_lc;
            }
            int rc = n - 1;
            auto it_rc = st.upper_bound(x);
            if (it_rc != st.end()) {
                rc = *it_rc;
            }
            int sz = rc - lc;
            auto map_it = mp.find(sz);
            if (map_it != mp.end()) {
                if (--map_it->second == 0) {
                    mp.erase(map_it);
                }
            }
            mp[x - lc]++;
            mp[rc - x]++;
            st.insert(x);
        } else {
            int k;
            cin >> k;
            if (mp.empty() || mp.rbegin()->first < k) {
                cout << "NO\n";
            } else {
                cout << "YES\n";
            }
        }
    }
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        
        Set<Integer> st = new TreeSet<>();
        Map<Integer, Integer> mp = new HashMap<>();
        mp.put(n - 1, 1);

        while (q-- > 0) {
            int op = sc.nextInt();

            if (op == 1) {
                int x = sc.nextInt();
                x--;

                // 如果 x 已经存在，则跳过
                if (st.contains(x)) {
                    continue;
                }

                int lc = 0;