🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 编程一对一辅导

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 50+ 套笔试题，笔试真题 会在第一时间跟新

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞！

🌰 饿了么春招第一场，来咯 !!!

🍉 这次笔试应该用的都是同一套卷子

1️⃣ 比较简单的贪心猜结论题

2️⃣ 看起来很很复杂，注意到机器人最多移动 2 * n 次，直接暴力即可。

3️⃣ 第三题是一道生成树和二分结合的问题，但比较容易想，难度不大

🍚 01.魔法字符串变形术

问题描述

K小姐是一位魔法师，她最近发明了一种神奇的字符串变形术。这种魔法可以将由 '0' 和 '1' 组成的字符串进行变形。每次施法，K小姐可以选择字符串中的任意一个字符，将 '0' 变成 '1'，或将 '1' 变成 '0'。

现在，K小姐想知道，如果她恰好施法 次，是否能将给定的字符串变成一个回文串。回文串是指从左往右读和从右往左读都一样的字符串。

输入格式

第一行输入一个整数 ，表示测试用例的数量。

对于每个测试用例：

• 第一行包含两个整数 和 ，分别表示字符串的长度和施法次数。
• 第二行包含一个长度为 的字符串 ，仅由字符 '0' 和 '1' 组成。

输出格式

对于每个测试用例，如果K小姐恰好施法 次后能将字符串变成回文串，输出 "YES"；否则输出 "NO"。每个答案占一行。

样例输入1

3
6 1
101100
6 2
101100
6 3
101100

样例输出1

YES
NO
YES

样例说明1

对于第一组测试数据，可得到的回文串为 "101101" 或 "001100"。 对于第二组测试数据，无论如何都不能使得其变成回文串。 对于第三组测试数据，由于其包含第一组测试数据，因此也可以变成回文串。

样例输入2

4
5 4
10101
4 3
1001
6 4
100100
6 5
000001

样例输出2

YES
NO
YES
YES

数据范围

• 
• 
• 

题解

贪心+猜结论

统计字符串前半部分与后半部分对应位置不同的字符数量，记为 。

如果 且 是偶数，或者 且字符串长度为奇数，则可以将字符串变为回文串。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

import sys

def solve(s, k):
    """
    判断是否能将字符串s通过k次操作变为回文串
    
    参数:
    s (str): 输入的字符串
    k (int): 允许的操作次数
    
    返回:
    str: 'YES' 如果可以变为回文串，否则 'NO'
    """
    n = len(s)
    # 计算需要改变的字符数量
    diff = sum(s[i] != s[n-1-i] for i in range(n//2))
    
    # 判断是否可以变为回文串
    if diff <= k and (k - diff) % 2 == 0:
        return 'YES'
    if diff <= k and n % 2 == 1:
        return 'YES'
    return 'NO'

# 读取输入
T = int(sys.stdin.readline().strip())
for _ in range(T):
    n, k = map(int, sys.stdin.readline().split())
    s = sys.stdin.readline().strip()
    print(solve(s, k))

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        
        for (int t = 0; t < T; t++) {
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            String s = scanner.next();
            System.out.println(solve(s, k));
        }
        
        scanner.close();
    }
    
    /**
     * 判断是否能将字符串s通过k次操作变为回文串
     * 
     * @param s 输入的字符串
     * @param k 允许的操作次数
     * @return "YES" 如果可以变为回文串，否则 "NO"
     */
    public static String solve(String s, int k) {
        int n = s.length();
        int diff = 0;
        
        // 计算需要改变的字符数量
        for (int i = 0; i < n / 2; i++) {
            if (s.charAt(i) != s.charAt(n - 1 - i)) {
                diff++;
            }
        }
        
        // 判断是否可以变为回文串
        if (diff <= k && (k - diff) % 2 == 0) {
            return "YES";
        }
        if (diff <= k && n % 2 == 1) {
            return "YES";
        }
        return "NO";
    }
}

• Cpp

#include <iostream>
#include <string>

using namespace std;

/**
 * 判断是否能将字符串s通过k次操作变为回文串
 * 
 * @param s 输入的字符串
 * @param k 允许的操作次数
 * @return "YES" 如果可以变为回文串，否则 "NO"
 */
string solve(const string& s, int k) {
    int n = s.length();
    int diff = 0;
    
    // 计算需要改变的字符数量
    for (int i = 0; i < n / 2; ++i) {
        if (s[i] != s[n - 1 - i]) {
            ++diff;
        }
    }
    
    // 判断是否可以变为回文串
    if (diff <= k && (k - diff) % 2 == 0) {
        return "YES";
    }
    if (diff <= k && n % 2 == 1) {
        return "YES";
    }
    return "NO";
}

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int n, k;
        string s;
        cin >> n >> k >> s;
        cout << solve(s, k) << endl;
    }
    
    return 0;
}

🍤 02.LYA的迷宫探险

问题描述

LYA 发现了一个神奇的迷宫。这个迷宫是一个 的方格阵列，每个方格上都有一个指示牌，上面写着 0 或 1。LYA 发明了一种特殊的探险机器人，它会按照以下规则在迷宫中移动：

1. 当机器人到达写有 0 的方格时，它会向下移动一格。
2. 当机器人到达写有 1 的方格时，它会向右移动一格。
3. 如果机器人移动到迷宫边界之外，就会停止移动。

LYA 对这个迷宫非常感兴趣，她想知道在迷宫的不同区域内，机器人的行为会有什么不同。她提出了 个问题，每个问题都是关于迷宫中的一个矩形区域 。LYA 想知道，如果机器人从 开始移动，它会从这个矩形区域的哪个位置离开。

输入格式

第一行输入一个整数 ，表示迷宫的大小。

接下来 行，每行输入 个整数 ，表示迷宫中每个方格上的数字。

第 行输入一个整数 ，表示 LYA 提出的问题数量。

接下来 行，每行输入四个整数 ，表示 LYA 询问的矩形区域范围。

输出格式

对于每个问题，输出一行，包含两个整数，表示机器人离开矩形区域的位置坐标。

样例输入1

4
1 0 0 1
0 0 1 1
1 0 1 0
0 1 1 1
2
2 2 4 4
2 3 3 3

样例输出1

4 4
2 3

样例输入2

5
1 0 0 1 0
1 1 0 1 0
0 0 1 1 1
0 1 0 1 1
1 1 1 1 0
2
2 2 3 5
1 1 5 5

样例输出2

3 5
3 5

数据范围

• 
• 
• 
• 
• 
• 

题解

看起来很复杂，但注意到每次机器人最多移动 的距离，所以可以直接暴力。

从起点开始，根据当前格子的值决定移动方向，直到离开指定区域。

时间复杂度为 ，其中 是询问次数， 是迷宫边长。空间复杂度为 ，

参考代码

• Python

import sys

def read_int():
    """读取一个整数"""
    return int(sys.stdin.readline().strip())

def read_ints():
    """读取一行整数"""
    return list(map(int, sys.stdin.readline().split()))

def solve(maze, x1, y1, x2, y2):
    """
    模拟机器人在指定区域内的移动
    
    参数:
    maze: 迷宫地图
    x1, y1, x2, y2: 指定区域的左上角和右下角坐标
    
    返回:
    tuple: 机器人离开区域的坐标
    """
    x, y = x1 - 1, y1 - 1
    last_x, last_y = x, y
    
    while x1 - 1 <= x <= x2 - 1 and y1 - 1 <= y <= y2 - 1:
        last_x, last_y = x, y
        if maze[x][y] == 1:
            y += 1
        else:
            x += 1
    
    return last_x + 1, last_y + 1

# 读取输入
n = read_int()
maze = [read_ints() for _ in range(n)]
q = read_int()

# 处理每个查询
for _ in range(q):
    x1, y1, x2, y2 = read_ints()
    result = solve(maze, x1, y1, x2, y2)
    print(*result)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取迷宫大小
        int n = scanner.nextInt();
        int[][] maze = new int[n][n];
        
        // 读取迷宫地图
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                maze[i][j] = scanner.nextInt();
            }
        }
        
        // 读取查询次数
        int q = scanner.nextInt();
        
        // 处理每个查询
        for (int i = 0; i < q; i++) {
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();