笔试时间：2025年9月20日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：字符串操作

题目描述：给定长度为 n 的字符串 s1 和长度为 m 的字符串 s2。对于长度为 L 的字符串，它的子串 s[l,r]（1≤l≤r≤L）是指从第 l 个字符开始到第 r 个字符结束这一段所构成的字符串。

请判断是否能够通过进行至多 1 次以下操作使得字符串 s1 和字符串 s2 完全相同：在字符串 s1 中选择一个子串 s1[l,r]（1≤l≤r≤n），将该子串从 s1 中删除，同时将该子串添加到 s2 末尾。

输入描述

输入包含多组测试数据。输入第一行包含一个整数 T（1≤T≤100），表示数据组数。之后每三行描述一组测试数据：

• 第一行包含两个正整数 n 和 m（1≤m≤n≤100）分别表示字符串 s1 和 s2 的长度。
• 第二行包含一个长度为 n 的字符串，表示字符串 s1，保证仅包含小写英文字母。
• 第三行包含一个长度为 m 的字符串，表示字符串 s2，保证仅包含小写英文字母。

输出描述

对于每组测试数据输出一行，如果能够通过至多 1 次操作使得字符串 s1 和 s2 完全相同，则输出 YES，否则输出 NO。

样例输入

2

4 2

acdc

ad

4 2

accd

ad

样例输出

YES

NO

样例说明： 对于样例的第一组测试数据，可以从 s1 中选择子串 "cd"，操作后有 s1="ad", s2="adcd"。 对于样例的第二组测试数据，通过该操作无法使得 s1 和 s2 完全相同。

参考题解

解题思路：

1. 操作后 s1 和 s2 必须相同：设操作中删除的子串长度为 k，那么操作后新的 s1 长度为 n-k，新的 s2 长度为 m+k。要求两者相等：n-k = m+k，解得 k = (n-m)/2。因此，n-m 必须是偶数。
2. 如果 k=0（即 n=m），则不需要操作，直接判断 s1 和 s2 是否相等。
3. 否则，枚举所有可能的子串起始位置，检查移除该子串后的 s1 是否等于 s2 拼接上该子串。

C++：

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

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        string s1, s2;
        cin >> s1 >> s2;
        
        if ((n - m) % 2 != 0) {
            cout << "NO" << endl;
            continue;
        }
        
        int k = (n - m) / 2;
        
        if (k == 0) {
            cout << (s1 == s2 ? "YES" : "NO") << endl;
            continue;
        }
        
        bool found = false;
        for (int start = 0; start <= n - k; start++) {
            string segment = s1.substr(start, k);
            string remaining = s1.substr(0, start) + s1.substr(start + k);
            if (remaining == s2 + segment) {
                found = true;
                break;
            }
        }
        
        cout << (found ? "YES" : "NO") << endl;
    }
    return 0;
}

Java：

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        
        while (T-- > 0) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            String s1 = scanner.next();
            String s2 = scanner.next();
            
            if ((n - m) % 2 != 0) {
                System.out.println("NO");
                continue;
            }
            
            int k = (n - m) / 2;
            
            if (k == 0) {
                System.out.println(s1.equals(s2) ? "YES" : "NO");
                continue;
            }
            
            boolean found = false;
            for (int start = 0; start <= n - k; start++) {
                String segment = s1.substring(start, start + k);
                String remaining = s1.substring(0, start) + s1.substring(start + k);
                if (remaining.equals(s2 + segment)) {
                    found = true;
                    break;
                }
            }
            
            System.out.println(found ? "YES" : "NO");
        }
        scanner.close();
    }
}

Python：

import sys

def main():
    I = sys.stdin.readline
    T = int(I())
    for _ in range(T):
        n, m = map(int, I().split())
        s1 = I().strip()
        s2 = I().strip()
        
        if (n - m) % 2 != 0:
            print("NO")
            continue
        
        k_val = (n - m) // 2
        
        if k_val == 0:
            print("YES" if s1 == s2 else "NO")
            continue
        
        found = False
        for start in range(n - k_val + 1):
            segment = s1[start:start + k_val]
            remaining = s1[:start] + s1[start + k_val:]
            if remaining == s2 + segment:
                found = True
                break
        
        print("YES" if found else "NO")

if __name__ == "__main__":
    main()

第二题：激光射击

题目描述：小明在玩一款叫做激光射击的游戏。

游戏在一个平面直角坐标系上进行。游戏的场地为一个 n×m 的矩形区域，其中矩形的四个顶点分别为 (0,0)、(n,0)、(n,m)、(0,m)。一束激光装置放置在 (0,0) 的位置，玩家可以向区域内任意方向发射一束激光。激光会沿着直线行进，当其抵达矩形区域的某个边界时，它会从跟该边界平行的另一个边界射出，方向不变。具体的，当激光抵达边界 x=n（0≤y≤m）时，激光会从 x=0 射出；当激光抵达边界 y=m（0≤x≤n）时，激光会从 y=0 射出；然而在 x=0 处有一个吸收装置，当激光抵达边界 x=0 时，激光会被吸收。

区域内有若干个靶，每个靶都可以看作一个点，并且其坐标均为整数。当激光击中靶子时，靶子会消失，同时玩家得一分。

小明希望自己的得分最大。请计算小明可以获得的最大得分是多少。

输入描述

第一行三个整数 n、m、k（1≤n,m≤10^6，0≤k≤500），表示矩形区域的大小以及靶子的数量。

接下来 k 行，每行两个整数 x_i, y_i（0<x_i<n，0<y_i<m），表示靶子的坐标。保证所有靶子的坐标都不相同。

输出描述

一个整数，表示小明可以获得的最大得分。

样例输入

5 5 7

1 3

1 4

2 1

2 2

3 3

3 4

4 2

样例输出

4

样例说明： 向 (1,1) 方向发射激光，击中的靶子的数量最多，得分最大为 4。

参考题解

解题思路：

1. 激光路径的周期性：由于反射规则，激光路径在平面上会周期性重复。可以将整个平面"展开"，将反射视为进入了一个镜像世界。
2. 方向向量的简化：对于每个靶子，考虑它在四个象限的镜像位置，这些点与原点连线的方向向量可以代表激光可能的方向。方向向量需要化简为最简分数形式。
3. 直线方程与整数解：对于每个方向向量，检查每个靶子是否位于该方向的激光路径上，这转化为求解线性丢番图方程。
4. 使用扩展欧几里得算法求解方程，判断是否存在整数解。
5. 对每个方向向量，计算能击中的靶子数量，取最大值。

C++：

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

int gcd(int a, int b) {
    return __gcd(abs(a), abs(b));
}

tuple<int, long long, long long> extended_gcd(long long a, long long b) {
    if (a == 0) return {b, 0, 1};
    auto [d, x1, y1] = extended_gcd(b % a, a);
    long long x = y1 - (b / a) * x1;
    long long y = x1;
    return {d, x, y};
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<pair<int, int>> targets(k);
    for (int i = 0; i < k; i++) {
        cin >> targets[i].first >> targets[i].second;
    }
    
    int max_score = k > 0 ? 1 : 0;
    set<pair<int, int>> directions;
    
    for (auto& [x, y] : targets) {
        for (int a_wrap = 0; a_wrap <= 1; a_wrap++) {
            for (int b_wrap = 0; b_wrap <= 1; b_wrap++) {
                int nx = x + a_wrap * n;
                int ny = y + b_wrap * m;
                if (nx == 0 && ny == 0) continue;
                int g = gcd(nx, ny);
                directions.insert({nx / g, ny / g});