夜雨聆风写在前面
本次给大家带来2026年7月30日百度算法岗笔试题的3道题，本场机考题目均可在咱们平台上在线刷题。
第一题：扫描括号串记录每个字符所在括号对的深度和全局最大深度，该字符的消失轮次就是“最大深度减当前深度再加”；
第二题：将环形序列复制一遍并计算前缀和余数，把每个起点的轨迹互异转化为前缀余数数组上的最长无重复连续区间，再用滑动窗口一次统计所有起点的答案。
第三题：每次优先减当前最大元素，并通过排序后批量“削平”较大的数，使操作后的各元素尽可能接近，从而让乘积最大；
塔子哥的配套网codefun2000.com
第1题-括号串逐层消除
题目内容
得到一个合法括号串 。接下来这个括号串会按轮次逐渐消失。
在每一轮中，当前括号串里所有深度最大的括号对会同时消失。消失后，剩余括号保持原来的相对顺序，形成新的括号串，继续下一轮。
这里括号对的深度定义为它被多少层括号包含再加 。例如，字符串 "((())())" 中最外层括号深度为 ，里面两对括号深度为 。
请你对原字符串中的每一个字符，输出它会在第几轮消失。
合法括号串：一个括号串被称为合法的括号串，当且仅当：
空串是合法的括号； 如果 是合法的括号串，那么 (A)也是合法的括号串；如果 和 都是合法的括号串，那么 也是合法的括号串。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：
第一行输入一个整数 ，表示括号串长度。 第二行输入一个长度为 的合法括号串 ，仅由 (和)组成。
保证 为偶数，且单个测试文件中 之和不超过 。
输出描述
对于每一组测试数据，新起一行输出 个整数，第 个整数表示原字符串中第 个字符会在第几轮消失。
样例1
输入
36(()())6((()))10(()((())))输出
2 1 1 1 1 23 2 1 1 2 34 3 3 3 2 1 1 2 3 4题解
解题思路
将每一对括号看成一个节点，括号的嵌套关系形成若干棵树。
设原括号串的最大深度为：
第轮删除深度为的括号对。 第轮删除深度为的括号对。 依次类推。
因此，原来深度为的括号对会在第
轮消失。
使用线性扫描统计每个字符所属括号对的深度：
遇到 (时，当前深度加，该字符的深度就是当前深度。遇到 )时，该字符的深度等于当前深度，随后当前深度减。扫描过程中记录最大深度。 最后令每个位置的答案为。
该方法使用括号栈的深度统计思想，但不需要真正维护栈。
复杂度分析
对于每组数据：
时间复杂度：。 空间复杂度：。
代码实现
python代码(C++和JAVA代码见在线OJ网址)
import sys# 计算每个字符消失的轮次defget_rounds(s): n = len(s) depth = [0] * n current_depth = 0 max_depth = 0# 统计每个字符所属括号对的深度for i in range(n):if s[i] == '(': current_depth += 1 depth[i] = current_depth max_depth = max(max_depth, current_depth)else: depth[i] = current_depth current_depth -= 1# 根据最大深度计算消失轮次for i in range(n): depth[i] = max_depth - depth[i] + 1return depthdefmain(): data = sys.stdin.read().split() t = int(data[0]) index = 1 output = []for _ in range(t): n = int(data[index]) s = data[index + 1] index += 2 answer = get_rounds(s) output.append(' '.join(map(str, answer))) print('\n'.join(output))if __name__ == '__main__': main()第2题-余数游走
题目内容
给定一个长度为 的整数序列 ，视为环状序列（位置 的后继为位置 ）。给定正整数 ，对于每个起点 ，进行如下“游走”并定义余数轨迹：
从位置 开始，依次取 ，当走到 后继续从 开始，形成一个最多包含 个元素的连续环段。 第 步的余数轨迹值定义为
其中取模为标准余数，落在区间 。
要求轨迹互异：在允许的最大步数 内， 两两不同；若再取一步会导致出现已出现过的余数值，则停止；若已取满 步也停止。轨迹只包含 的 ，不包含初始 。
定义起点 的游走长度 为以上规则下可达到的最大步数。请计算所有起点的游走长度之和 。
输入描述
每个测试文件包含多组测试数据。第一行输入一个整数 表示测试组数，每组测试数据描述如下：
第一行输入两个整数 。 第二行输入 个整数 。
保证所有测试数据的 之和不超过 。
输出描述
对于每组测试数据，输出一行一个整数，表示该组数据的 。
样例1
输入
25 31 2 2 1 24 55 0 5 0输出
114题解
解题思路
使用前缀和与双指针滑动窗口。
将原序列复制一遍，得到长度至少为 的序列。定义前缀余数：
对于起点 ，第 步的轨迹值为：
对于任意两个步数 和 ：
当且仅当：
因为两边同时减去了相同的 。
因此，起点 的游走长度 ，等于序列：
从左端开始的最长无重复前缀长度。
使用双指针维护一个无重复窗口 ：
集合中保存 。 对于每个 ，不断向右扩展 。 扩展时要求 ，保证游走长度不超过 。 如果下一个前缀余数已经存在于集合中，则不能继续扩展。 此时：
统计答案后，将 从集合中删除，再处理下一个起点。
双指针中的 始终单调向右移动，因此所有位置只会加入和删除集合常数次。
答案最大可能达到 ，需要使用 位整数保存。
复杂度分析
对于每组测试数据：
构造双倍前缀余数的时间复杂度为 。 双指针扫描的时间复杂度为 。 总时间复杂度为 。 前缀数组和集合的空间复杂度为 。
由于所有测试数据的 之和不超过 ，该复杂度可以通过。
代码实现
python代码(C++和JAVA代码见在线OJ网址)
import sysdefsolve_case(n, m, a):# prefix[i] 表示双倍序列前 i 个数之和对 m 取模 prefix = [0] * (2 * n)# 实际只需要计算到下标 2n-1for i in range(1, 2 * n): prefix[i] = (prefix[i - 1] + a[(i - 1) % n]) % m seen = set() right = 0 answer = 0# 枚举每一个起点for left in range(1, n + 1): limit = left + n - 1# 保证窗口内余数互不相同，并且长度不超过 nwhile right + 1 <= limit and prefix[right + 1] notin seen: right += 1 seen.add(prefix[right])# 当前窗口长度就是该起点的游走长度 answer += right - left + 1# 左端点右移，删除离开窗口的余数if left <= right: seen.remove(prefix[left])return answerdefmain(): data = list(map(int, sys.stdin.buffer.read().split())) index = 0 t = data[index] index += 1 result = []for _ in range(t): n = data[index] m = data[index + 1] index += 2 a = data[index:index + n] index += n result.append(str(solve_case(n, m, a))) sys.stdout.write("\n".join(result))if __name__ == "__main__": main()第3题-最大乘积操作
题目内容
给定一个长度为 的正整数序列。你必须进行 次操作（若所有元素均为 时则无法继续，提前停止，即使你还有剩余操作次数。）：每次选择一个满足 的下标，将 减一（）。
在上述前提下，最终序列的乘积 尽可能大。输出该最大乘积对 取模的结果。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：
第一行输入两个整数； 第二行输入 个整数，表示序列。
保证所有测试中 的总和不超过。
输出描述
对于每组数据，输出一个整数，操作后可以得到的序列最大乘积对 取模后的结果。
样例1
输入
33 32 2 34 25 1 3 21 10010输出
2181题解
解题思路
采用贪心算法与排序。
假设当前有两个可操作的数，满足 ：
将 减一，乘积变为原来的 ； 将 减一，乘积变为原来的 。
由于 ，所以每次将当前最大的数减一，乘积损失最小。
因此，最优策略是不断降低最大的元素，使较大的若干元素逐渐相等。直接执行 次可能超时，可以排序后批量处理：
将数组从小到大排序。
从最大值开始，维护当前被一起降低的元素数量 和它们的值 。
将这 个元素全部降低到下一个较小值，需要的操作次数为：
若剩余操作次数足够，则整体降低并扩大处理范围。
否则，设：
最终有 个元素等于 ，有 个元素等于 。
若 ，所有元素最终都会变成 ，答案为 。
乘积使用模快速幂计算，并对 取模。
复杂度分析
每组数据需要排序，时间复杂度为 。
计算最终乘积需要 ，因此总时间复杂度为 。
排序数组需要 的空间，空间复杂度为 。
代码实现
python代码(C++和JAVA代码见在线OJ网址)
import sysMOD = 1000000007defmax_product(a, k):"""计算执行操作后的最大乘积""" a.sort() n = len(a)# 所有元素最多能够减少的总次数 total = sum(x - 1for x in a)if k >= total:return1 level = a[-1] cnt = 1# 从大到小批量降低较大的元素for i in range(n - 2, -1, -1): cost = (level - a[i]) * cntif k >= cost: k -= cost level = a[i] cnt += 1else: q, r = divmod(k, cnt) high = level - q ans = 1# 前面的元素保持不变for j in range(i + 1): ans = ans * a[j] % MOD# 当前最大的 cnt 个元素只相差一 ans = ans * pow(high, cnt - r, MOD) % MOD ans = ans * pow(high - 1, r, MOD) % MODreturn ans# 所有元素已经被降低到相同值 q, r = divmod(k, n) high = level - q ans = pow(high, n - r, MOD) ans = ans * pow(high - 1, r, MOD) % MODreturn ansdefmain(): data = list(map(int, sys.stdin.buffer.read().split())) pos = 0 T = data[pos] pos += 1 answers = []for _ in range(T): n = data[pos] k = data[pos + 1] pos += 2 a = data[pos:pos + n] pos += n answers.append(str(max_product(a, k))) print("\n".join(answers))if __name__ == "__main__": main()
