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

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

第一题

题目：数字放大镜

给出一个长度为n的整数数组A1,A2,A3,...,An,其中0≤A[i]≤9.牛牛有一个神奇的数字放大镜，可以设置放大倍数为k,然后用这个放大镜观察区间[l,r]的数，对于第i(l≤i≤r)个数Ai在放大镜下观察到的值为A[i]×kmod10,既只观察到放大后的个位。现在，一共有q次询问，第i次询问用一个三元组(li,ri,ki)表示，表示用放大倍数为ki的放大镜在区间[li,ri]观察，对于每个询问，输出10个整数，分别表示观察到的A[i]的值为0~9的个数。

输入描述

第一行输入一个整数n(1≤n≤10^5)代表数组中的元素数量。

第二行输入n个整数A1,A2,A3,...,An(0≤A[i]≤9)代表数组元素。

第三行输入一个整数q(1≤q≤10^5)表示询问的数量。

此后9行，每行输入三个数字li,ri,ki(1≤li≤ri≤n；1≤ki≤10^5)代表一次询问三元组。

输出描述

对于每一次间问，在一行上输出十个整数，分别表示观察到的A[i]的值为0~9的个数。

样例输入

5

 1 2 3 4 5

 2

 1 3 6

 2 5 8

样例输出

0 0 1 0 0 0 1 0 1 0

1 0 1 0 1 0 1 0 0 0

解释：对于第一次询问，观察的数初始为1,2,3，在放大6倍后，变为6,2,8.对于第二次间问，观察的数初始为2,3,4,5，在放大8倍后，变为6,4,2,0。

参考题解

前缀和预处理：对于每个可能的数字 d（从 0 到 9），我们计算其在数组位置 1 到 i 之间的出现次数，存储在二维数组 sum_d[d][i] 中。这样，对于任意区间 [l, r]，数字 d 出现的次数可以通过 sum_d[d][r] - sum_d[d][l - 1] 快速得到。处理查询：对于每个查询 (l, r, k)，我们需要计算放大镜观察到的每个数字的次数。对于原始数字 d，放大后的值为 (d * k) % 10。我们遍历所有可能的原始数字 d，累加对应的放大后值的次数。输出结果：对于每个查询，输出数组 observed[0..9]，表示放大镜观察到的数字 0 到 9 的次数。

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

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

// 使用快速读入优化
inline void read(int &x) {
    x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
}

int main() {
    int n;
    read(n);
    vector<int> A(n + 1);
    for(int i = 1; i <= n; ++i) {
        char ch = getchar();
        while(ch < '0' || ch > '9') ch = getchar();
        A[i] = ch - '0';
    }

    vector<vector<int>> sum_d(10, vector<int>(n + 1, 0));
    for(int d = 0; d <= 9; ++d) {
        for(int i = 1; i <= n; ++i) {
            sum_d[d][i] = sum_d[d][i - 1] + (A[i] == d ? 1 : 0);
        }
    }

    int q;
    read(q);
    while(q--) {
        int l, r, k;
        read(l); read(r); read(k);

        int observed[10] = {0};

        for(int d = 0; d <= 9; ++d) {
            int cnt_d = sum_d[d][r] - sum_d[d][l - 1];
            int observed_value = (d * k) % 10;
            observed[observed_value] += cnt_d;
        }

        for(int i = 0; i <= 9; ++i) {
            printf("%d", observed[i]);
            if(i != 9) printf(" ");
            else printf("\n");
        }
    }

    return 0;
}

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

import java.util.Scanner;

public class Main {

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

        // 读取n
        int n = scanner.nextInt();
        scanner.nextLine();  // 消耗换行符

        int[] A = new int[n + 1];
        String input = scanner.nextLine().trim();
        for (int i = 1; i <= n; ++i) {
            A[i] = input.charAt(i - 1) - '0';
        }

        int[][] sum_d = new int[10][n + 1];
        for (int d = 0; d <= 9; ++d) {
            for (int i = 1; i <= n; ++i) {
                sum_d[d][i] = sum_d[d][i - 1] + (A[i] == d ? 1 : 0);
            }
        }

        // 读取q
        int q = scanner.nextInt();
        while (q-- > 0) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            int k = scanner.nextInt();

            int[] observed = new int[10];

            for (int d = 0; d <= 9; ++d) {
                int cnt_d = sum_d[d][r] - sum_d[d][l - 1];
                int observed_value = (d * k) % 10;
                observed[observed_value] += cnt_d;
            }

            for (int i = 0; i <= 9; ++i) {
                System.out.print(observed[i]);
                if (i != 9) System.out.print(" ");
                else System.out.println();
            }
        }

        scanner.close();
    }
}

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

def read_integers():
    return list(map(int, input().split()))

def main():
    n = int(input())
    A = [0] + [int(x) for x in input().strip()]
    
    # 预计算每个数字在位置1到n中的累计出现次数
    sum_d = [[0] * (n + 1) for _ in range(10)]
    for d in range(10):
        for i in range(1, n + 1):
            sum_d[d][i] = sum_d[d][i - 1] + (1 if A[i] == d else 0)

    # 读取查询数量
    q = int(input())
    for _ in range(q):
        l, r, k = read_integers()
        
        observed = [0] * 10
        
        # 计算每个数的出现次数并将其映射到 (d * k) % 10
        for d in range(10):
            cnt_d = sum_d[d][r] - sum_d[d][l - 1]
            observed_value = (d * k) % 10
            observed[observed_value] += cnt_d

        print(" ".join(map(str, observed)))

if __name__ == "__main__":
    main()

第二题

题目：2chess

给定一个n×m的网格棋盘，每个格子可以选择放入黑子或者白子（不能不放）。两个格子联通当且仅当：1.两个格子上下左右相邻或两个格子与同一个格子联通2.两个格子上棋子同色。我们选择一些格子，称之为一个连通块当且仅当任意两个选中的点联通。当不存在更大的连通块包含该连通块时，我们称该连通块为极大连通块。我们称一个极大连通块是优秀的当且仅当该连通块大小（即含有的格子大小）是奇数，我们想知道对于该棋盘，有多少种布局使得每个极大连通块都是优秀的。

输入描述

输入两个整数n,m(1≤n×m≤16)代表棋盘的大小。

输出描述

输出一个整数，表示布局数量。

样例输入

1 1

样例输出

2

解释：放黑子白字都可以。

参考题解

枚举所有可能的棋盘状态：由于棋盘最多是 16x16，而每个格子有 2 种状态（放置黑子或白子），所以可以通过位运算来枚举所有可能的棋盘状态。连通块的判断：对于每种棋盘状态，使用深度优先搜索（DFS）或广度优先搜索（BFS）来找到棋盘上的所有连通块。一个连通块的定义是：上下左右相连并且颜色相同的格子组成一个连通块。判定连通块的大小：统计每个连通块的大小，如果所有连通块的大小均为奇数，那么这是一种有效的棋盘布置。结果统计：最终统计满足条件的棋盘布置数量。

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

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

const int MAXN = 16;
int n, m;
vector<vector<int>> board;
vector<vector<bool>> visited;
int dx[4] = {1, -1, 0, 0};  // 方向数组，表示上下左右移动
int dy[4] = {0, 0, 1, -1};

void dfs(int x, int y, int &size) {
    visited[x][y] = true;
    size++;
    
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && board[nx][ny] == board[x][y]) {
            dfs(nx,