✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

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

🌸 目前本专栏已经上线100+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

题目一：小兰的序列统计

1️⃣：维护两个计数器分别统计遇到的0和1的个数

2️⃣：根据当前字符是0还是1，选择对应的不同字符计数器作为答案

难度：简单

这道题目的关键在于理解"不同"的含义，对于当前位置的字符，统计左侧与它不同的字符个数。通过维护两个计数器，可以在O(n)时间内解决问题。

题目二：小基的魔法矩阵构造

1️⃣：分析2×2子矩阵和总和的关系

2️⃣：使用棋盘染色的构造方法

3️⃣：令(i+j)为偶数的位置填1，为奇数的位置填-1

难度：中等

这道题目需要理解矩阵构造的数学原理。通过棋盘染色的巧妙构造，可以保证每个2×2子矩阵包含两个1和两个-1，和为0，同时整个矩阵的总和也为0。

题目三：小毛的幸运数字变换

1️⃣：使用动态规划，状态为dp[i][r]表示前i位余数为r的最小修改次数

2️⃣：状态转移时枚举每一位可能的数字0-9

3️⃣：记录路径信息以便输出修改后的数字

难度：中等偏难

这道题目结合了动态规划和数论知识，需要理解模运算的性质。通过记录状态转移的路径，可以在求出最少修改次数的同时构造出具体的修改方案。

01. 小兰的序列统计

问题描述

小兰正在研究一串由红灯和绿灯组成的信号序列。这个序列可以用一个由 和 组成的字符串 来表示，其中 代表红灯， 代表绿灯。

对于序列中的每个位置 （），小兰想要知道在第 个位置左侧有多少个与当前位置颜色不同的灯。

输入格式

第一行包含一个正整数 （），表示测试数据的组数。

对于每组测试数据：

• 第一行包含一个正整数 （），表示信号序列的长度。
• 第二行包含一个长度为 的字符串 ，仅包含字符 和 。

输出格式

对于每组测试数据，输出一行，包含 个非负整数 ，其中 表示位置 左侧与位置 不同的字符个数。相邻整数之间用空格分隔。

样例输入

2
4
1101
5
01010

样例输出

0 0 2 1
0 1 1 2 2

数据范围

• 
• 
• 字符串 仅包含字符 和

题解

这道题的核心思路是维护两个计数器：一个统计已经遇到的 的个数，一个统计已经遇到的 的个数。

当我们遍历到位置 时：

• 如果当前字符是 ，那么答案就是之前遇到的 的个数
• 如果当前字符是 ，那么答案就是之前遇到的 的个数

然后更新对应的计数器即可。

这个算法的时间复杂度是 ，对于给定的数据范围完全可以接受。

关键点在于理解"不同"的含义：对于当前位置的字符，我们要统计左侧与它不同的字符个数。

参考代码

• Python

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

T = int(input())
for _ in range(T):
    n = int(input())
    s = input()
    
    # cnt0: 统计遇到的'0'的个数, cnt1: 统计遇到的'1'的个数
    cnt0 = cnt1 = 0
    res = []
    
    for i in range(n):
        if s[i] == '0':
            # 当前字符是'0'，答案是之前遇到的'1'的个数
            res.append(cnt1)
            cnt0 += 1
        else:
            # 当前字符是'1'，答案是之前遇到的'0'的个数
            res.append(cnt0)
            cnt1 += 1
    
    print(' '.join(map(str, res)))

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n;
        string s;
        cin >> n >> s;
        
        // cnt0: 统计遇到的'0'的个数, cnt1: 统计遇到的'1'的个数
        int cnt0 = 0, cnt1 = 0;
        vector<int> ans(n);
        
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') {
                // 当前字符是'0'，答案是之前遇到的'1'的个数
                ans[i] = cnt1;
                cnt0++;
            } else {
                // 当前字符是'1'，答案是之前遇到的'0'的个数
                ans[i] = cnt0;
                cnt1++;
            }
        }
        
        for (int i = 0; i < n; i++) {
            cout << ans[i] << (i == n - 1 ? '\n' : ' ');
        }
    }
    
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        
        while (T-- > 0) {
            int n = sc.nextInt();
            String s = sc.next();
            
            // cnt0: 统计遇到的'0'的个数, cnt1: 统计遇到的'1'的个数
            int cnt0 = 0, cnt1 = 0;
            int[] ans = new int[n];
            
            for (int i = 0; i < n; i++) {
                if (s.charAt(i) == '0') {
                    // 当前字符是'0'，答案是之前遇到的'1'的个数
                    ans[i] = cnt1;
                    cnt0++;
                } else {
                    // 当前字符是'1'，答案是之前遇到的'0'的个数
                    ans[i] = cnt0;
                    cnt1++;
                }
            }
            
            for (int i = 0; i < n; i++) {
                System.out.print(ans[i]);
                if (i < n - 1) System.out.print(" ");
            }
            System.out.println();
        }
        
        sc.close();
    }
}

02. 小基的魔法矩阵构造

问题描述

小基正在研习古老的魔法阵构造技术。她需要在一个 行 列的魔法矩阵中填入非零整数，使得魔法阵能够平衡能量。

具体而言，魔法阵的平衡条件是：任意一个 的子矩阵中，四个位置的数值之和必须等于整个 矩阵所有数值的总和。

已知 为偶数，魔法学理论保证这样的构造一定存在。

输入格式

第一行包含一个正整数 （），表示测试数据的组数。

对于每组测试数据：

• 第一行包含两个正整数 （，且 ）。
• 保证单个测试文件中所有 的和不超过 。

输出格式

对于每组测试数据，输出 行，第 行包含 个用空格分隔的非零整数 ，其中 。

如果存在多种构造方案，输出任意一种即可。

样例输入

2
2 2
3 4

样例输出

1 -1
-1 1
1 -1 1 -1
-1 1 -1 1
1 -1 1 -1

数据范围

• 
• 
• 
• 为偶数
• 
• 

题解

这道题的关键观察是：我们需要构造一个矩阵，使得任意 子矩阵的和等于整个矩阵的总和。

一个巧妙的构造方法是使用棋盘染色的思想：

• 将矩阵按照 的奇偶性进行染色
• 如果 为偶数，填入
• 如果 为奇数，填入

这样构造的原理：

1. 由于 为偶数，整个矩阵中 和 的个数相等，所以总和为
2. 对于任意 子矩阵，其四个位置的坐标分别为
3. 这四个位置的 的奇偶性分别为：偶，奇，奇，偶
4. 因此每个 子矩阵恰好包含两个 和两个 ，和为

这个构造方法保证了条件的满足，时间复杂度为 。

参考代码

• Python

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

T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    
    # 构造棋盘模