大厂真题 / 百度

百度 2026-7-30 笔试真题 - 算法岗

本场考试概述

考试时间：2026年7月30日

考试岗位：算法岗

难度评级：中等

考点分析：

• 第一题：括号深度与线性扫描（难度简单）
• 第二题：前缀余数与双指针（难度中等）
• 第三题：乘积贪心、二分答案与快速幂（难度中等偏难）

建议策略：

• 第一题不要逐轮删除括号；先求整串最大深度，再把每个字符的深度直接换算成消失轮次。
• 第二题的关键是消去与起点有关的常数，把“轨迹余数互异”转化为前缀余数窗口内无重复。
• 第三题先证明每次递减当前最大值的乘积损失最小，再二分最终被削平的水平线，避免按操作次数模拟。

第 1 题：消失的括号层

题目描述

给定一个长度为 $n$ 的合法括号串 $s$。括号串按轮次逐渐消失：每一轮中，当前串里深度最大的所有括号对同时删除；剩余字符保持原有相对顺序，并继续下一轮。

一个括号对的深度，等于包围它的括号对数量再加 $1$。请对原串中的每个字符，输出该字符在第几轮消失。同一对左右括号的答案相同。

输入包含 $T$ 组测试数据，其中 $1\le T\le 10^4$。每组先给出括号串长度 $n$，满足 $2\le n\le 2\times 10^5$；再给出长度为 $n$、仅由 ( 和 ) 构成的合法括号串。保证 $n$ 为偶数，且单个测试文件中所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

样例

输入

3
6
(()())
6
((()))
10
(()((())))

输出

2 1 1 1 1 2
3 2 1 1 2 3
4 3 3 3 2 1 1 2 3 4

第一组 (()()) 的两个内层括号对在第 $1$ 轮同时删除，最外层括号对随后在第 $2$ 轮删除。

思路分析

第一步：一次扫描求每个字符的原始深度

扫描括号串并维护当前深度 current_depth：

• 遇到左括号时，先令深度加 $1$，再记录该字符深度；
• 遇到右括号时，先记录当前深度，再令深度减 $1$。

这样一对匹配括号会记录到同一个深度。扫描过程中同时求出整串最大深度 $D$。

用公式表示，第 $i$ 个字符的深度为

第二步：理解删除一层后的变化

第一轮删除所有深度为 $D$ 的括号对。删除它们不会改变更浅括号对之间的包含关系：一个深度较小的括号对只被它外侧的括号包围，而删除的是它内侧、更深的括号。

只要仍有括号存在，深度大于 $1$ 的括号对必然被上一层括号包围。因此删除当前最深层后，最大深度恰好从 $D$ 降为 $D-1$，不会跨过某一层。

第三步：把深度直接换成轮次

深度为 $D$ 的字符第 $1$ 轮消失；深度为 $D-1$ 的字符第 $2$ 轮消失。一般地，深度为 $d$ 的字符消失轮次为

因此无需真正执行任何一轮删除。求完深度后，再线性换算答案即可。

题解代码

import sys
input = sys.stdin.readline


def vanish_rounds(brackets):
    depths = []
    current_depth = 0
    max_depth = 0

    for char in brackets:
        if char == '(':
            current_depth += 1
            depth = current_depth
        else:
            depth = current_depth
            current_depth -= 1

        depths.append(depth)
        max_depth = max(max_depth, depth)

    return [max_depth - depth + 1 for depth in depths]


def solve():
    test_count = int(input())
    output = []

    for _ in range(test_count):
        n = int(input())
        brackets = input().strip()
        answer = vanish_rounds(brackets[:n])
        output.append(' '.join(map(str, answer)))

    print('\n'.join(output))


solve()

复杂度分析

设当前测试的括号串长度为 $n$。

时间复杂度：$O(n)$，扫描求深度和换算轮次各进行一次。

空间复杂度：$O(n)$，用于保存每个字符的深度和答案。

第 2 题：余数游走

题目描述

给定长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$ 和正整数模数 $M$。序列首尾相接，视为一个环。

对于起点 $s$，从 $a_s$ 开始沿环依次取数，最多取 $n$ 个。走出第 $t$ 步后的余数轨迹值定义为

余数采用标准非负表示，落在 $[0,M-1]$。轨迹不包含尚未取元素时的初始余数 $0$。

只要下一步得到的余数与轨迹中已有余数重复，游走就停止；若一直没有重复，则取满 $n$ 步后停止。记从起点 $s$ 出发能取到的最大步数为 $L_s$，求

输入包含 $T$ 组测试数据，其中 $1\le T\le 10^5$。每组输入满足 $1\le n,M\le 2\times 10^5$，随后给出 $n$ 个整数，且 $-10^9\le a_i\le 10^9$。保证所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

样例

输入

2
5 3
1 2 2 1 2
4 5
5 0 5 0

输出

11
4

第二组的每个元素对 $5$ 都等价于 $0$。任一起点走第一步得到余数 $0$，第二步仍得到 $0$，所以每个起点的游走长度都是 $1$，总和为 $4$。

思路分析

第一步：破环成链

把数组在逻辑上复制一遍。由于起点只有 $n$ 个，且每个起点最多走 $n$ 步，只需处理覆盖所有这些环形区间的 $2n-1$ 个元素。

定义前缀余数

代码计算 $P_0,P_1,\ldots,P_{2n-1}$。

第二步：消去起点带来的常数

若从位置 $s$ 出发，走 $t$ 步后的轨迹值为

对于固定起点 $s$，每个轨迹值都减去了同一个常数 $P_{s-1}$。因此两个步数的轨迹值相等，当且仅当对应的前缀余数相等：

也就是说，从起点 $s$ 出发走 $L$ 步合法，等价于

两两不同。于是

原问题由“环上每个起点的余数轨迹”转化为“前缀余数数组中，每个左端点开始的最长无重复窗口”。

第三步：双指针维护最长无重复窗口

对每个起点 $s=0,1,\ldots,n-1$，窗口左端对应 $s+1$。维护右端指针 right 和集合 seen：

1. 只要窗口长度尚未达到 $n$，且下一个前缀余数不在集合中，就把右端向右扩展；
2. 当前窗口长度就是该起点的 $L_i$，累加到答案；
3. 左端右移前，从集合中删除离开的前缀余数。

当左端右移时，窗口只会少一个元素，原有右端仍然合法，所以右端不需要回退。每个前缀余数最多入窗、出窗各一次。

第四步：累加窗口长度

当前窗口长度 right - left + 1 就是对应起点的 $L_s$。累加后删除左端余数，再处理下一个起点。答案最大可达 $n^2=4\times10^{10}$，在固定宽度语言中必须使用 64 位整数保存。本文代码使用哈希集合维护窗口，空间不超过 $O(n)$。

题解代码

import sys
input = sys.stdin.readline


def total_walk_length(n, modulus, values):
    prefix = [0] * (2 * n)
    current = 0

    for i in range(1, 2 * n):
        current = (current + values[(i - 1) % n]) % modulus
        prefix[i] = current

    seen = set()
    right = 0
    total = 0

    for left in range(1, n + 1):
        limit = left + n - 1

        while right < limit and prefix[right + 1] not in seen:
            right += 1
            seen.add(prefix[right])

        total += right - left + 1
        seen.remove(prefix[left])

    return total


def solve():
    test_count = int(input())
    output = []

    for _ in range(test_count):
        n, modulus = map(int, input().split())
        values = list(map(int, input().split()))
        output.append(str(total_walk_length(n, modulus, values)))

    print('\n'.join(output))


solve()

复杂度分析

设当前测试的序列长度为 $n$。

时间复杂度：期望 $O(n)$。前缀余数计算为 $O(n)$；双指针中每个位置至多进入和离开集合各一次。哈希集合单次操作的期望复杂度为 $O(1)$。

空间复杂度：$O(n)$，用于前缀余数数组和至多包含 $n$ 个元素的集合。

第 3 题：最大乘积操作

题目描述

给定长度为 $n$ 的正整数序列 $a$ 和操作次数 $k$。每次操作选择一个当前值大于 $1$ 的元素，将它减 $1$。如果所有元素都已经等于 $1$，则无法继续操作并提前停止，即使仍有剩余操作次数。

在上述规则下，使最终序列的乘积

尽可能大，并输出最大乘积对 $10^9+7$ 取模的结果。

输入包含 $T$ 组测试数据，其中 $1\le T\le 10^5$。每组满足 $1\le n\le 2\times10^5$、$0\le k\le10^{18}$，随后给出 $n$ 个正整数，满足 $1\le a_i\le10^9$。保证所有测试中 $n$ 的总和不超过 $4\times10^5$。

样例

输入

3
3 3
2 2 3
4 2
5 1 3 2
1 100
10

输出

2
18
1

第一组可依次把当前最大元素减小，最终得到 [1, 1, 2]，乘积为 $2$。第三组把唯一元素从 $10$ 减到 $1$ 后无法继续，答案为 $1$。

思路分析

第一步：一次操作应该减哪个元素

假设当前乘积为 $P$，选择值为 $v>1$ 的元素递减后，新乘积相当于乘上

$v$ 越大，这一比例越大，乘积损失越小。因此每次操作都应选择当前最大的元素。若有多个最大元素，选择其中任意一个都等价。

这一结论也可通过交换论证理解：如果某一步减了较小值 $x$，却保留了更大的值 $y$，把这一步改为减 $y$，其乘积保留比例不会更差。

第二步：最终序列一定呈“削平”形态

持续递减当前最大值，会把所有冒尖元素逐渐压到同一水平附近。于是可以先选择整数水平线 $x$，把所有大于 $x$ 的元素削到 $x$。削平后的中间状态为

达到水平线 $x$ 所需操作数为

$x$ 越低，cost(x) 越大。因此“cost(x) <= k”具有单调性，可以二分找到操作次数能够达到的最低水平线 $x$。

第三步：快速计算削平代价

先将数组升序排序，并计算前缀和。对给定 $x$，用二分查找定位第一个大于 $x$ 的元素。若其下标为 $j$，则

这样每次检查只需一次二分查找，不必扫描整个数组。

第四步：分配削平后的剩余操作

令 $x$ 为最低可达到的水平线，并设

把所有原值不小于 $x$ 的元素压到 $x$ 后，还剩 $r$ 次操作。由于 $x$ 已经是最低可行水平线，若把所有这些 $x$ 都再减一次就会达到更低水平线 $x-1$，与最低性的定义矛盾。因此 $r$ 小于削平后等于 $x$ 的元素个数。

剩余操作应分别落在 $r$ 个值为 $x$ 的元素上，把它们变成 $x-1$；其余仍为 $x$。原本小于 $x$ 的元素不变。最终乘积可分成三部分：

1. 原值小于 $x$ 的元素之积；
2. 若干个 $x$ 的幂；
3. $r$ 个 $x-1$ 的幂。

若削平后等于 $x$ 的元素个数为 $c$，最终乘积为

用 Python 内置三参数 pow 完成快速幂取模。

第五步：处理所有元素都能减到 1 的情况

把所有元素减到 $1$ 最多能执行

次。若 $k$ 不小于这个值，操作会因所有元素均为 $1$ 而提前停止，最终乘积直接为 $1$。这个分支也避免后续出现水平线以下的无效计算。

题解代码

import sys
from bisect import bisect_left, bisect_right

input = sys.stdin.readline
MOD = 10 ** 9 + 7


def max_product(values, operation_count):
    values.sort()
    n = len(values)

    prefix_sum = [0] * (n + 1)
    for i, value in enumerate(values):
        prefix_sum[i + 1] = prefix_sum[i] + value

    if operation_count >= prefix_sum[n] - n:
        return 1

    def cost_to_level(level):
        first_greater = bisect_right(values, level)
        high_sum = prefix_sum[n] - prefix_sum[first_greater]
        high_count = n - first_greater
        return high_sum - level * high_count

    low, high = 1, values[-1]
    while low < high:
        middle = (low + high) // 2
        if cost_to_level(middle) <= operation_count:
            high = middle
        else:
            low = middle + 1

    level = low
    remaining = operation_count - cost_to_level(level)

    first_level = bisect_left(values, level)
    level_count = n - first_level

    result = 1
    for value in values[:first_level]:
        result = result * value % MOD

    result = result * pow(level, level_count - remaining, MOD) % MOD
    result = result * pow(level - 1, remaining, MOD) % MOD
    return result


def solve():
    test_count = int(input())
    output = []

    for _ in range(test_count):
        n, operation_count = map(int, input().split())
        values = list(map(int, input().split()))
        output.append(str(max_product(values[:n], operation_count)))

    print('\n'.join(output))


solve()

复杂度分析

设当前测试的序列长度为 $n$，最大元素为 $V$。

时间复杂度：排序为 $O(n\log n)$；二分水平线进行 $O(\log V)$ 次检查，每次用二分查找计算代价，耗时 $O(\log n)$；最后计算未改变部分的乘积为 $O(n)$。总时间复杂度为 $O(n\log n+\log V\log n)$。

空间复杂度：$O(n)$，用于排序后的数组和前缀和。

小结

• 第一题中，删除最深层后剩余括号的包含关系不变，最大深度每轮恰好减 $1$，所以答案可由原始深度直接换算。
• 第二题把轨迹余数写成两个前缀余数之差，消去固定起点对应的常数后，就得到最长无重复窗口问题，可用双指针在线性期望时间内解决。
• 第三题利用“递减越大的元素，乘积相对损失越小”的贪心性质，把最终状态描述成削平后的序列；二分水平线并用前缀和求代价，即可处理很大的操作次数。