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

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

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

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🍥 本次题目难度不小，其中第二题和上周蚂蚁的T3类似，

1️⃣ 贪心，优先将大的数字覆给前面的

2️⃣ bitset 优化转移

3️⃣ 枚举+找规律

🍡 01.LYA的键盘映射

问题描述

LYA是一名热爱编程的高中生。最近，她获得了一个特殊的九键键盘，键盘布局如下：

A | B | C
D | E | F
G | H | I
# | J | #

LYA发现这个键盘可以将每个键映射到一个数字。她随机按下了几个键，形成了一个字符串 。现在，她想找出一种映射方式，使得映射后得到的数字最大。

例如，如果将 A 映射为 2，C 映射为 6，那么字符串 "AC" 就会被映射为数字 26。

LYA想知道，对于给定的字符串 ，最大可能的映射结果是多少。

输入格式

输入一行，包含一个字符串 ，由大写字母 A 到 J 组成。

输出格式

输出四行，前三行每行包含三个数字，最后一行包含 #x#，其中 x 为一个数字。这些数字表示键盘上每个位置的映射结果。

样例输入1

BCD

样例输出1

698
754
321
#0#

样例输入2

ABCDEFGHIJ

样例输出2

987
654
321
#0#

样例输入3

J

样例输出3

876
543
210
#9#

数据范围

，其中 表示字符串 的长度。

题解

贪心

需要将出现在字符串中的字母按照出现顺序映射到最大的可用数字上。

具体步骤如下：

1. 遍历输入的字符串 ，为每个未映射的字符分配当前可用的最大数字（从9开始递减）。

2. 对于键盘上的每个位置，如果对应的字符已经被映射，则输出映射的数字；否则，输出当前可用的最大数字，并将该数字减1。

3. 特别处理 J 键的情况，它在最后一行单独输出。

参考代码

• Python

def solve():
    s = input().strip()
    mp = {}
    cnt = 9
    
    # 为输入的字符分配最大的可用数字
    for c in s:
        if c not in mp:
            mp[c] = cnt
            cnt -= 1
    
    # 输出映射结果
    for i in range(3):
        for j in range(3):
            c = chr(ord('A') + i * 3 + j)
            if c in mp:
                print(mp[c], end='')
            else:
                print(cnt, end='')
                cnt -= 1
        print()
    
    # 处理 J 键
    print('#', end='')
    if 'J' in mp:
        print(mp['J'], end='')
    else:
        print(cnt, end='')
    print('#')

solve()

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        solve(scanner);
        scanner.close();
    }
    
    public static void solve(Scanner scanner) {
        String s = scanner.nextLine().trim();
        Map<Character, Integer> mp = new HashMap<>();
        int cnt = 9;
        
        // 为输入的字符分配最大的可用数字
        for (char c : s.toCharArray()) {
            if (!mp.containsKey(c)) {
                mp.put(c, cnt);
                cnt--;
            }
        }
        
        // 输出映射结果
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                char c = (char)('A' + i * 3 + j);
                if (mp.containsKey(c)) {
                    System.out.print(mp.get(c));
                } else {
                    System.out.print(cnt);
                    cnt--;
                }
            }
            System.out.println();
        }
        
        // 处理 J 键
        System.out.print('#');
        if (mp.containsKey('J')) {
            System.out.print(mp.get('J'));
        } else {
            System.out.print(cnt);
        }
        System.out.println('#');
    }
}

• Cpp

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

void solve() {
    string s;
    cin >> s;
    map<char, int> mp;
    int cnt = 9;
    
    // 为输入的字符分配最大的可用数字
    for (char c : s) {
        if (mp.find(c) == mp.end()) {
            mp[c] = cnt--;
        }
    }
    
    // 输出映射结果
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            char c = 'A' + i * 3 + j;
            if (mp.find(c) != mp.end()) {
                cout << mp[c];
            } else {
                cout << cnt--;
            }
        }
        cout << endl;
    }
    
    // 处理 J 键
    cout << '#';
    if (mp.find('J') != mp.end()) {
        cout << mp['J'];
    } else {
        cout << cnt;
    }
    cout << '#' << endl;
}

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

⁕ 02.LYA的迷宫探险

问题描述

LYA是一位热爱冒险的年轻探险家。她最近发现了一个神秘的线性迷宫，迷宫由 个连续的房间组成，从左到右编号为 到 。LYA初始位于第 个房间。

迷宫的设计者留下了一串神秘指令，LYA需要按照这些指令移动。指令包括：

• L：向左移动一个房间（）。如果已在最左边（），则原地不动。
• R：向右移动一个房间（）。如果已在最右边（），则原地不动。
• ?：这是一个神秘指令，LYA可以随机将其解读为L或R，并执行相应动作。

由于?指令的存在，LYA的探险路径可能有多种可能。她想知道在所有可能的路径中，哪些房间她有可能到达。

我们用一个长度为 的字符串 来描述每个房间是否可能被到达。如果第 个房间可能被到达，则 ；否则，。

输入格式

第一行包含两个整数 和 （，），分别表示迷宫的房间数量和LYA的初始位置。

第二行包含一个长度为 （）的字符串，仅由字符L、R和?组成，表示LYA需要执行的指令序列。

输出格式

输出一行，包含一个长度为 的字符串，仅由字符0和1组成，表示每个房间是否可能被到达。

样例输入

5 1
R?L?

样例输出

11100

数据范围

• 
• 
• ，其中 为指令序列的长度

题解

bitset

除了cpp外其他语言在笔试中可能会通过不了

核心思想是用一个bitset来表示当前可能到达的位置，然后根据指令序列更新这个bitset。

1. 初始化一个长度为 的bitset，将第 位设为1，表示初始位置。
2. 遍历指令序列，对每个指令进行处理：
   • 对于L指令，将bitset右移一位，但保持第1位不变。
   • 对于R指令，将bitset左移一位，但保持第n位不变。
   • 对于?指令，将bitset左移和右移的结果进行或运算。
3. 用另一个bitset记录所有可能到达的位置（每次更新后与结果bitset进行或运算）。
4. 最后输出结果bitset。

时间复杂度：，其中 是房间数量， 是指令序列长度。

参考代码

• Python

def solve():
    # 读取输入
    n, k = map(int, input().split())
    s = input().strip()
    
    # 初始化bitset
    curr = 1 << (k - 1)
    result = curr
    
    # 遍历指令序列
    for cmd in s:
        if cmd == 'L':
            # 向左移动，保持最左位不变
            curr = ((curr >> 1) | (curr & 1)) & ((1 << n) - 1)
        elif cmd == 'R':
            # 向右移动，保持最右位不变
            curr = ((curr << 1) | (curr & (1 << (n-1)))) & ((1 << n) - 1)
        else:  # cmd == '?'
            # 左右都可能，取并集
            left = ((curr >> 1) | (curr & 1)) & ((1 << n) - 1)
            right = ((curr << 1) | (curr &