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

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

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

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

✨ 算法合集传送们 -> 🧷学长刷题笔记

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

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

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

这套卷比较简单，大家可以练练手

1️⃣ 哈希表+枚举

2️⃣ 计数器+枚举

3️⃣ 排序+贪心

🕹️ 01.遥控器输入优化 评测链接🔗

问题描述

LYA 最近购买了一台智能电视，但发现遥控器的输入方式有些麻烦。电视屏幕上显示了一个虚拟键盘，LYA 需要使用遥控器的方向键（上、下、左、右）来移动光标，然后按 OK 键选择字符。

虚拟键盘是一个 的矩阵，包含大写字母 'A''Z'、小写字母 'a''z'、数字 '1'~'9' 和一些特殊字符 ' '、'.'、'/'、':'、';'、'@'，以及空格（用下划线 '_' 表示）。

LYA 想知道，要输入一个给定的字符串，她最少需要按多少次遥控器按键？

输入格式

第一行给出测试用例的个数 。

对于每一组用例：

• 第一行给出两个整数 和 ，表示虚拟键盘的行数和列数。
• 接下来 行，每行 个字符，描述虚拟键盘的布局。
• 最后一行给出要输入的字符串 。

输出格式

对于每组测试用例，输出一个整数，表示最少需要按键的次数。

样例输入1

1
5 11
___________
____A______
________M__
___________
_C_________
ACM

样例输出1

23

样例输入2

1
3 9
ABCDEFGHl
JKLMNOPQR
STUvwXYz_
NOwCODER

样例输出2

33

样例解释

数据范围

题解

模拟+哈希表

这道题目的核心是模拟遥控器输入过程，并找出最优的输入路径。

可以通过以下步骤来解决这个问题：

1. 首先记录每个字符在虚拟键盘上的位置。可以使用一个哈希表（如 C++ 中的 map）来存储每个字符的坐标。

2. 从输入字符串的第一个字符开始，依次计算光标从当前位置移动到目标字符位置所需的步数。这个步数等于横向移动的步数加上纵向移动的步数，即曼哈顿距离。

3. 对于每个字符，需要加上移动步数和一次按 OK 键的步数。

4. 最后，需要更新光标的当前位置为刚刚输入的字符的位置。

这个解法的时间复杂度是 ，其中 是构建哈希表的时间， 是遍历输入字符串的时间。考虑到题目给出的数据范围，这个复杂度是完全可以接受的。

参考代码

• Python

def solve():
    n, m = map(int, input().split())
    # 使用字典存储每个字符的位置
    char_pos = {}
    for i in range(n):
        row = input()
        for j, char in enumerate(row):
            char_pos[char] = (i, j)
    
    s = input()
    res = len(s)  # 每个字符都需要按一次OK键
    x, y = 0, 0  # 初始光标位置
    
    for char in s:
        # 获取目标字符的位置
        a, b = char_pos[char]
        # 计算移动步数并累加
        res += abs(a - x) + abs(b - y)
        # 更新光标位置
        x, y = a, b
    
    print(res)

# 读取测试用例数量
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 {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            solve(br);
        }
    }

    static void solve(BufferedReader br) throws IOException {
        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

        // 使用Map存储每个字符的位置
        Map<Character, int[]> charPos = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String row = br.readLine();
            for (int j = 0; j < m; j++) {
                charPos.put(row.charAt(j), new int[]{i, j});
            }
        }

        String s = br.readLine();
        int res = s.length();  // 每个字符都需要按一次OK键
        int x = 0, y = 0;  // 初始光标位置

        for (char c : s.toCharArray()) {
            int[] pos = charPos.get(c);
            // 计算移动步数并累加
            res += Math.abs(pos[0] - x) + Math.abs(pos[1] - y);
            // 更新光标位置
            x = pos[0];
            y = pos[1];
        }

        System.out.println(res);
    }
}

• Cpp

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    
    // 使用map存储每个字符的位置
    map<char, pair<int, int>> char_pos;
    for (int i = 0; i < n; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < m; j++) {
            char_pos[row[j]] = {i, j};
        }
    }
    
    string s;
    cin >> s;
    int res = s.length();  // 每个字符都需要按一次OK键
    int x = 0, y = 0;  // 初始光标位置
    
    for (char c : s) {
        auto [a, b] = char_pos[c];
        // 计算移动步数并累加
        res += abs(a - x) + abs(b - y);
        // 更新光标位置
        x = a, y = b;
    }
    
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

📖 02.LYA的期末考试 评测链接🔗

问题描述

LYA是一名高中生，平时喜欢打游戏，不太爱学习。这学期期末考试临近，学校决定采用全新的考试方式：每门科目都是100道选择题，每题只有A、B两个选项。LYA觉得这种考试方式很简单，即使不会做也可以靠猜，每题都有50%的正确率。

考试结束后，LYA收到了成绩单。看到自己的分数后，她突然好奇：如果当时在考场上，每道题都选择与自己实际选择相反的选项，最终的得分会不会更高呢？

现在，LYA想请你帮她分析一下，对于每门科目，如果她选择了相反的答案，最终的正确题目数量是否会更多。

输入格式

第一行输入一个正整数 （），表示科目数量。

对于每门科目：

• 第一行输入一个正整数 （），表示该科目的题目数量。
• 第二行输入 个字母，表示LYA的答案，每个字母为A或B。
• 第三行输入 个字母，表示正确答案，每个字母为A或B。

输出格式

对于每门科