大厂真题 / 百度

百度 7.16 笔试真题 - 研发岗

本场考试概述

考试时间：2026年7月16日

考试岗位：研发岗

难度评级：中等

考点分析：

• 第一题：周期模拟与取模（难度简单）
• 第二题：线性不变量、向量空间与可行性判定（难度中等偏难）
• 第三题：交替状态动态规划（难度中等）

建议策略：

• 第一题只记录到达每扇门时的时刻，用取模判断它处于开启段还是关闭段。
• 第二题先寻找操作保持不变的量，再证明这些不变量不但必要，而且足以刻画所有可达状态。
• 第三题要特别注意路径只能在走出边界时结束，不能因为后续贡献为负就主动停下。

第 1 题：断续传送门

题目描述

你需要依次经过 $n$ 扇传送门。所有传送门都从时刻 $t=0$ 开始运行。

第 $i$ 扇门会循环执行以下过程：

• 开启 $a_i$ 秒；
• 随后关闭 $b_i$ 秒；
• 然后重新开启 $a_i$ 秒，如此循环。

你在 $t=0$ 时到达第一扇门。到达一扇门时：

• 如果门正处于开启状态，就立即开始通过；
• 如果门正处于关闭状态，就等待到它下一次开启，再开始通过。

通过每一扇门都需要恰好 $1$ 秒。通过第 $i$ 扇门后立即到达第 $i+1$ 扇门。求通过全部传送门的时刻。

在每个周期中，将相位记为 $r=t\bmod(a_i+b_i)$。当 $0\le r<a_i$ 时门开启；当 $a_i\le r<a_i+b_i$ 时门关闭。特别地，$r=a_i$ 的瞬间已经算作关闭。

输入描述

第一行输入一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行输入一个整数 $n$，表示传送门数量；
• 接下来 $n$ 行，每行输入两个正整数 $a_i,b_i$。

数据范围：

• $1\le T\le 10^6$；
• 所有测试数据的 $n$ 之和不超过 $10^6$；
• $1\le a_i,b_i\le 10^9$。

输出描述

对每组测试数据输出一行一个整数，表示通过全部传送门的时刻。

样例

输入

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

输出

5
6

样例解释

第一组中：

• $t=0$ 时第一扇门开启，通过后为 $t=1$；
• $t=1$ 时第二扇门关闭，等待到 $t=2$，通过后为 $t=3$；
• $t=3$ 时第三扇门关闭，等待到 $t=4$，通过后为 $t=5$。

思路分析

令 time 表示到达当前传送门的时刻。对于参数为 $(a,b)$ 的门，其周期长度为

计算当前时刻在周期内的相位：

• 若 $remainder<a$，当前处于开启段，可以立刻通过；
• 若 $remainder\ge a$，当前处于关闭段，距离下一周期开启还需等待 $period-remainder$ 秒。

完成可能的等待后，再把通过门所需的 $1$ 秒加入答案：

只需要按顺序模拟一次，无需逐秒推进。

正确性证明

依次考虑每一扇门。假设 time 是到达当前门的真实时刻。

• 当 time % (a + b) < a 时，按照门的周期定义，此刻门开启，最早且实际的通过完成时刻就是 time + 1。
• 否则门关闭，本周期内不会再次开启；下一次开启恰好发生在 time + (a + b - time % (a + b))。等待到该时刻并花费 $1$ 秒通过，得到的也是最早且实际的完成时刻。

因此，每次更新后 time 都等于通过当前门的真实最早时刻。由数学归纳法，扫描完所有门后，time 就是通过全部传送门的时刻。

题解代码

import sys


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    iterator = iter(data)
    test_count = next(iterator)
    answers = []

    for _ in range(test_count):
        n = next(iterator)
        time = 0

        for _ in range(n):
            open_time = next(iterator)
            close_time = next(iterator)
            period = open_time + close_time
            remainder = time % period

            if remainder >= open_time:
                time += period - remainder

            time += 1

        answers.append(str(time))

    sys.stdout.write('\n'.join(answers))


solve()

复杂度分析

设所有测试数据的传送门总数为 $N$。

时间复杂度：$O(N)$。

空间复杂度：除读入数据与输出外，额外空间为 $O(1)$。代码一次性读入输入，因此实际输入存储为 $O(N)$。

第 2 题：防火墙

题目描述

有一个长度为 $n$ 的实数序列 $w_1,w_2,\ldots,w_n$。你可以执行任意多次以下操作：

选择一个下标 $i$（$1\le i\le n-2$）和任意实数 $x$，令连续三个元素发生变化：

请判断是否能通过若干次操作，使序列中所有元素都非负。

操作过程中的元素可以为负，只要求最终序列全部非负。由于 $x$ 可以是任意实数，操作也允许取负的 $x$。

输入描述

第一行输入一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行输入一个整数 $n$；
• 第二行输入 $n$ 个整数 $w_1,w_2,\ldots,w_n$。

数据范围：

• $1\le T\le 10^4$；
• 所有测试数据的 $n$ 之和不超过 $2\times 10^5$；
• $-10^9\le w_i\le 10^9$。

输出描述

若可以使所有元素非负，输出 YES；否则输出 NO。

样例

输入

4
3
-1 2 0
4
-2 2 2 0
3
1 -3 1
4
3 0 0 -1

输出

YES
YES
NO
NO

样例解释

• 第一组取 $i=1,x=-1$，序列由 $(-1,2,0)$ 变成 $(0,0,1)$。
• 第二组的总和 $S=2$，位置加权和 $Q=8$，满足 $0\le S\le Q\le 4S$，因此存在全非负的可达终态。
• 第三组总和为 $-1$，不可能得到元素总和非负的全非负序列。
• 第四组 $S=2,Q=-1$，而非负序列必须满足 $Q\ge S$，因此不可能。

思路分析

1. 找到两个不变量

定义序列总和

和位置加权和

一次操作在位置 $i,i+1,i+2$ 上增加的向量是

它对总和的改变量为

对位置加权和的改变量为

所以无论进行多少次操作，$S$ 和 $Q$ 都保持不变。

2. 推出必要条件

假设最终得到全非负序列 $v_1,v_2,\ldots,v_n$。那么

又因为每个位置 $j$ 都满足 $1\le j\le n$，且 $v_j\ge0$，所以

即

因此必要条件是

当 $S=0$ 时，这个条件自动要求 $Q=0$。

3. 证明条件足够：先构造一个非负目标

若 $S\ge0$ 且 $S\le Q\le nS$，可以只在位置 $1$ 和 $n$ 放置非负权重：

其余位置令 $v_j=0$。由 $S\le Q\le nS$ 可知 $v_1,v_n\ge0$，并且

所以确实存在一个全非负序列，与原序列具有相同的 $S,Q$。

这里 $n=1$ 时无需使用上述分母：此时 $Q=S=w_1$，判定条件恰好退化为 $w_1\ge0$。

4. 证明同样的两个不变量足以保证可达

还必须排除一种可能：虽然找到了具有相同 $S,Q$ 的非负序列，但操作未必能到达它。

对每个 $1\le i\le n-2$，记一次单位操作向量为

这些向量都满足总和与位置加权和为 $0$，且它们线性无关：若

观察第一个坐标可得 $c_1=0$；再依次观察第二、第三直到第 $n-2$ 个相关坐标，就能递推出所有 $c_i=0$。因此它们张成一个 $n-2$ 维空间。

另一方面，所有满足

的变化向量 $d$ 构成两个独立线性约束的解空间，其维数同样为 $n-2$。操作向量张成的空间包含于该解空间，且维数相同，所以二者完全相等。

于是，只要两个序列的 $S,Q$ 相同，它们的差就一定能写成若干操作向量的实数线性组合。因为每次操作的 $x$ 可以取任意实数，这个线性组合可以逐项执行，故构造出的非负目标一定可达。

对于 $n=1$ 或 $n=2$，没有可执行的三元操作，但结论仍成立：$S,Q$ 已唯一确定整个序列。具体地，$n=2$ 时

条件 $S\le Q\le2S$ 正好等价于 $w_1,w_2\ge0$。

综上，判定条件既必要又充分。

正确性证明

算法计算原序列的 $S,Q$，并仅在 $S\ge0$ 且 $S\le Q\le nS$ 时输出 YES。

• 必要性：操作保持 $S,Q$ 不变；任意全非负终态都满足 $S\ge0$ 和 $S\le Q\le nS$。因此算法不会把不可行情况误判为 YES。
• 充分性：条件成立时，存在具有同样 $S,Q$ 的全非负目标序列；所有保持 $S,Q$ 的变化都由三元操作向量张成，因此该目标从原序列可达。算法不会把可行情况误判为 NO。

故算法判定正确。

题解代码

import sys


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    iterator = iter(data)
    test_count = next(iterator)
    answers = []

    for _ in range(test_count):
        n = next(iterator)
        total = 0
        weighted_total = 0

        for position in range(1, n + 1):
            value = next(iterator)
            total += value
            weighted_total += position * value

        possible = (
            total >= 0
            and total <= weighted_total <= n * total
        )
        answers.append('YES' if possible else 'NO')

    sys.stdout.write('\n'.join(answers))


solve()

Python 整数不会溢出。若使用 64 位整数语言，$\lvert Q\rvert$ 在给定规模下可能达到约 $2\times10^{19}$，应使用 128 位整数计算加权和。

复杂度分析

设所有测试数据的元素总数为 $N$。

时间复杂度：$O(N)$。

空间复杂度：除读入数据与输出外，额外空间为 $O(1)$。

第 3 题：交替步长

题目描述

有一条长度为 $n$ 的数组 $A_1,A_2,\ldots,A_n$，以及两个正整数步长 $p,q$。

你可以任选一个位置作为起点，并任选 $p$ 或 $q$ 作为第一次移动的步长。将起点的权值计入路径和后，开始不断向右移动：

• 如果第一次选择步长 $p$，之后的步长依次为 $p,q,p,q,\ldots$；
• 如果第一次选择步长 $q$，之后的步长依次为 $q,p,q,p,\ldots$。

每到达一个仍在数组范围内的位置，就把该位置的权值加入路径和。某一步移动后位置超出数组右边界时，路径结束。

路径一旦开始，就必须按照交替规则一直移动到出界，不能在仍可移动到数组内时主动停止。求所有起点和两种首步选择中的最大路径和。

输入描述

第一行输入一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行输入三个整数 $n,p,q$；
• 第二行输入 $n$ 个整数 $A_1,A_2,\ldots,A_n$。

数据范围：

• $1\le T\le 10^5$；
• 所有测试数据的 $n$ 之和不超过 $2\times10^5$；
• $1\le p,q\le n$；
• $-10^9\le A_i\le10^9$。

输出描述

对每组测试数据输出一行一个整数，表示最大路径和。

样例

输入

3
3 1 2
1 3 9
4 1 2
5 -100 6 6
4 1 1
10 -100 5 7

输出

12
17
12

样例解释

• 第一组从位置 $2$ 出发并让首步为 $p=1$，访问 $2,3$，路径和为 $3+9=12$。
• 第二组从位置 $1$ 出发并让首步为 $q=2$，访问 $1,3,4$，路径和为 $5+6+6=17$。
• 第三组 $p=q=1$。从位置 $3$ 出发后必须继续走到位置 $4$，路径和为 $5+7=12$。

思路分析

1. 状态必须包含“下一步走多远”

只知道当前位置还不够，因为到达同一位置后，下一步可能应该走 $p$，也可能应该走 $q$。定义两个状态：

• $f_p[i]$：从位置 $i$ 出发，计入 $A_i$，且下一步必须走 $p$ 时，直到出界的路径和；
• $f_q[i]$：从位置 $i$ 出发，计入 $A_i$，且下一步必须走 $q$ 时，直到出界的路径和。

采用代码中的 $0$ 下标后，转移为

因为转移只指向更大的下标，所以从右向左计算即可。

2. 为什么绝对不能写 max(0, 后续状态)

本题只有“下一步走出右边界”才能结束路径。如果下一步仍在数组内，即使后续路径和为负，也必须继续走。

因此下面这种常见写法是错误的：

f_p[i] = A[i] + max(0, f_q[i + p])

max(0, ...) 等价于允许玩家在位置 $i$ 主动停止，改变了题意。

例如 $n=2,p=q=1,A=[100,-1000]$。从位置 $1$（代码下标 $0$）出发必须访问两个位置，路径和为 $-900$，不能只拿到 $100$ 就停止；从位置 $2$ 出发得到 $-1000$，所以该例的真正答案是 $-900$。错误转移却会虚构出答案 $100$。

只有当 i + step >= n、即这一步会直接出界时，后续贡献才是 $0$。

3. 枚举所有合法起始状态

题目允许任选起点，也允许首步选择 $p$ 或 $q$。所以最终答案为

即使所有 $A_i$ 都是负数，也必须选择一个起点，因此答案不能初始化为 $0$，而应初始化为负无穷或直接取状态数组的最大值。

正确性证明

按下标从右到左进行归纳。

对于位置 $i$：

• 若下一步 $p$ 会出界，则以 $p$ 为下一步的路径只访问位置 $i$，故 $f_p[i]=A_i$；
• 若 $i+p<n$，规则要求必须移动到 $i+p$，之后下一步切换为 $q$。路径不能提前停止，因此完整路径和唯一地等于 $A_i+f_q[i+p]$。

这正是 $f_p[i]$ 的转移。对 $f_q[i]$ 同理。由于依赖位置都严格位于 $i$ 的右侧，逆序计算时依赖状态已经正确，于是归纳得到所有状态均表示对应规则下直到出界的真实路径和。

每条合法路径都唯一对应某个起点及某种首步选择，也就是某个 $f_p[i]$ 或 $f_q[i]$；反之每个状态也对应一条合法路径。因此取所有状态的最大值，恰好得到题目要求的最大路径和。

题解代码

import sys


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    iterator = iter(data)
    test_count = next(iterator)
    answers = []

    for _ in range(test_count):
        n = next(iterator)
        p = next(iterator)
        q = next(iterator)
        values = [next(iterator) for _ in range(n)]

        dp_p = [0] * n
        dp_q = [0] * n

        for i in range(n - 1, -1, -1):
            dp_p[i] = values[i]
            if i + p < n:
                dp_p[i] += dp_q[i + p]

            dp_q[i] = values[i]
            if i + q < n:
                dp_q[i] += dp_p[i + q]

        answer = max(max(dp_p), max(dp_q))
        answers.append(str(answer))

    sys.stdout.write('\n'.join(answers))


solve()

复杂度分析

设所有测试数据的数组长度之和为 $N$。

时间复杂度：$O(N)$。

空间复杂度：每组 $O(n)$，用于两个动态规划数组。

小结

• 第一题通过 time % (a + b) 直接定位门在当前周期中的状态，只在关闭时跳到下一周期开头。
• 第二题的完整结论是：存在全非负可达终态，当且仅当 $S\ge0$ 且 $S\le Q\le nS$。关键不仅是找到两个不变量，还要证明操作向量张成了保持这两个量不变的全部变化。
• 第三题需要为“下一步走 $p$”和“下一步走 $q$”分别建状态。路径必须持续到出界，所以合法转移中不能出现 max(0, ...)，全负数组时答案也不能默认为 $0$。