✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺
• 配套练习题库

互联网必备刷题宝典🔗

1️⃣：统计 01 串中 0 和 1 的个数，通过计算可能的交换方式确定不同字符串数量

2️⃣：使用模板匹配技术识别验证码图片中的"#"符号分布模式

3️⃣：构建字典树（Trie）优化异或查询，实现高效的数字黑板游戏

整体难度

这套题目整体难度适中，由简到难逐步递进：

• 第一题是基础的计数问题，需要理解交换操作的特性
• 第二题是模式识别问题，需要实现模板匹配
• 第三题是高级数据结构应用，需要熟悉字典树和位运算

01. 小基的拼图游戏

题目内容

小基是密码学研究中心的一名研究员，她正在研究一种新的字符串变换方法。她有一个由字符"0"和"1"组成的二进制字符串 。研究过程中，小基需要对这个字符串进行一次且仅一次的基本变换操作：

选择两个不同的位置 和 （其中 ），交换这两个位置上的字符 和 。

小基想知道，通过所有可能的一次变换操作，最多能生成多少个不同的字符串？

输入描述

一个仅由字符"0"和"1"构成的字符串 。

输出描述

一个整数，表示通过一次变换操作能生成的不同字符串的数量。

样例1

输入：

1100

输出：

5

题解

这道题目要求计算通过一次交换操作能得到多少个不同的字符串。

分析交换操作的特性：

• 交换相同字符（两个 0 或两个 1）：字符串保持不变。
• 交换不同字符（一个 0 和一个 1）：会得到一个新的字符串。

解题思路是统计字符串中 0 和 1 的个数，分别记为 和 。

可以选择的 0 和 1 的交换方式有 种，每种交换都会产生一个不同的字符串。

另外，如果存在至少两个相同字符（ 或 ），交换这两个相同字符后，字符串保持不变，这种情况也应算作一种结果。

因此，答案是 （如果 或 ，则再加 1）。

算法的时间复杂度是 ，其中 是字符串的长度，主要用于统计 0 和 1 的个数。空间复杂度是 ，只需要常数级的额外空间。

对于题目给出的样例"1100"，其中有 2 个 0 和 2 个 1，所以答案是 。

三语言参考代码

• Cpp

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

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    
    // 计数0和1的数量
    long long num0 = 0, num1 = 0;
    for (char ch : s) {
        if (ch == '0') num0++;
        else num1++;
    }
    
    // 计算结果
    long long res = num0 * num1;
    // 如果有至少两个相同字符，可以交换它们得到相同字符串
    if (num0 >= 2 || num1 >= 2) res++;
    
    cout << res << "\n";
    return 0;
}

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入的01串
s = input()

# 统计0和1的个数
dig0 = s.count('0')
dig1 = s.count('1')

# 计算结果
ans = dig0 * dig1
# 如果有至少两个相同字符，交换后字符串不变，也算一种结果
if dig0 >= 2 or dig1 >= 2:
    ans += 1

# 输出结果
print(ans)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        // 读取输入的01串
        String s = scan.next();
        
        // 统计0和1的个数
        long zCnt = 0, oCnt = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0') zCnt++;
            else oCnt++;
        }
        
        // 计算不同字符交换的结果数
        long res = zCnt * oCnt;
        
        // 如果存在至少两个相同字符，交换它们后字符串不变，也算一种结果
        if (zCnt >= 2 || oCnt >= 2) res++;
        
        // 输出结果
        System.out.println(res);
        scan.close();
    }
}

02. 小柯的智能验证系统

题目内容

小柯是一家科技公司的安全专家，为了解决日益严重的机器人自动注册问题，她设计了一种创新的图像验证码系统。

这个系统的核心思想是：在 5×5 的网格中同时放置特殊符号"#"和数字（0-9）。真正的验证码信息隐藏在"#"符号的分布模式中，而数字只是用来干扰机器人识别。

每个数字（0-9）在 5×5 网格中都有唯一的"#"符号排列模式：

例如数字 5 的模式如下：

#...#
#.###
#...#
###.#
#...#

系统可能在非"#"的位置随机填入 0-9 的数字，但这些数字对于验证码的正确识别没有意义，例如：

#222#
#2###
#232#
###2#
#272#

这张图片中的"#"符号排列模式正好代表数字 5。

现在，小柯向你提供了 张验证码图片，请你识别出每张图片代表的真实数字，并按顺序输出这些数字组成的验证码。

输入描述

第一行一个整数 （），表示验证码图片的数量。

接下来 行，每 5 行描述一张 5×5 的验证码图片。图片中只包含字符"#"和数字 0-9。

输出描述

一个整数，表示所有验证码图片按顺序识别出的数字组成的结果。

样例1

输入：

1
#222#
#2###
#232#
###2#
#272#

输出：

5

样例2

输入：

2
#222#
#2###
#232#
###2#
#272#
##1##
##1##
##1##
##1##
##1##

输出：

51

题解

这道题目的核心是模式识别问题。需要识别 5×5 网格中"#"符号的分布模式，忽略其中的数字干扰，从而判断每张图片代表的实际数字。

首先，定义每个数字 0-9 对应的"#"符号模式。这些模式可以硬编码在程序中，作为识别的基准。每个数字都有唯一的 5×5 模式，比如数字 5 的模式如题目所示。

解题步骤：

1. 初始化模板：定义 0-9 十个数字的"#"符号分布模式。每个模式是一个 5×5 的网格，其中"#"表示该位置应该有特殊符号，"."表示该位置可以是任何数字或空白。

2. 读取输入：读取 及接下来的 行图片数据，每 5 行构成一张图片。

3. 预处理图片：对每张图片进行预处理，将所有数字字符替换为"."，保留"#"符号。这样处理后的图片就只包含模式信息。

4. 模式匹配：将处理后的图片与预定义的 10 个数字模板进行比对。如果某个模板与图片完全匹配，那么这张图片就代表对应的数字。

5. 组合结果：按顺序将识别出的数字组合起来，得到最终的验证码。

处理 张图片，每张图片需要与 10 个模板进行比对，每次比对需要检查 5×5=25 个位置，因此总的时间复杂度是 。对于 的数据范围来说，这个复杂度是完全可接受的。

难点在于正确定义各个数字的模板，以及准确地进行模式匹配。

三语言参考代码

• Cpp

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

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int m;
    cin >> m;  // 读入图片数量
    
    // 定义0-9各数字对应的模板
    vector<vector<string>> mods(10, vector<string>(5));
    
    // 初始化各数字模板
    mods[0] = {
        "#...#",
        "#.#.#",
        "#.#.#",
        "#.#.#",
        "#...#"
    };
    mods[1] = {
        "##.##",
        "##.##",
        "##.##",
        "##.##",
        "##.##"
    };
    mods[2] = {
        "#...#",
        "###.#",
        "#...#",
        "#.###",
        "#...#"
    };
    mods[3] = {
        "#...#",
        "###.#",
        "#...#",
        "###.#",
        "#...#"
    };
    mods[4] = {
        "#.#.#",
        "#.#.#",
        "#...#",
        "###.#",
        "###.#"
    };
    mods[5] = {
        "#...#",
        "#.###",
        "#...#",
        "###.#",
        "#...#"
    };
    mods[6] = {
        "#...#",
        "#.###",
        "#...#",
        "#.#.#",
        "#...#"
    };
    mods[7] = {
        "#...#",
        "###.#",
        "###.#",
        "###.#",
        "###.#"
    };
    mods[8] = {
        "#...#",
        "#.#.#",
        "#...#",
        "#.#.#",
        "#...#"
    };
    mods[9] = {
        "#...#",
        "#.#.#",
        "#...#",
        "###.#",
        "#...#"
    };
    
    // 读取所有图片
    vector<vector<string>> pics(m, vector<string>(5));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> pics[i][j];
        }
    }
    
    string res;
    res.reserve(m);
    
    // 处理每张图片
    for (int i = 0; i < m; i++) {
        // 将数字替换为'.'
        vector<string> image = pics[i];
        for (int r = 0; r < 5; r++) {
            for (int c = 0; c < 5; c++) {
                if (isdigit(image[r][c])) {
                    image[r][c] = '.';
                }
            }
        }
        
        // 与模板匹配
        int digit = -1;
        for (int d = 0; d < 10; d++) {
            bool same = true;
            for (int r = 0; r < 5; r++) {
                if (image[r] != mods[d][r]) {
                    same = false;
                    break;
                }
            }
            if (same) {
                digit = d;
                break;
            }
        }
        
        // 添加识别结果
        res.push_back('0' + digit);
    }
    
    // 输出结果
    cout << res << "\n";
    return 0;
}

• Python

import sys
input = lambda:sys.stdin.readline().strip()

def main():
    # 读入图片数量
    m = int(input())
    
    # 定义0-9各数字对应的模板
    # 其中'#'表示特殊符号，'.'表示可以是任何数字
    tpl_list = [
        [  # 数字0的模板
            "#...#",
            "#.#.#",
            "#.#.#",
            "#.#.#",
            "#...#"
        ],
        [  # 数字1的模板
            "##.##",
            "##.##",
            "##.##",
            "##.##",
            "##.##"
        ],
        [  # 数字2的模板
            "#...#",
            "###.#",
            "#...#",
            "#.###",
            "#...#"
        ],
        [  # 数字3的模板
            "#...#",
            "###.#",
            "#...#",
            "###.#",
            "#...#"
        ],
        [  # 数字4的模板
            "#.#.#",
            "#.#.#",
            "#...#",
            "###.#",
            "###.#"
        ],
        [  # 数字5的模板
            "#...#",
            "#.###",
            "#...#",
            "###.#",
            "#...#"
        ],
        [  # 数字6的模板
            "#...#",
            "#.###",
            "#...#",
            "#.#.#",
            "#...#"
        ],
        [  # 数字7的模板
            "#...#",
            "###.#",
            "###.#",
            "###.#",
            "###.#"
        ],
        [  # 数字8的模板
            "#...#",
            "#.#.#",
            "#...#",
            "#.#.#",
            "#...#"
        ],
        [  # 数字9的模板
            "#...#",
            "#.#.#",
            "#...#",
            "###.#",
            "#...#"
        ]