笔试时间：2024年04月03日

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

第一题

题目：小红的数组访问

小红有一个长度为 n 的数组 a ，她每次会询问区间 [l,r] 中所有数字拼接起来是否是 3 的倍数。

输入描述

第一行输入两个整数 n,q(1<=n,q<=10^5) 表示数组长度和询问次数。

第二行输入 n 个整数表示数组 a(1<=ai<=10^9) 。

接下来的q行，每行输入2个整数，表示询问的 [l,r] 区间。1<=l<=r<=n。

输出描述

对于每个询问输出一行，若区间所有数字拼接起来是 3 的倍数，则输出 "YES" ，否则输出 "NO" 。

样例输入

3 2

11 45 14

1 3

2 2

样例输出

NO

YES

说明

将[1,3]拼接后，数字为114514，不是3的倍数，输出"NO"。将[2,2]拼接后，数字为45，是3的倍数，输出"YES"。

参考题解

前缀和。统计前缀和，判断查询的区间的总和是否为3的倍数即可。

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

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }

    vector<int> pres(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        pres[i] = pres[i - 1] + A[i - 1];
    }

    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        if ((pres[r] - pres[l - 1]) % 3 == 0) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

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

import java.util.Scanner;

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

        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] A = new int[n];
        for (int i = 0; i < n; ++i) {
            A[i] = sc.nextInt();
        }

        int[] pres = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            pres[i] = pres[i - 1] + A[i - 1];
        }

        for (int i = 0; i < q; ++i) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            if ((pres[r] - pres[l - 1]) % 3 == 0) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }

        sc.close();
    }
}

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

n,q = map(int, input().split())
A = list(map(int, input().split()))

pres = [0] * (n+1)
for i in range(1, n+1):
    pres[i] = pres[i-1] + A[i-1]

for i in range(q):
    l,r = map(int, input().split())
    if (pres[r] - pres[l-1])%3==0:
        print("YES")
    else:
        print("NO")

第二题

题目：小苯的数组染色

小红给了小苯一个长为 n 的数组 a，初始数组中的每个数字都是白色。小苯可以进行如下两种操作中的一种：

1、任选一个白色的元素，将其染红。

2、选择一个区间[l,r]，满足al != ar且区间两个端点元素均为白色。将区间所有元素染红。

小苯想知道他最少几次操作可以将所有数字都染红，请你帮帮他吧。

输入描述

输入包含 2*T+1 行。

第一个一个正整数 T(1<=T<=10^4)，表示测试数据组数。

接下来对于每组测试数据，输入包含两行。

第一行一个正整数 n(1<=n<=2*10^5)，表示数组 a 的长度。

第二行 n 个正整数 ai(1<=ai<=10^9)，表示数组 ai 的元素。

输出描述

输出包含 T 行。

对于每组测试数据，输出包含一行一个正整数，表示染红所有数字的最小操作次数。

样例输入

2

3

1 2 1

2

1 1

样例输出

2

2

参考题解

动态规划。

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

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

int main() {
    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        vector<int> A(n);
        for (int i = 0; i < n; ++i) {
            cin >> A[i];
        }

        if (A[0] != A[n - 1]) {
            cout << 1 << endl;
            conti