热乎乎的科大讯飞笔试复盘（2025.07.26场）：三道编程题思路与踩坑点分析

哈喽大家好，牛客的牛友们！

上周讯飞的笔试，感觉题目质量还不错，有签到题、构造题和经典的DP题，考察的知识点挺全面的。趁着记忆还热乎，赶紧把三道题的思路和AC代码复盘一下，希望能给后面参加笔试的同学一些参考，帮助大家少走弯路，顺利拿下Offer！

第一题：

题目大意

简单来说，就是给你一个只包含 '0' 和 '1' 的字符串。对于字符串中的每一个位置，你需要计算出在它左边的所有字符中，有多少个跟它不同的字符。

考点分析

线性扫描 / 前缀计数。这道题本质上是考察一次遍历解决问题的能力，是一道比较基础的“送分题”，关键在于快速准确地理解题意。

样例输入与输出

0 0 2 1
0 1 1 2 2

解题思路

这道题的思路非常直接，我们只需要从左到右遍历一次字符串即可。

设置计数器：我们需要两个计数器，zeros_count 用来统计到目前为止遇到的 '0' 的数量，ones_count 用来统计 '1' 的数量。
遍历字符串：当我们遍历到第 i 个字符 s[i] 时：
- 如果 s[i] 是 '0'，那么在它左边和它不同的字符就是 '1'。所以，当前位置的答案就是 ones_count。
- 如果 s[i] 是 '1'，同理，在它左边和它不同的字符就是 '0'。所以，当前位置的答案就是 zeros_count。
记录并更新：将计算出的答案存入结果列表后，不要忘记更新我们对应的计数器。如果当前是 '0'，则 zeros_count 加一；如果是 '1'，则 ones_count 加一。
循环往复：重复这个过程直到遍历完整个字符串，最后输出结果列表。

这种方法的时间复杂度是 O(n)，空间复杂度是 O(n)（用于存储结果），完全满足题目要求。

AC代码 (Python)

Python

import sys

def solve():
    """
    处理单组测试数据的函数
    """
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().strip()
    
    # 两个计数器，分别统计已遍历过的0和1的数量
    zeros_count = 0
    ones_count = 0
    
    results = []
    
    for char in s:
        if char == '0':
            # 当前是'0'，左侧与它不同的就是'1'的数量
            results.append(ones_count)
            # 更新'0'的计数
            zeros_count += 1
        else: # char == '1'
            # 当前是'1'，左侧与它不同的就是'0'的数量
            results.append(zeros_count)
            # 更新'1'的计数
            ones_count += 1
            
    print(' '.join(map(str, results)))

# 读取测试用例的数量
T = int(sys.stdin.readline())
for _ in range(T):
    solve()

第二题：

题目大意

我们需要构造一个 ntimesm 的矩阵，矩阵中填充非零整数。要求是：矩阵中任意一个 2times2 子矩阵的元素之和，必须等于整个 ntimesm 矩阵所有元素的总和。题目保证 ntimesm 是偶数。

考点分析

构造题、数学思维。这类题目的关键是找到一个满足条件的通用模式。题目的约束“任意”和“全局”相等，是一个非常强的暗示，引导我们去思考如何让这些和都等于一个恒定的值，比如0。

样例输入与输出

2
2 2
3 4

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

解题思路

这是一个非常巧妙的构造题，直接给出结论会觉得很神奇，但分析一下就豁然开朗了。

核心突破口：要让任意 2times2 子矩阵和等于全局和，最简单的实现方式就是让所有这些和都为0。
构造 2times2 矩阵：我们先看一个 2times2 的情况，如何让四个数的和为0？最简单的就是 [[1, -1], [-1, 1]]，两个1，两个-1，和为0。
推广到 ntimesm：这个思想可以推广到任意大小的矩阵。我们使用经典的棋盘染色法。
- 根据每个元素坐标 (i, j)（从1开始计数）的奇偶性来填充数值。
- 如果 i + j 的和是偶数，我们就在该位置填 1。
- 如果 i + j 的和是奇数，我们就在该位置填 -1。
正确性验证：
- 局部验证 (2x2子矩阵)：任意一个 2times2 的子矩阵，其四个格子的坐标分别是 (i, j), (i, j+1), (i+1, j), (i+1, j+1)。它们的 行号+列号 的和的奇偶性一定是两奇两偶（例如，偶, 奇, 奇, 偶），所以这四个格子必定是两个 1 和两个 -1，和恒为0。
- 全局验证 (n x m矩阵)：因为题目保证了 ntimesm 是偶数，这意味着整个矩阵中 i+j 为偶数的位置和为奇数的位置数量相等。因此，整个矩阵中 1 和 -1 的数量完全相同，总和也为0。
- 这样一来，局部和为0，全局和也为0，完美满足题目要求。

AC代码 (Python)

Python

import sys

def solve():
    """
    处理单组测试数据的函数
    """
    n, m = map(int, sys.stdin.readline().split())
    
    matrix = []
    # 遍历每一行
    for i in range(1, n + 1):
        row = []
        # 遍历每一列
        for j in range(1, m + 1):
            # 核心构造逻辑：棋盘染色
            if (i + j) % 2 == 0:
                row.append(1)
            else:
                row.append(-1)
        matrix.append(' '.join(map(str, row)))
    
    print('\n'.join(matrix))

# 读取测试用例的数量
T = int(sys.stdin.readline())
for _ in range(T):
    solve()

第三题：

题目大意

给一个正整数 n（可能很大，以字符串形式处理），问最少修改其中几位数字，可以使得新数字被 495 整除。同时要输出修改后的数字，且不能有前导零。

考点分析

动态规划（特别是数位DP）、模运算、路径记录。这是数位DP的经典应用场景。由于数字很大，我们不能直接枚举，必须按位进行决策。状态的设计是解决本题的重中之重。

样例输入与输出

1
495

解题思路

这是一个典型的数位DP问题，我们需要从高位到低位逐位确定修改后的数字。

定义DP状态：这是最关键的一步。我们定义 dp[i][j] 表示：当我们处理完原数字的前 i 位，构造出的新数字在模 495 意义下的余数为 j 时，所需要的最少修改次数。
状态转移：dp[i][j] 的值可以从 dp[i-1][k] 推导出来。我们枚举第 i 位可以填的数字 d（从 0 到 9）。
- 假设前 i-1 位构造出的数字模 495 的余数是 k，那么在前 i-1 位的数字后面添上一个 d，得到的新数字模 495 的余数就是 new_rem = (k * 10 + d) % 495。
- 此次转移的代价（cost）等于前 i-1 位的最小代价 dp[i-1][k]，再加上当前位的修改代价。如果 d 和原数字的第 i 位 s[i-1] 不同，则修改代价为1，否则为0。
- 所以转移方程为：dp[i][new_rem] = min(dp[i][new_rem], dp[i-1][k] + cost)。
记录路径：为了最终能输出修改后的数字，我们光有 dp 表还不够。还需要一个 path 或者 prev_digit 之类的二维数组来记录最优决策。例如，path_digit[i][j] 记录的是当 dp[i][j] 取到最小值时，第 i 位所填的数字是什么。同时，我们还需要 path_prev_rem[i][j] 来记录它是从前一个状态的哪个余数转移过来的，以便回溯。
初始化和边界条件：
- dp 数组全部初始化为一个极大值（代表不可达）。
- dp[0][0] = 0，表示一个空数字（前0位），余数为0，修改次数为0。
- 踩坑点：处理第一位时，枚举的数字 d 不能为 0，以防止前导零。
回溯构造答案：
- 最终的最小修改次数就是 dp[L][0]（L为数字长度），因为它表示处理完所有位，且最终余数为0的最小代价。
- 从 dp[L][0] 开始，利用我们记录的路径信息，从后往前一步步反推出每一位应该填什么数字，最终拼接成完整的答案。

AC代码 (Python)

Python

import sys

def solve():
    s = sys.stdin.readline().strip()
    length = len(s)
    mod = 495
    inf = float('inf')
    
    # dp[i][r]: 处理前i位，余数为r的最小修改次数
    dp_costs = [[inf] * mod for _ in range(length + 1)]
    
    # path_digit[i][r]: 达到dp[i][r]状态时，第i位选择的数字
    path_digit = [[-1] * mod for _ in range(length + 1)]
    
    # path_prev_rem[i][r]: 达到dp[i][r]状态时，前一个状态(i-1)的余数
    path_prev_rem = [[-1] * mod for _ in range(length + 1)]
    
    # 初始化：处理0位，余数为0，代价是0
    dp_costs[0][0] = 0
    
    # 按位进行DP
    for i in range(1, length + 1):
        original_digit = int(s[i-1])
        # 遍历前一个状态的所有可能余数
        for prev_rem in range(mod):
            if dp_costs[i-1][prev_rem] == inf:
                continue
            
            # 遍历当前位所有可能的数字d
            for d in range(10):
                # 关键：第一位不能是0
                if i == 1 and d == 0:
                    continue
                
                # 计算新余数
                new_rem = (prev_rem * 10 + d) % mod
                # 计算修改成本
                cost = dp_costs[i-1][prev_rem] + (1 if d != original_digit else 0)
                
                # 如果找到了更优的解，则更新
                if cost < dp_costs[i][new_rem]:
                    dp_costs[i][new_rem] = cost
                    path_digit[i][new_rem] = d
                    path_prev_rem[i][new_rem] = prev_rem

    # --- 结果回溯 ---
    min_modifications = dp_costs[length][0]
    print(min_modifications)
    
    result_chars = [''] * length
    current_rem = 0
    # 从最后一位开始往前推
    for i in range(length, 0, -1):
        digit = path_digit[i][current_rem]
        result_chars[i-1] = str(digit)
        # 找到上一个状态的余数，进行回溯
        current_rem = path_prev_rem[i][current_rem]
        
    print(''.join(result_chars))

solve()

#科大讯飞##笔试##秋招#

互联网复盘刷题集合文章被收录于专栏

互联网复盘刷题集合