大厂真题

百度算法岗 2026-09-10

本场考试概述

考试时间：2026年9月10日

考试岗位：算法岗

难度评级：中等

考点分析：

• 第一题：构造（简单）
• 第二题：二分答案 + 贪心 + 差分（中等）
• 第三题：数论（中等偏难）

建议策略：

• 第一题的区间只是干扰项，交替串 0101… 对任意偶数长度的区间都成立，读完 n 直接输出即可，别去逐个满足区间
• 第二题看到”最小值最大化”就想二分答案，判定时从左往右补缺口、窗口起点尽量靠右，再用差分把单次判定压到线性
• 第三题先证明”起点对 H 余数不同”就保证互不重叠，答案化成对每个 H 取 min(H, cnt) 的最大值；H 可能大于标记种数，不能只枚举到 c
• 第二题的单个缺口可达 3 乘 10 的 9 次方，C++、Java、Go 要用 64 位整数

第 1 题：区间平衡01串构造

题目描述

给定一个正整数 以及 个区间，第 个区间为 ，保证每个区间的长度 都是偶数。

请构造一个长度为 且仅由字符 和 组成的字符串 （下标从 开始），使得对于每一个给定区间 ，子串 中字符 的个数与字符 的个数相等。

可以证明在题目给定的范围内一定存在满足条件的字符串。如果存在多个满足条件的字符串，输出任意一个即可。

输入描述

第一行输入一个整数 ，表示字符串的长度。

第二行输入一个整数 ，表示区间的数量，保证 为偶数。

此后 行，第 行输入两个整数 ，表示第 个区间，保证 为偶数。

输出描述

在一行上输出一个长度为 的字符串，表示构造出的答案。

如果存在多个满足条件的字符串，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

7
4
1 4
2 7
3 6
5 6

输出

0101010

样例解释

构造的字符串为 。区间 对应子串 ，区间 对应子串 ，二者都含 个 和 个 ；区间 对应子串 ，含 个 和 个 ；区间 对应子串 ，含 个 和 个 。四个区间全部满足条件。

题解：构造

思路分析

给出若干个长度为偶数的区间，要构造一个 01 串，使每个区间内 和 的个数相等，多解任取其一。

这是一道看穿之后几乎没有代码的构造题：区间多达 个且互相重叠，逐个去满足会互相牵制，关键是找到一个对所有偶数长度区间同时成立的串。

算法实现

先看交替串 有什么性质。它任意相邻的两位，恰好是一个 和一个 。

对长度为偶数的区间 ，从 开始每两位切一刀，正好切成 对相邻位置，每对各贡献一个 和一个 ，于是

这里 、 分别是区间内 与 的个数。推导只用到了区间长度为偶数，与区间在哪、和别的区间怎样重叠都无关，所以交替串一次性满足全部 个约束。

题面保证长度为偶数，正是这个构造成立的前提。反过来，只要混进一个长度为奇数的区间， 为奇数，任何串都不可能让两者相等。

实现上只需读入 ，从第 位起奇数位放 、偶数位放 ，拼成字符串输出，区间数据不参与计算。以 开头的 同样合法，评测会逐个区间核验，两种都能通过。

复杂度分析

时间复杂度：。逐位生成长度为 的字符串是唯一开销，与区间个数 无关。

空间复杂度：，存放待输出的字符串。

题解代码

import sys
input = sys.stdin.readline

def build(n):
    chars = []
    for i in range(n):
        chars.append('0' if i % 2 == 0 else '1')
    return ''.join(chars)

n = int(input())
print(build(n))

正确性说明

任意偶数长度区间都能分成相邻两位，每对在交替串中含一个零和一个一，故所有给定区间同时平衡。

易错点与边界

区间数量为偶数是题面给出的附加条件，构造本身只依赖每个区间长度为偶数。多解输出不必与样例逐字符一致。

第 2 题：定长区间加一最大化最小值

题目描述

给定一个长度为 的整数数组 ，以及两个整数 和 。

你可以进行至多 次操作。每次操作选择一个整数 ，将 这连续 个元素各加上 。同一个位置 可以被选择多次。

请求出在操作次数不超过 的前提下，数组最小值 能够达到的最大值。

输入描述

第一行输入三个整数 ，分别表示数组长度、每次操作覆盖的元素个数以及操作次数上限。

第二行输入 个整数 ，表示数组元素。

输出描述

在一行上输出一个整数，表示数组最小值能够达到的最大值。

样例1

输入

5 3 4
2 5 3 6 1

输出

3

样例解释

每次操作覆盖连续 个元素，最多操作 次。

要让最小值达到 ：先选 操作 次，数组变为 ；此时 还差 ，而能覆盖 的只有 ，选它操作 次，数组变为 ，最小值为 ，共用 次操作。

要让最小值达到 ： 需要 操作 次， 需要 操作 次，共需 次，超过上限 ，无法做到。因此答案为 。

题解：二分答案

思路分析

每次把一段长度固定为 的连续区间整体加 ，最多做 次，要让数组最小值尽可能大。

这是一道判定比求值容易的题：给定目标值问能否做到，从左往右补缺口就能回答，且可行性随目标值单调。

算法实现

二分答案：二分最终的最小值 。 能达到时，同一套操作对任何更小的目标也成立，满足二分的单调性。每次操作最多让最小值加 ，故答案落在 内。

check 函数：给定 ，从左往右扫，维护当前位置已被叠加的量 ，位置 的缺口为

若 ，就以 为起点补做 次操作，累计次数超过 立刻判不可行。

起点这样选是最优的。左边位置都已达标，缺口只能靠覆盖 的窗口补；这些窗口里起点越靠右，盖住的右侧元素越多，把任何更靠左的起点换成它，后面的缺口只减不增。起点上限是 ，所以末尾 个位置只能共用最后一个窗口。

朴素写法每补一次就把窗口内 个元素逐个加上，单次 check 是 ， 时远超时限。改用差分，在 处记下这批加量到此失效，扫到那里时从 里减掉，单次 check 降到 。

可达 而 低到 ，单个缺口就有 ，缺口与累计次数须用 位整数。

二分过程：check 通过令 ，否则令 。中点取上中位数 ，否则 且 check 通过时会死循环。

输出：区间收缩到 时， 就是最小值能达到的最大值。

复杂度分析

时间复杂度：O(n log(k+2))，包含 k=0 时的输入和最小值扫描。

空间复杂度：O(n)。

题解代码

import sys
input = sys.stdin.readline

def check(a, n, w, k, target):
    expire = [0] * (n + 1)
    last = n - w  # 窗口起点（0 下标）最多只能到 n-w
    add = 0       # 当前位置被所有生效窗口加了多少
    used = 0      # 已经用掉的操作次数
    for i in range(n):
        add -= expire[i]
        need = target - a[i] - add
        if need > 0:
            used += need
            if used > k:
                return False
            add += need
            start = i if i < last else last
            expire[start + w] += need
    return True

def max_min_value(a, n, w, k):
    lo = min(a)
    hi = lo + k
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2
        if check(a, n, w, k, mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

n, w, k = map(int, input().split())
a = list(map(int, input().split()))
print(max_min_value(a, n, w, k))

正确性说明

从左向右处理首个不足目标的位置，任何方案都必须补足该缺口。把覆盖它的操作尽量右移，既不破坏已满足位置，又不减少对未来位置的覆盖，故贪心使用最少操作。差分只压缩相同的区间更新；单调判定上的二分得到最大可行目标。

易错点与边界

数组允许负数，k 可以为 0；末尾起点需要截到 n-w，不能创建越界窗口。

第 3 题：周期标记最多启用种数

题目描述

在一条向两端无限延伸的数轴上，整数点的下标取遍全体整数 。现有 种标记，第 种标记的周期为 。

标记的规则如下：若某个整数点 被打上第 种标记，那么整数点 与 也必须打上第 种标记，并且该规则会反复生效。也就是说，第 种标记一旦从起点 开始打，就会覆盖集合 中的所有整数点。

你需要先选定一个正整数 ，然后从这 种标记中挑选若干种启用，并为每种启用的标记指定一个起点，要求同时满足以下两个条件：

1. 每种启用的标记，其周期 必须是 的倍数；
2. 任意两种启用的标记，它们的起点对 取模的结果互不相同。

每个整数点最多只能打上一种标记，允许存在不打任何标记的整数点。请求出启用的标记种数最多是多少。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数 ，表示数据组数，每组测试数据描述如下：

在一行上先输入一个整数 ，表示标记的种数，紧接着在同一行输入 个整数 ，表示每种标记的周期。

保证所有测试数据的 之和不超过 。

输出描述

在一行上输出 个整数，相邻两个整数之间用一个空格分隔，第 个整数表示第 组测试数据中启用的标记种数的最大值。

样例1

输入

3
5 6 10 15 30 7
4 2 2 2 2
3 5 7 11

输出

3 2 1

样例解释

第一组数据取 ，周期是 的倍数的标记为 ，共 种，而对 取模有 种不同结果，足够让它们的起点互不相同，因此可以启用 种。取 同样能启用 这 种，而任何 都无法启用 种，答案为 。

第二组数据取 ， 种标记的周期都是 的倍数，但对 取模只有 种不同结果，所以最多启用 种，答案为 。

第三组数据中周期 两两没有大于 的公约数，任何 至多只能启用 种，取 时对 取模只有 种结果，答案为 。

题解：数论

思路分析

给定 个周期，选一个 ，只能启用周期是 倍数的标记，且起点对 的余数互不相同，求最多启用几种。

这是一道先化简条件、再解决计数效率的数论题：看清不重叠限制自动成立后，答案是一个最值式，难点变成快速统计每个 的倍数个数。

算法实现

先看不重叠这条限制。两种标记覆盖的点集 与 有公共点，当且仅当 ，其中 。若 都是 的倍数，则 ，起点对 余数不同就推出对 余数也不同，两者必然不相交。

于是固定 后，能用的标记有 种，可用的余数只有 种，把起点依次取 就能取满较小的那个：

朴素做法对每个 扫一遍全部周期，单组就是 次。

改为从周期出发去数。 不是任何 的约数时 ，不影响答案；反过来从每个 出发，给它的每个约数各记一次，就恰好得到全部非零的 。总工作量是 ， 以内的数约数最多 个，最坏约 次加法。

注意 不能只枚举到 。周期为 时取 能启用 种，而 都只能启用 种，只看 会得到错误答案 。

算法实现上分三步：

第一步，用调和级数 筛预处理约数表：对每个 ，把它追加到 的约数表里。

第二步，每组先按值去重得到重数 ，对每个不同的值 ，给它约数表里的每个 执行 。C++、Java、Go 用数组计数，处理完一组只清零本组碰过的下标；若每组都清空整个数组， 时就是 次清零。

第三步，遍历本组出现过的 ，取 的最大值作为该组答案。

复杂度分析

时间复杂度：O(M log(M+1)+S+∑τ(v))，S 为全部周期输入数；求和按各组不同周期 v 计，τ 为约数个数。

空间复杂度：O(M log(M+1)+S)，包含约数表及全部输入组。

题解代码

import sys
input = sys.stdin.readline

from collections import Counter
from itertools import chain

def build_divisors(limit):
    divs = [[] for _ in range(limit + 1)]
    for d in range(1, limit + 1):
        for j in range(d, limit + 1, d):
            divs[j].append(d)
    return divs

def max_enabled(ps, divs):
    freq = Counter(ps)
    cnt = Counter(chain.from_iterable(map(divs.getitem, freq)))
    for v, f in freq.items():
        if f > 1:
            for d in divs[v]:
                cnt[d] += f - 1
    return max(map(min, cnt.keys(), cnt.values()))

t = int(input())
groups = []
for _ in range(t):
    nums = list(map(int, input().split()))
    groups.append(nums[1:])

limit = max(max(g) for g in groups)
divs = build_divisors(limit)
print(' '.join(str(max_enabled(g, divs)) for g in groups))

正确性说明

固定 H 后只有整除 H 的周期可选，且最多使用 H 个不同余数。取互异起点余数可使各标记集合不相交，因此上界 min(H,cnt) 可以达到。枚举所有实际出现的周期约数覆盖一切可能有正贡献的 H，取最大值正确。

易错点与边界

H 可以大于标记种数，例如两个周期均为 5。复杂度需包含全部输入组占用，不能只写约数表的空间。

小结

优先从题面约束提炼模型，再用样例检查边界。本文保留题面数学符号的原始 SVG，代码统一为 Python 3；未给出的评测限制或规则不补作事实。