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

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

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

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

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

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

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🌈 字节跳动秋招笔试，来啦！！！

🧸 本次难度中等偏上，最后一题需要用比较好的数据结构来处理

1️⃣ 模拟题，根据给出的数据模拟即可，可以用二进制优化

2️⃣ 贪心题，每次把后面的0换到前面即可

3️⃣ 预处理+dp，经典老题了

4️⃣ 最简单无脑的做法直接扔 manacher，但要会模版，还有一种做法是字符串哈希+二分。

📱 01.LED屏幕的秘密 评测链接🔗

问题描述

LYA 是一家电子公司的工程师，她正在研究一种新型的 LED 屏幕。这种屏幕由 5×4 的 LED 灯矩阵组成，可以显示 0 到 9 的数字。每个数字的显示都需要特定的 LED 灯组合亮起。

0:      1:      2:      3:      4:
####    ..##    ####    ####    #.#.
#..#    ...#    ...#    ...#    #.#.
#..#    ...#    ####    ####    ####
#..#    ...#    #...    ...#    ..#.
####    ...#    ####    ####    ..#.

5:      6:      7:      8:      9:
####    ####    ####    ####    ####
#...    #...    ...#    #..#    #..#
####    ####    ...#    ####    ####
...#    #..#    ...#    #..#    ...#
####    ####    ...#    ####    ####

LYA 想要分析在数字变换过程中，每个 LED 灯的亮灭次数。她特别关注某个特定位置的 LED 灯，想知道在整个数字变换序列中，这个 LED 灯经历了多少次亮灭转换。

请你帮助 LYA 编写一个程序，计算指定位置的 LED 灯在给定的数字变换序列中的亮灭转换次数。

输入格式

第一行输入一个整数 （），表示测试数据的组数。

对于每组测试数据：

• 第一行包含三个整数 、 和 （；；），分别表示数字变换序列的长度、关注的 LED 灯的行数和列数。
• 第二行是一个长度为 的字符串 ，仅由数字 0-9 组成，表示数字变换的顺序。

保证所有测试数据中 的总和不超过 。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示指定位置（第 行第 列）的 LED 灯在整个变换过程中经历的亮灭转换次数。

样例输入1

2
5 1 1
00000
6 1 2
114514

样例输出1

0
2

样例解释

样例 解释说明

样例1	对于第一组测试数据，(1,1) 位置的 LED 灯在显示数字 0 时始终保持亮起状态，没有发生亮灭转换。 对于第二组测试数据，(1,2) 位置的 LED 灯在数字从 4 变为 5 时由暗变亮，在 5 变为 1 时由亮变暗，共经历 2 次转换。

数据范围

• 
• 
• 
• 
• 所有测试数据中 的总和不超过

题解

模拟+枚举

可以用一个 20 位整数来表示每个数字的 LED 显示模式，其中每一位代表一个 LED 的亮灭状态。

参考代码

• Python

# LED 显示模式：每个数字用 20 位整数表示，对应 5x4 的 LED 矩阵
LED_PATTERNS = [
    0b11111001100110011111,  # 0
    0b00110001000100010001,  # 1
    0b11110001111110001111,  # 2
    0b11110001111100011111,  # 3
    0b10101010111100100010,  # 4
    0b11111000111100011111,  # 5
    0b11111000111110011111,  # 6
    0b11110001000100010001,  # 7
    0b11111001111110011111,  # 8
    0b11111001111100011111   # 9
]

def count_led_changes(n, x, y, s):
    # 计算 LED 在 5x4 矩阵中的位置
    pos = 19 - ((x - 1) * 4 + (y - 1))  # 从右往左数，因为二进制表示是从右往左的
    mask = 1 << pos
    count = 0
    
    # 遍历数字序列，比较相邻数字的 LED 状态
    for i in range(n - 1):
        current = int(s[i])
        next = int(s[i+1])
        # 检查指定位置的 LED 状态是否发生变化
        if (LED_PATTERNS[current] & mask) != (LED_PATTERNS[next] & mask):
            count += 1
    return count

# 读取测试用例数量
T = int(input())

# 处理每个测试用例
for _ in range(T):
    # 读取 n, x, y 和数字序列
    n, x, y = map(int, input().split())
    s = input().strip()
    # 计算并输出 LED 变化次数
    print(count_led_changes(n, x, y, s))

• Java

import java.util.Scanner;

public class Main {
    // LED 显示模式：每个数字用 20 位整数表示，对应 5x4 的 LED 矩阵
    private static final int[] LED_PATTERNS = {
        0b11111001100110011111,  // 0
        0b00110001000100010001,  // 1
        0b11110001111110001111,  // 2
        0b11110001111100011111,  // 3
        0b10101010111100100010,  // 4
        0b11111000111100011111,  // 5
        0b11111000111110011111,  // 6
        0b11110001000100010001,  // 7
        0b11111001111110011111,  // 8
        0b11111001111100011111   // 9
    };

    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 x = scanner.nextInt();
            int y = scanner.nextInt();
            String s = scanner.next();

            System.out.println(countLedChanges(n, x, y, s));
        }
        scanner.close();
    }

    private static int countLedChanges(int n, int x, int y, String s) {
        // 计算 LED 在 5x4 矩阵中的位置
        int pos = 19 - ((x - 1) * 4 + (y - 1));  // 从右往左数，因为二进制表示是从右往左的
        int mask = 1 << pos;
        int count = 0;

        // 遍历数字序列，比较相邻数字的 LED 状态
        for (int i = 0; i < n - 1; i++) {
            int current = s.charAt(i) - '0';
            int next = s.charAt(i+1) - '0';
            // 检查指定位置的 LED 状态是否发生变化
            if ((LED_PATTERNS[current] & mask) != (LED_PATTERNS[next] & mask)) {
                count++;
            }
        }
        return count;
    }
}

• Cpp

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// LED 显示模式：每个数字用 20 位整数表示，对应 5x4 的 LED 矩阵
const vector<int> LED_PATTERNS = {
    0b11111001100110011111,  // 0
    0b00110001000100010001,  // 1
    0b11110001111110001111,  // 2
    0b11110001111100011111,  // 3
    0b10101010111100100010,  // 4
    0b11111000111100011111,  // 5
    0b11111000111110011111,  // 6
    0b11110001000100010001,  // 7
    0b11111001111110011111,  // 8
    0b11111001111100011111   // 9
};

// 计算 LED 变化次数的函数
int countLedChanges(int n, int x, int y, const string& s) {
    // 计算 LED 在 5x4 矩阵中的位置
    int pos = 19 - ((x - 1) * 4 + (y - 1));  // 从右往左数，因为二进制表示是从右往左的
    int mask = 1 << pos;
    int count = 0;

    // 遍历数字序列，比较相邻数字的 LED 状态
    for (int i = 0; i < n - 1; i++) {
        int current = s[i] - '0';
        int next = s[i+1] - '0';
        // 检查指定位置的 LED 状态是否发生变化
        if ((LED_PATTERNS[current] & mask) != (LED_PATTERNS[next] & mask)) {
            count++;
        }
    }
    return count;
}

int main() {
    int T;
    cin >> T;  // 读取测试用例数量

    // 处理每个测试用例
    for (int t = 0; t < T; t++) {
        int n, x, y;
        string s;
        // 读取 n, x, y 和数字序列
        cin >> n >> x >> y >> s;

        // 计算并输出 LED 变化次数
        cout << countLedChanges(n, x, y, s) << endl;
    }

    return 0;
}

✨ 02.LYA的字符串魔法 评测链接🔗

问题描述

LYA是一位魔法学院的学生，她最近学会了一种神奇的字符串魔法。这种魔法可以交换字符串中任意两个字符的位置。LYA有一个由 和 组成的魔法字符串 ，她想要通过恰好 次魔法操作，使得这个字符串的字典序最小。

在魔法学院中，字符串的字典序定义如下：

1. 如果字符串 是字符串 的前缀，且 ，则 的字典序小于 。
2. 如果字符串 和 的第一个不同字符位置上， 的字符比 的字符更靠前，则 的字典序小于 。

现在，LYA需要你的帮助来完成这个魔法任务。你能帮她找出经过恰好 次魔法操作后，字典序最小的魔法字符串吗？

输入格式

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

对于每个测试用例：

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

保证所有测试用例中 的总和不超过 。

输出格式

对于每个测试用例，输出一行，包含一个长度为 的字符串，表示经过恰好 次魔法操作后，字典序最小的魔法字符串。

样例输入1

2
6 2
110000
2 10
11

样例输出1

000011
11

样例解释

样例 解释说明

样例1	对于第一组测试数据，LYA需要恰好进行 次魔法操作。她可以依次交换 和 ，然后交换 和 ，得到字典序最小的字符串 "000011"。 对于第二组测试数据，无论进行多少次操作，字符串 "11" 都无法变得更小，所以输出原字符串。

数据范围

• 
• 
• 
• 所有测试用例中 的总和不超过

题解

模拟

可以观察到，要使字符串字典序最小，就应该尽可能将 '0' 移到前面，将 '1' 移到后面。

解题思路如下：

1. 首先，统计字符串中 '0' 和 '1' 的位置。
2. 从后往前遍历 '0' 的位置，从前往后遍历 '1' 的位置。
3. 每次操作，交换一个靠后的 '0' 和一个靠前的 '1'，如果最右边0的位置已经小于最左边的1了，提前break
4. 最多进行 次这样的交换，或者直到无法再进行交换为止。

参考代码

参考代码

• Python

def solve():
    n, k = map(int, input().split())
    s = input().strip()
    
    # 特判 n = 2 且 k 为奇数的情况
    if n == 2 and k % 2 == 1:
        print(s[::-1])  # 直接输出反转的字符串
        return
    
    # 统计 '0' 和 '1' 的位置
    zero = [i for i in range(n) if s[i] == '0']
    one = [i for i in range(n) if s[i] == '1']
    
    # 交换操作
    i, j = len(zero) - 1, 0
    while k > 0 and i >= 0 and j < len(one):
        if zero[i] <= one[j]:
            break
        
        zero[i], one[j] = one[j], zero[i]
        i -= 1
        j += 1
        k -= 1
    
    # 构造结果字符串
    result = ['0'] * n
    for pos in one:
        result[pos] = '1'
    
    print(''.join(result))

T = int(input())
for _ in range(T):
    solve()

• Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {