笔试时间：2025年03月15日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：Mex

整数数组的 mex 定义为没有出现在数组中的最小非负整数。例如 mex{1,2,3}=0、mex{0,2,5}=1。现在，对于给定的由n个整数组成的数组{a1,a2，…,an}，取出全部连续非空子数组，并计算每个子数组的 mex之和。连续非空子数组为从原数组中，连续的选择一段元素(可以全选、可以不选)得到的新数组，且新数组中至少有一个元素。

输入描述

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

第二行输入n个整数 a1,a2,…,an(0≤ai<=2)代表数组元素

输出描述

输出一个整数，代表所有了数组的 mex之和。

样例输入

3

1 1 0

样例输出

5

说明：

在这个样例中，答案由以下三部分构成:·长度为1的连续了数组:{1}、{1}、{0}，mex之和为0+0+1=1.·长度为2的连续子数组:{1,1}、{1,0}，mex之和为0+2 = 2。长度为3的连续子数组:{1,1,0}，mex 之和为 2。因此，答案为1十2+2=5。

参考题解

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

#include <iostream>
using namespace std;
int T;
int n,q;
int a[300005];
int pre[300005][3];
int main() {
 int n;
 cin>>n;
 for(int i = 1; i<=n; i++) cin>>a[i];
 long long all = 1LL*n*(n+1)/2,cnt0=0,cnt1=0,cnt2=0,cnt3=0;
 for(int i = 1; i<=n; i++) {
  if(a[i] == 0) pre[i][0] = i;
  else pre[i][0] = pre[i-1][0];
  if(a[i] == 1) pre[i][1] = i;
  else pre[i][1] = pre[i-1][1];
  if(a[i] == 2) pre[i][2] = i;
  else pre[i][2] = pre[i-1][2];
 }
 //有多少的mex是0：即不能包含0
 for(int i = 1; i<=n; i++) {
  if(a[i] == 0) continue;
  long long len = i - pre[i][0];
  cnt0 += len;
 } 
 // 有多少的mex是1：即必须包含0，且不能包含1
 for(int i = 1; i<=n; i++) {
  if(a[i] == 1) continue;
  if(pre[i][1] >= pre[i][0]) continue;
  long long len = pre[i][0]-pre[i][1];
  cnt1 += len;
 } 
 // 有多少的mex是3：数组中必须有0,1,2 
 for(int i = 1; i<=n; i++) {
  long long len;
  if(a[i] == 0) len = i-min(pre[i][1], pre[i][2]);
  if(a[i] == 1) len = i-min(pre[i][1], pre[i][0]);
  if(a[i] == 2) len = i-min(pre[i][2], pre[i][0]);
  if(pre[i][0] && pre[i][1] && pre[i][2]) cnt3 += len;
 }
 cnt2 = all - cnt0 - cnt1-cnt3;
 cout << cnt1+2*cnt2+3*cnt3 << endl;
}

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

import java.util.Scanner;

public class MexCounter {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n + 1];
        int[][] pre = new int[n + 1][3];

        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }

        long all = 1L * n * (n + 1) / 2;
        long cnt0 = 0, cnt1 = 0, cnt2 = 0, cnt3 = 0;

        for (int i = 1; i <= n; i++) {
            pre[i][0] = (a[i] == 0) ? i : pre[i - 1][0];
            pre[i][1] = (a[i] == 1) ? i : pre[i - 1][1];
            pre[i][2] = (a[i] == 2) ? i : pre[i - 1][2];
        }

        // Count MEX = 0
        for (int i = 1; i <= n; i++) {
            if (a[i] == 0) continue;
            long len = i - pre[i][0];
            cnt0 += len;
        }

        // Count MEX = 1
        for (int i = 1; i <= n; i++) {
            if (a[i] == 1) continue;
            if (pre[i][1] >= pre[i][0]) continue;
            long len = pre[i][0] - pre[i][1];
            cnt1 += len;
        }

        // Count MEX = 3
        for (int i = 1; i <= n; i++) {
            long len = 0;
            if (a[i] == 0) len = i - Math.min(pre[i][1], pre[i][2]);
            if (a[i] == 1) len = i - Math.min(pre[i][0], pre[i][2]);
            if (a[i] == 2) len = i - Math.min(pre[i][0], pre[i][1]);
            if (pre[i][0] != 0 && pre[i][1] != 0 && pre[i][2] != 0) {
                cnt3 += len;
            }
        }

        cnt2 = all - cnt0 - cnt1 - cnt3;
        System.out.println(cnt1 + 2 * cnt2 + 3 * cnt3);
    }
}

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

n = int(input())
a = [0] + list(map(int, input().split()))
pre = [[0, 0, 0] for _ in range(n + 1)]

all_subarrays = n * (n + 1) // 2
cnt0 = cnt1 = cnt2 = cnt3 = 0

for i in range(1, n + 1):
    pre[i][0] = i if a[i] == 0 else pre[i - 1][0]
    pre[i][1] = i if a[i] == 1 else pre[i - 1][1]
    pre[i][2] = i if a[i] == 2 else pre[i - 1][2]

# MEX = 0: must not contain 0
for i in range(1, n + 1):
    if a[i] == 0:
        continue
    cnt0 += i - pre[i][0]

# MEX = 1: must contain 0, but not 1
for i in range(1, n + 1):
    if a[i] == 1:
        continue
    if pre[i][1] >= pre[i][0]:
        continue
    cnt1 += pre[i][0] - pre[i][1]

# MEX = 3: must contain 0,1,2
for i in range(1, n + 1):
    if a[i] == 0:
        length = i - min(pre[i][1], pre[i][2])
    elif a[i] == 1:
        length = i - min(pre[i][0], pre[i][2])
    elif a[i] == 2:
        length = i - min(pre[i][0], pre[i][1])
    else:
        continue
    if pre[i][0] and pre[i][1] and pre[i][2]:
        cnt3 += length

cnt2 = all_subarrays - cnt0 - cnt1 - cnt3
print(cnt1 + 2 * cnt2 + 3 * cnt3)

第二题

题目：部落关系

某国的领土可以看作n行m列的矩阵，一共几nxm个单元格，每一个单元格中都有一个部落。我们使用(i,j)表示矩阵中从上往下数第i行和从左往右数第j列的单元格，里面的部族名为小写字母Sij。同一个部族的成员如果彼此相邻，那么他们更进一步的被称作亲密部落。更具体地，若存在这样两个单元格(x,y)和(p,q)，使得Sx,y = Sp,q 且 |x-p|+|y-q|=1，那么我们称他们属于同一个亲密部落。现在小红想让你回答，对于任意(i,j)这个单元格上的部族，其所在亲密部落与多少个非自己部族的部族相邻.在本题中，我们认为两个单元格(x,y)和(p,q)是相邻的,当且仅当|x-p|+|y-q|=1(四相邻)

输入描述

第一行两个整数n,m(1 <n,m < 500)代表国家的领士大小。

此后 n 行，第i行输入一个长度为 m，由小写字母组成的字符串si，代表第i行的部落分布。

输出描述

输出 n 行，每行 m 个整数，第i行第j个整数代表(i,j)所在部落存在多少不同的敌对部落。

样例输入

3 3

baa

aab

cac

样例输出

1 2 2

2 2 2

1 2 2

参考题解

图论，涉及到连通块的知识。这里使用dfs来分别维护即可。

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

#include <iostream>
#include <set>
using namespace std;
char s[505][505];
int n,m;
set<int> ss;
int nx[4] = {1,0,-1,0};
int ny[4] = {0,1,0,-1};
bool vis[555][555], vis2[555][555];
int ans[555][555];
void dfs1(int x, int y) {
    vis[x][y] = 1;
    for(int k = 0; k<4; k++) {
        int tx = x + nx[k];
        int ty = y + ny[k];
        if(tx < 1 || tx > n ||ty < 1 ||ty > m) continue;
        if(s[tx][ty] != s[x][y]) {
            ss.insert(s[tx][ty]);
            continue;
        }
        if(vis[tx][ty] == 1) continue;
        dfs1(tx,ty);
    }
}
void dfs2(int x, int y, int num) {
    vis2[x][y] = 1;
    ans[x][y] = num;