大厂真题 / 科大讯飞

科大讯飞 4.11 笔试真题

本场考试概述

考试时间：2026年4月11日 考试岗位：通用岗 难度评级：中等

考点分析：

第一题：贪心 + 奇偶性分析（难度简单）
第二题：贪心（难度简单）
第三题：快速幂 + 乘法逆元（难度困难）

建议策略：

前两题纯贪心，逻辑简单，争取满分
第三题是硬核数学题，需要掌握快速幂和费马小定理

第一题：大写字母最大化

题目描述

给定一个仅由大小写字母构成的长度为 n 的字符串，每次操作可以将一个字符在大小写之间切换。恰好 k 次操作后，使大写字母数量尽可能多。

样例

输入

5 3
arBrg

输出

思路分析

第一步：贪心策略

优先把小写转大写，每次消耗一次操作。设小写字母个数为 lower。

第二步：分类讨论

若 k <= lower，操作次数不足以把所有小写都转大写，答案为 upper + k。若 k > lower，先把所有小写转大写用掉 lower 次，剩余 k - lower 次在同一字符上来回切换。剩余次数为偶数时全部大写（答案 n）；为奇数时牺牲一个字符（答案 n-1）。

题解代码

def solve(n, k, s):
    lower = sum(1 for c in s if c.islower())
    upper = n - lower
    if k <= lower:
        return upper + k
    remain = k - lower
    return n if remain % 2 == 0 else n - 1

n, k = map(int, input().split())
s = input()
print(solve(n, k, s))

复杂度分析

时间复杂度：O(n)，遍历字符串统计小写字母个数。 空间复杂度：O(1)。

第二题：最小区间长度

题目描述

给定一个长度为 n 的非严格递增数组，可以至多进行一次操作：选择区间 [l, r]，对区间内第 i 个元素加 m*(r-l+1-i)（越靠左加得越多）。为了使操作后数组存在非递增相邻对，需要选择的区间长度最小值是多少？无法满足则输出 -1。

样例

输入

输出

1
-1

思路分析

第一步：分析操作效果

区间内相邻元素 a[i], a[i+1] 操作后差变为 a[i+1]-a[i]-m。要使某对相邻元素非递增（差 < 0），需要 a[i+1]-a[i] < m。

第二步：贪心判断

这个条件与区间长度无关，只取决于原始相邻差。只要存在某对相邻元素差值严格小于 m，选长度为 1 的区间即可破坏非递减性；否则无论选多大的区间都无法破坏，输出 -1。

题解代码

import sys
input = sys.stdin.readline

def solve(n, m, a):
    for i in range(n - 1):
        if a[i + 1] - a[i] < m:
            return 1
    return -1

T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve(n, m, a))

复杂度分析

时间复杂度：O(n)，单次遍历数组。 空间复杂度：O(n)，存储数组。

第三题：网格反置

题目描述

有一个 n 行 m 列的网格，初始所有单元格为 0。进行 k 次操作，每次反置某一行或某一列（0 变 1，1 变 0）。所有操作结束后，将网格按行优先顺序拼接为一个二进制数，输出其十进制值对 10^9+7 取模的结果。

样例

输入

输出

13218195

思路分析

第一步：观察题目性质

网格最大有 10^18 个格子，逐格模拟不可能。但操作最多 10^5 次，实际被翻转过的行列数很少。翻转一个格子两次等于没翻，因此格子最终是 0 还是 1 只取决于它所在的行和列各被翻转了奇数次还是偶数次。

第二步：行列分离

统计每行每列被翻转的次数，翻转奇数次的标记为”翻转”。对于”翻转行”，非翻转列的位置为 1；对于”非翻转行”，翻转列的位置为 1。

第三步：等比数列求和 + 快速幂

每行在总数中的权重因子为 2^((n-i)*m)，将所有翻转行的权重因子加起来记为 A，非翻转行权重因子总和为 B = total - A。所有行的权重因子总和是公比为 2^m 的等比数列，用求和公式配合费马小定理求模逆元计算。

题解代码

MOD = 10**9 + 7

def solve(n, m, k, ops):
    row_flip = {}
    col_flip = {}
    for x, y in ops:
        if x == 1:
            col_flip[y] = col_flip.get(y, 0) + 1
        else:
            row_flip[y] = row_flip.get(y, 0) + 1

    # 翻转列的位权之和
    S_C = 0
    for j, cnt in col_flip.items():
        if cnt % 2 == 1:
            S_C = (S_C + pow(2, m - j, MOD)) % MOD

    # 翻转行的行权重因子之和
    A = 0
    for i, cnt in row_flip.items():
        if cnt % 2 == 1:
            A = (A + pow(2, (n - i) * m, MOD)) % MOD

    S_all = (pow(2, m, MOD) - 1) % MOD
    S_notC = (S_all - S_C) % MOD

    # 等比数列求和
    pow2m = pow(2, m, MOD)
    if pow2m == 1:
        total_pow = n % MOD
    else:
        total_pow = (pow(2, n * m, MOD) - 1) * pow(pow2m - 1, MOD - 2, MOD) % MOD

    B = (total_pow - A) % MOD
    return (S_notC * A + S_C * B) % MOD

n, m, k = map(int, input().split())
ops = []
for _ in range(k):
    x, y = map(int, input().split())
    ops.append((x, y))
print(solve(n, m, k, ops))

复杂度分析

时间复杂度：O(k log(nm))，遍历 k 次操作后对至多 k 个行/列各做一次快速幂。 空间复杂度：O(k)，哈希表存储行列翻转次数。

小结

第一题贪心 + 奇偶性，优先把小写转大写，多余操作看剩余次数奇偶
第二题贪心，操作对相邻差的净效果为减 m，只要存在原始差 < m 即可用长度 1 的区间破坏
第三题快速幂 + 乘法逆元是本场难点，核心是行列翻转独立性和等比数列求和的模运算处理

这篇文章有帮助吗？

| GitHub 留言