笔试时间：2025年5月10日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：行走

小美正在一个无限大的二维坐标轴上运动，初始时她位于坐标(x,y)。她将基于一个由 n个整数组成的数组{a1,a2,...,an}进行移动，对于第i次移动，她都需要选择这样两个整数l和r，满足｜l｜+｜r｜= ai，随后移动到(x+l,y+r)这个位置。现在请问，n次移动后，她能否恰好移动到(p,q)这个位置。

输入描述

第-行一个整数t(1<=t<=1000)表示数据组数。对于每组数据格式为:

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

第二行n个整数，第i个整数为ai(0 ≤ ai<=1)，表示每次移动的距离。

第三行四个整数x,y,p,q(-10^18≤ x,y,p,q ≤ 10^18)，分别表示起点的横纵坐标，终点的横纵坐标。

数据保证单个测试文件∑n ≤10^5

输出描述

对于每组数据输出一个字符串，若可以恰好移动到(p,q)输出 "YES"，否则输出"NO"。

样例输入

2

2

0 0 

1 1 1 1

3

1 1 1

1 1 2 2

样例输出

YES

NO

参考题解

模拟，由于a[i]=1代表会在一个方向上走一步，因此只需要总步数和(x,y)(p,q)两个坐标差，相差的奇偶性相同即可，且需要保证总步数大于坐标差。

C++：

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

int main() {
    int t;
    cin >> t;
    
    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int j = 0; j < n; j++) {
            cin >> a[j];
        }
        int x, y, p, q;
        cin >> x >> y >> p >> q;
        
        int dx = p - x;
        int dy = q - y;
        int s = accumulate(a.begin(), a.end(), 0);
        int sumAbs = abs(dx) + abs(dy);
        
        if (sumAbs > s) {
            cout << "NO" << endl;
        } else if (sumAbs % 2 != s % 2) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
        }
    }
    return 0;
}

Java：

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        
        for (int i = 0; i < t; i++) {
            int n = scanner.nextInt();
            int[] a = new int[n];
            for (int j = 0; j < n; j++) {
                a[j] = scanner.nextInt();
            }
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int p = scanner.nextInt();
            int q = scanner.nextInt();
            
            int dx = p - x;
            int dy = q - y;
            int s = 0;
            for (int num : a) {
                s += num;
            }
            int sumAbs = Math.abs(dx) + Math.abs(dy);
            
            if (sumAbs > s) {
                System.out.println("NO");
            } else if (sumAbs % 2 != s % 2) {
                System.out.println("NO");
            } else {
                System.out.println("YES");
            }
        }
        scanner.close();
    }
}

Python：

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    x, y, p, q = map(int, input().split())
    dx = p - x
    dy = q - y
    s = sum(a)  # 由于数组元素非0即1，s也是1的数量
    sum_abs = abs(dx) + abs(dy)
    
    if sum_abs > s:
        print("NO")
    elif sum_abs % 2 != s % 2:
        print("NO")
    else:
        print("YES")

第二题：小美的数对合并

由于小美对图论十分感兴趣，因此小美希望创建一个属于自己的无向图。他有一个长度为n的数组a，他认为一对数字i,j是好的当且仅当:i,j(1<=i<j<=n)同时i-j<ai-aj。小美创建图的方式则是:对于任意一个点对 u,v(1≤u,v≤n)，如果u,v是一对好的数字，则他会在u,v之间连上一条无向边。现在小美想知道，他所创建出的图有多少个极大连通块，由于图中的边数过多他数不过来，因此他想请你帮他算一算。对于图上的两个点，如果它们之间有边相连，则称他们位于同一个连通块里。对于一个连通块，如果其已经无法再加入更多的点，则称其为极大连通块。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤100)代表数据组数，每组测试数据描述如下:

第一行输入一个整数n(1≤n≤2x10^5)，表示数组a的长度。

第二行输入n个正整数 a1,a2,...,an(1≦ai≤10^9)，表示数组。

除此之外，保证单个测试文件的 n 之和不超过2x10^5

输出描述

对于每组测试数据:

输出一行一个正整数表示他的图中连通块的个数。

样例输入

2

4

3 3 4 6

5

1 2 3 4 5

样例输出

2

5

参考题解

题意的约束可以转化为i<j，且i-a[i]<j-a[j]，因此构建新数组ci=i-a[i]。假设把极大连通块的最大值定义为我们待统计的一个连通块的根，因此需要维护后缀最大值，对于答案统计，如果当前节点是后缀最大值且无法和前面的连通块合并，则ans++。对于和前面连通块合并，只需要考察当前a[i]是否比前面出现过的最小值要大即可。

C++：

#include<iostream>

using namespace std;
int t,n,a[200005], rmax[200005];
int main()
{
 cin>>t;
while(t--) {
  scanf("%d", &n);
for(int i = 1; i<=n; i++) {
   cin>>a[i];
   a[i] = i-a[i];
  }
  rmax[n+1] = -1e9;
for(int i = n; i>=1; i--) {
   rmax[i] = max(rmax[i+1], a[i]);
  }
  int ans = 0;
  int all_minn = 1e9+1, pre_minn = 1e9+1;
for(int i = 1; i<=n; i++) {
   if(a[i] == rmax[i]) {
    if(a[i] <= pre_minn) {
     ans++;
    }
    pre_minn = min(pre_minn, all_minn);
   }
   all_minn = min(all_minn, a[i]);
  }
  cout << ans << endl;
 }
return 0;
} 

Java：

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    t = int(input[ptr])
    ptr += 1
    
    for _ in range(t):
        n = int(input[ptr])
        ptr += 1
        a = [0] * (n + 2)  # 索引从1开始
        rmax = [0] * (n + 2)
        
        for i in range(1, n+1):
            a[i] = int(input[ptr])
            ptr += 1
            a[i] = i - a[i]
        
        rmax[n+1] = -1e9
        for i in range(n, 0, -1):
            rmax[i] = max(rmax[i+1], a[i])
        
        ans = 0
        all_minn = 1e9 + 1
        pre_minn = 1e9 + 1