大厂真题 / 百度
百度 2026-7-23 笔试真题 - 算法岗
本场考试概述
考试时间：2026年7月23日
考试岗位：算法岗
难度评级：中等偏难
考点分析：
- 第一题：相邻翻转与被迫决策贪心（难度简单）
- 第二题：前缀最值与线性动态规划（难度中等）
- 第三题：质数筛、动态颜色维护与增量路径（难度困难）
建议策略：
- 第一题从左向右消除已经无法由后续开关修正的灯，决策是唯一的
- 第二题先抓住“剩余藤蔓始终是一个前缀”，再把操作写成前缀长度之间的转移
- 第三题先证明相邻两人的路径只有最后至多两步需要重算，再考虑如何查询右侧最近的目标颜色
原始公开题解中的部分公式和数据范围以 SVG 呈现，转换后未完整保留。本文不猜测缺失的数值约束，只保留能够从题意、样例与代码中确认的内容。
第 1 题：开关控制灯
题目描述
有 $n$ 盏灯和 $n$ 个开关，均从 $1$ 到 $n$ 编号。对于 $1 \le i < n$，按下开关 $i$ 会同时翻转灯 $i$ 和灯 $i+1$；开关 $n$ 只翻转灯 $n$。翻转表示亮变灭、灭变亮。
给定每盏灯的初始状态，$1$ 表示亮，$0$ 表示灭。求使所有灯熄灭所需的最少按键次数。
输入包含多组测试。每组先输入灯数 $n$，再输入 $n$ 个初始状态。
样例
输入
2
5
1 1 0 1 1
3
1 1 1
输出
2
2
第二组可以按下开关 $1$ 和开关 $3$：第一次把前两盏灯变为 0 0，第二次熄灭最后一盏灯。
思路分析
第一步：观察一盏灯由哪些开关控制
灯 $i$ 只会被开关 $i-1$ 和开关 $i$ 影响。按从左到右的顺序处理时，开关 $i-1$ 的选择已经结束，而更靠右的开关又不会影响灯 $i$。
因此，扫描到灯 $i$ 时，开关 $i$ 是最后一个还能改变它的开关。
第二步：得到被迫的贪心决策
- 如果灯 $i$ 当前为亮，必须按下开关 $i$，否则它以后再也无法熄灭。
- 如果灯 $i$ 当前为灭，就不能按开关 $i$，否则会把它重新点亮。
每个位置的选择都是唯一的，不存在用后续操作补救的空间，所以这一线性扫描自然得到最少操作次数。
第三步：把影响传给下一盏灯
按下开关 $i$ 后，灯 $i$ 已经确定为灭。代码无需再修改它，只需在 $i<n$ 时用异或翻转灯 $i+1$，供下一轮读取最新状态。
题解代码
import sys
input = sys.stdin.readline
def solve():
test_count = int(input())
answers = []
for _ in range(test_count):
n = int(input())
lights = list(map(int, input().split()))
operation_count = 0
for i in range(n):
if lights[i] == 1:
operation_count += 1
if i + 1 < n:
lights[i + 1] ^= 1
answers.append(str(operation_count))
print('\n'.join(answers))
solve()
复杂度分析
时间复杂度：每组为 $O(n)$。
空间复杂度：输入数组占 $O(n)$，除输入外的额外空间为 $O(1)$。
第 2 题：魔法藤蔓
题目描述
一根藤蔓由 $n$ 个魔法段组成，从头到尾编号为 $1$ 到 $n$，第 $i$ 段的硬度为 $a_i$。每次可以选择以下一种操作：
- 在当前剩余藤蔓中找到硬度最大值最后一次出现的位置，将该位置及其右侧全部剪掉；
- 在当前剩余藤蔓中找到硬度最小值最后一次出现的位置，将该位置及其右侧全部剪掉。
“最后一次出现”就是并列时选择下标最大的魔法段。求至少操作多少次，才能让开头的第 $1$ 段也被剪掉。
输入包含多组测试。每组先输入魔法段数量 $n$，再输入 $n$ 个硬度。
样例
输入
2
3
1 3 2
4
4 2 4 1
输出
1
2
第一组当前最大硬度是 $3$、最小硬度是 $1$。直接选择最小值所在的第一段，就会一次剪掉整根藤蔓。
思路分析
第一步：把动态过程压缩成前缀长度
每次都从某个位置开始，将它和右侧全部剪掉。因此无论执行多少次，剩余部分一定是原数组的一个前缀 $[1,k]$。
不需要记录具体剪过哪些位置，只需要记录当前前缀长度 $k$。
第二步：定义动态规划状态
令 $f[k]$ 表示从只剩前缀 $[1,k]$ 开始，到剪掉第 $1$ 段所需的最少操作次数。空前缀已经完成目标，所以 $f[0]=0$。
再定义：
- $max_pos(k)$：前缀 $[1,k]$ 中最大值最右侧的位置；
- $min_pos(k)$：前缀 $[1,k]$ 中最小值最右侧的位置。
选择最大值操作后，剩余前缀长度变成 $max_pos(k)-1$；选择最小值操作后，剩余长度变成 $min_pos(k)-1$。于是有：
\[f[k] = 1 + \min\left(f[max\_pos(k)-1],\ f[min\_pos(k)-1]\right)\]第三步：扫描时同步维护前缀最值位置
从左到右扫描数组即可维护最大值、最小值及其最右下标。并列时要求选择下标最大的元素，因此更新条件必须包含等号：
- 当前值大于或等于前缀最大值时，更新最大值位置；
- 当前值小于或等于前缀最小值时，更新最小值位置。
每个状态只做常数次运算，总体是线性动态规划。
题解代码
import sys
input = sys.stdin.readline
def min_operations(hardness):
n = len(hardness)
dp = [0] * (n + 1)
max_value = float('-inf')
min_value = float('inf')
max_pos = 0
min_pos = 0
for k in range(1, n + 1):
value = hardness[k - 1]
if value >= max_value:
max_value = value
max_pos = k
if value <= min_value:
min_value = value
min_pos = k
dp[k] = 1 + min(dp[max_pos - 1], dp[min_pos - 1])
return dp[n]
def solve():
test_count = int(input())
answers = []
for _ in range(test_count):
n = int(input())
hardness = list(map(int, input().split()))
answers.append(str(min_operations(hardness)))
print('\n'.join(answers))
solve()
复杂度分析
时间复杂度：每组为 $O(n)$。
空间复杂度：$O(n)$，用于保存动态规划数组。
第 3 题：格子行走翻转
题目描述
有一条从 $1$ 开始编号、向右无限延伸的一维格子。初始时，编号为质数的格子是黑色，其余格子是白色，因此格子 $1$ 为白色。
给定长度为 $n$、只包含字符 0 和 1 的指令串 $s$。共有 $n$ 个人依次行动，第 $k$ 个人都从格子 $1$ 出发，只执行前 $k$ 条指令：
0：移动到当前位置严格右侧、编号最小的白格；1：移动到当前位置严格右侧、编号最小的黑格。
第 $k$ 个人完成移动后，会翻转终点格子的颜色。后面的人在已经发生这些翻转的棋盘上行动。
对于每组数据，输出两行：第一行是最终颜色与初始颜色不同的格子数量，第二行按升序输出这些格子的编号；若答案为空，第二行仍输出一个空行。
样例
输入
2
1
0
2
11
输出
1
4
2
2 5
当 $s=\texttt{0}$ 时，从格子 $1$ 向右遇到的第一个白格是 $4$，因此格子 $4$ 被翻转。
当 $s=\texttt{11}$ 时，第一个人落在质数格 $2$ 并把它翻成白色；第二个人重新从 $1$ 出发，依次走到黑格 $3$、黑格 $5$。最终与初始颜色不同的是格子 $2$ 和 $5$。
思路分析
第一步：直接模拟为什么太慢
第 $k$ 个人需要执行 $k$ 条指令。若每个人都从头重走，指令执行次数为 $1+2+\cdots+n=O(n^2)$。此外，每一步还要在动态变化的棋盘上寻找右侧最近的目标颜色，不能直接用静态的质数表代替。
需要同时解决两个问题：
- 复用相邻两个人的大部分路径；
- 动态维护颜色，并快速查找右侧第一个白格或黑格。
第二步：证明只需重算最后至多两步
第 $k-1$ 个人结束后，棋盘只改变了一个位置：他的终点。由于行走始终严格向右，这个终点比此前路径上的所有位置都大。
因此，第 $k$ 个人执行前 $k-2$ 条指令时，查询范围都位于旧终点左侧，结果不会受到这次翻转影响。可能变化的只有第 $k-1$ 步；重算这一步后，再计算第 $k$ 个人新增的第 $k$ 步即可。
用数组 path[j] 保存当前人员执行前 $j$ 条指令后的落点。每增加一个人，只更新 path[k-1] 和 path[k]，于是所有人的路径计算总量从平方级降为线性级。
第三步：用树状数组维护动态黑格
先在一个足够大的有限区间 $[1,B]$ 内用埃氏筛标记质数。树状数组 black_tree 维护每个位置当前是否为黑色：
- 单点翻转：若当前位置由白变黑则加 $1$，由黑变白则减 $1$；
- 前缀黑格数：树状数组前缀和；
- 前缀白格数：位置数量减去前缀黑格数。
要找位置 $x$ 右侧的第一个黑格，可以先计算前缀 $[1,x]$ 中有多少黑格，再在树状数组上寻找第“下一”个黑格。
白格查询也可以变成顺序统计。对任意前缀 $[1,p]$，白格数等于 $p-black(p)$。树状数组二进制提升时，若候选前缀的白格数仍小于目标序号，就跳过该段；否则向更小的范围继续定位。
每次查找和翻转均为 $O(\log B)$。
第四步：如何处理无限棋盘
无限棋盘不能一次建完。实现从一个估计上界开始；如果查询发现区间内不存在目标颜色，就将边界扩大一倍、重新筛质数并重建树状数组，同时保留此前所有翻转状态，再继续查询。
这样正确性不依赖固定经验系数。由于每次扩容至少翻倍，重建次数是对数级的；在常见数据范围下通常只会扩容很少几次。
第五步：维护最终答案
一个格子被翻转奇数次时，最终颜色才与初始颜色不同。使用集合 changed：每次翻转一个位置时，若它已在集合中就删除，否则加入。最后排序输出即可。
题解代码
import sys
input = sys.stdin.readline
def sieve(limit):
is_prime = bytearray(b'\x01') * (limit + 1)
is_prime[0] = 0
if limit >= 1:
is_prime[1] = 0
p = 2
while p * p <= limit:
if is_prime[p]:
start = p * p
count = (limit - start) // p + 1
is_prime[start:limit + 1:p] = b'\x00' * count
p += 1
return is_prime
class DynamicBoard:
def __init__(self, initial_limit):
self.limit = max(16, initial_limit)
self.flipped = set()
self._rebuild()
def _add(self, index, delta):
while index <= self.limit:
self.tree[index] += delta
index += index & -index
def _prefix_black(self, index):
total = 0
while index > 0:
total += self.tree[index]
index -= index & -index
return total
def _rebuild(self):
self.is_prime = sieve(self.limit)
current = bytearray(self.is_prime)
for position in self.flipped:
if position <= self.limit:
current[position] ^= 1
self.current = current
self.tree = [0] * (self.limit + 1)
for position in range(1, self.limit + 1):
self.tree[position] += current[position]
parent = position + (position & -position)
if parent <= self.limit:
self.tree[parent] += self.tree[position]
def _expand(self):
self.limit *= 2
self._rebuild()
def toggle(self, position):
old_color = self.current[position]
self.current[position] ^= 1
self._add(position, 1 if old_color == 0 else -1)
if position in self.flipped:
self.flipped.remove(position)
else:
self.flipped.add(position)
def _find_by_order(self, order, want_black):
index = 0
black_before = 0
step = 1 << (self.limit.bit_length() - 1)
while step:
next_index = index + step
if next_index <= self.limit:
next_black = black_before + self.tree[next_index]
next_count = next_black if want_black else next_index - next_black
if next_count < order:
index = next_index
black_before = next_black
step >>= 1
return index + 1
def next_position(self, position, want_black):
while True:
black_before = self._prefix_black(position)
count_before = black_before if want_black else position - black_before
total_black = self._prefix_black(self.limit)
total_count = total_black if want_black else self.limit - total_black
if total_count > count_before:
return self._find_by_order(count_before + 1, want_black)
self._expand()
def solve_case(instructions):
n = len(instructions)
board = DynamicBoard(max(64, 8 * n + 16))
path = [0] * (n + 1)
path[0] = 1
for k in range(1, n + 1):
if k > 1:
path[k - 1] = board.next_position(
path[k - 2], instructions[k - 2] == '1'
)
path[k] = board.next_position(
path[k - 1], instructions[k - 1] == '1'
)
board.toggle(path[k])
answer = sorted(board.flipped)
return answer
def solve():
test_count = int(input())
output = []
for _ in range(test_count):
n = int(input())
instructions = input().strip()
answer = solve_case(instructions[:n])
output.append(str(len(answer)))
output.append(' '.join(map(str, answer)))
print('\n'.join(output))
solve()
复杂度分析
设最终扩容后的边界为 $B$。
时间复杂度：筛法与历次扩容重建合计为 $O(B\log\log B)$；每个人只计算至多两个新落点并执行一次翻转，合计为 $O(n\log B)$。
空间复杂度：$O(B+n)$，用于质数标记、当前颜色、树状数组和路径数组。
小结
- 第一题的核心不是尝试不同开关组合，而是识别“当前开关是修正当前灯的最后机会”，从而得到唯一贪心决策。
- 第二题先把剪切过程压缩为前缀长度，再维护前缀最大值和最小值的最右位置，就能在线性时间内完成动态规划。
- 第三题的关键是路径增量引理：相邻两个人的前 $k-2$ 步不变，只需重算最后至多两步；动态颜色查询则通过质数筛、树状数组顺序统计和按需扩容完成。