笔试时间：2024年04月12日

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

第一题

题目：小红的质数合数

小红有一个数组，她想知道这个数组不同的质数和不同的合数共有多少个。合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数(O除外)整除的数。

输入描述

第一行输入一个整数n(1<= n<=2 x 10^5)表示数组长度。

第二行输入n个整数表示数组ai。

输出描述

输出一个整数。

样例输入

3

20 2 4

样例输出

3

参考题解

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

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

int main() {
    int n; cin >> n;
    unordered_set<int> st;
    for (int i = 0; i < n; ++i) {
        int a; cin >> a;
        if (a > 1) {
            st.emplace(a);
        }
    }
    cout << st.size();
}

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

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < n; ++i) {
            int a = scanner.nextInt();
            if (a > 1) {
                set.add(a);
            }
        }
        System.out.println(set.size());
    }
}

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

n = int(input())
st = set()
for _ in range(n):
    a = int(input())
    if a > 1:
        st.add(a)
print(len(st))

第二题

题目：小苯的数组查询

小苯有一个长度为n的数组α。它定义了一个函数：

f(l,r) = al|al + 1|ar。

(|表示位运算中的按位或运算)

现在他有q次询问,每次询问他都会给出一个区间[l,r]，以及一个正整数k，他想知道在区间中是否存在一个右端点r'，使得f(l, r')请你帮帮他处理每次询问吧。

输入描述

输入包含若干行。 第一行两个正整数n,q(),分别表示数组α的长度和小苯的询问次数。

第二行n个正整数,表示数组α的每个元素。

接下来q行,每行三个正整数l,r,k

输出描述

输出包含q行,每行一个整数，如果存在符合条件的,请输出最小的一个,如果不存在输出一个-1。

样例输入

5 5

3 2 3 3 6

1 2 3

1 5 7

1 4 7

2 2 2

2 3 7

样例输出

1

5

-1

2

-1

说明

第一个询问,区间[1.2]中,选择r=1，区间[1,1]的f值为3，因此输出1。

参考题解

比较典型的题目，遇到按位或运算，可以考虑前缀和，因为bit的数目是递增的，可以先统计每个数位上1的数目的前缀和；然后对于每一次询问，采用二分查找来找到最左边符合条件的索引。在二分查找中，利用前缀和数组构建当前区间所有元素按位或的和，判断其与k的大小关系，从而收缩左右边界。

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

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    int n, q; cin >> n >> q;
    vector<int> a(n);
    vector<vector<int>> S(n + 2, vector<int>(32, 0));
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        S[i + 1] = S[i];
        for (int j = 0; j < 32; ++j) S[i + 1][j] += (a[i] >> j & 1);
    }
    for (int i = 0; i < q; ++i) {
        ll left, right, k; cin >> left >> right >> k;
        left--, right--;
        ll cur = 0, l = left, r = right;
        while (l <= r) {
            ll mid = (l + r) / 2;
            cur = 0;
            for (int j = 0; j < 32; ++j) {
                int c = S[mid + 1][j] - S[left][j];
                if (c) cur |= (1 << j);
            }
            if (cur >= k) r = mid - 1;
            else l = mid + 1;
        }
        cur = 0;
        for (int j = 0; j < 32; ++j) {
            int c = S[l + 1][j] - S[left][j];
            if (c) cur |= (1 << j);
        }
        if (cur == k && l + 1 <= right + 1) cout << l + 1 << "\n";
        else cout << "-1\n";
    }
}

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        int[] a = new int[n];
        int[][] S = new int[n + 2][32];

        for (int i = 0; i < n; ++i) {
            a[i] = scanner.nextInt();
            System.arraycopy(S[i], 0, S[i + 1], 0, 32);
            for (int j = 0; j < 32; ++j)
                S[i + 1