大厂真题 / 百度

百度 2026-09-03 笔试真题 - 算法岗

本场考试概述

考试时间：2026 年 9 月 3 日

考试岗位：算法岗

难度评级：中等

题型说明：本场可确认有 3 道编程题，本文完整整理这 3 道题。

考点分析：

第 1 题：不变量、充要条件、字符计数；
第 2 题：位运算、按末尾连续 1 的数量分组计数；
第 3 题：阶段化建模、二分答案、排序与前缀和。

证据边界

本文只整理现有材料中能够由正文、公式、样例和源码相互核对的 3 道编程题。题面中因网页公式渲染而缺失的符号，按同页公式语义和源码恢复；约束按网页内容核对。未补写选择题、隐藏规则或无法确认的附加限制，样例输出仅表示题面给出的结果。

第 1 题：可删去的 01 串计数

题目描述

给定 $n$ 个仅由字符 0 和 1 构成的字符串。对任意一个字符串，可以重复执行以下操作：选择一对相邻且不同的字符，即 01 或 10，将这两个字符同时删除，再把剩余部分拼接起来。

若一个字符串经过若干次操作（也可以是 $0$ 次）后能够变为空串，则称它是“可删去的”。求给定字符串中可删去的字符串数量。

输入描述

第一行输入一个整数 $n$，表示字符串数量，满足

\[1\le n\le 2\times 10^5.\]

接下来 $n$ 行，每行输入一个仅由 0 和 1 构成的非空字符串 $s$，满足

\[1\le \lvert s\rvert\le 10^5.\]

保证所有字符串长度之和不超过 $5\times 10^5$。

输出描述

输出一个整数，表示可删去的字符串数量。

样例

输入

输出

样例解释：01 可以直接删空；0011 先删除中间的 01，剩余 01，再删除一次即可。其余字符串中 0 和 1 数量不同，无法删空。

算法

一次操作恰好删除一个 0 和一个 1，因此两种字符的数量差始终不变。若最后能得到空串，初始时 0 和 1 的数量必须相等。

反过来，若一个非空 01 串中两种字符数量相等，那么串中必然存在相邻的不同字符：否则所有相邻字符都相同，整个串只能由同一种字符组成，与两种字符数量相等矛盾。删除这样一对字符后，两种字符数量仍然相等；重复这个过程，最终一定能删到空串。

所以，可删去的充要条件就是 0 和 1 的数量相等。逐个字符串计数即可。

正确性证明

必要性：每次删除 01 或 10，都会让 0 和 1 的数量各减少 $1$，故二者数量差不变。空串中二者数量差为 $0$，所以能删空的字符串最初必须有相同数量的 0 和 1。

充分性：设当前字符串非空且 0 和 1 数量相等。若不存在相邻的不同字符，则所有相邻字符都相同，字符串只能全为 0 或全为 1，与两种字符数量相等矛盾。因此当前一定存在可删除的相邻字符对。删除该对后，两种字符数量仍相等，字符串长度减少 $2$。不断应用这一结论，有限次后字符串必为空。

综上，算法恰好统计所有可删去的字符串。

Python ACM 题解

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    n = int(data[0])
    answer = 0
    for raw in data[1:n + 1]:
        if raw.count(b"0") * 2 == len(raw):
            answer += 1

    print(answer)


if __name__ == "__main__":
    solve()

复杂度分析

设所有字符串的总长度为 $L$。

时间复杂度：$O(L)$，每个字符只被统计一次。

空间复杂度：除输入缓冲区外为 $O(1)$；计入一次性读入的数据为 $O(L)$。

易错点

操作必须同时删除相邻且不同的两个字符，不能删除 00 或 11；
不需要模拟删除过程，字符数量相等是充要条件；
只判断长度为偶数并不充分，例如 0000 仍然不能删空；
应利用总长度限制做线性处理，避免反复修改字符串导致平方复杂度。

第 2 题：相邻异或路径权值和

题目描述

数轴上有编号为 $1,2,\ldots,n$ 的点，仅相邻点之间有无向边。连接点 $i$ 与点 $i+1$ 的边权为

\[i\mathbin{\operatorname{xor}}(i+1),\]

其中 $\operatorname{xor}$ 表示按位异或。

求从点 $1$ 到点 $n$ 的唯一路径上所有边权之和，并对 $10^9+7$ 取模。也就是计算

\[\sum_{i=1}^{n-1}\bigl(i\mathbin{\operatorname{xor}}(i+1)\bigr)\pmod{10^9+7}.\]

输入描述

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

\[1\le T\le 2\times 10^5.\]

接下来 $T$ 行，每行输入一个整数 $n$，满足

\[1\le n\le 10^{18}.\]

输出描述

对每组测试数据输出一行一个整数，表示从点 $1$ 到点 $n$ 的路径权值和对 $10^9+7$ 取模后的结果。

样例

输入

输出

样例解释：$n=1$ 时无需经过边，答案为 $0$。$n=2$ 时只有边 $(1,2)$，边权为 $1\operatorname{xor}2=3$。$n=3$ 时两条边权分别为 $3$ 和 $1$，总和为 $4$。$n=10$ 时九条边权依次为 $3,1,7,1,3,1,15,1,3$，总和为 $35$。

算法

设非负整数 $i$ 的二进制末尾恰有 $t$ 个连续的 1。计算 $i+1$ 时，这 $t$ 个 1 变为 0，其上一位的 0 变为 1，更高位不变。因此恰好低 $t+1$ 位发生翻转，有

\[i\mathbin{\operatorname{xor}}(i+1)=2^{t+1}-1.\]

末尾恰有 $t$ 个连续 1 的整数满足

\[i\equiv 2^t-1\pmod{2^{t+1}}.\]

令 $M=n-1$，只需统计区间 $[1,M]$ 中每一类整数的数量。记

\[r=2^t-1,\qquad p=2^{t+1}.\]

先统计数列 $r,r+p,r+2p,\ldots$ 落在 $[0,M]$ 中的项数：当 $r\le M$ 时为

\[\left\lfloor\frac{M-r}{p}\right\rfloor+1.\]

$t=0$ 时 $r=0$，上述计数包含了不属于求和范围的 $i=0$，必须额外减 $1$。把每组数量乘以对应边权 $p-1$ 并累加即可。由于 $n\le 10^{18}$，枚举约 $60$ 个二进制位就足够。

正确性证明

引理 1：若 $i$ 的末尾恰有 $t$ 个连续 1，则 $i\operatorname{xor}(i+1)=2^{t+1}-1$。

证明：加一会把末尾 $t$ 个 1 全部变成 0，并把紧邻的上一位 0 变成 1；其余位不变。异或结果的低 $t+1$ 位全为 1，更高位全为 0，故值为 $2^{t+1}-1$。

引理 2：算法为每个 $t$ 准确统计了区间 $[1,n-1]$ 中末尾恰有 $t$ 个连续 1 的整数数量。

证明：这类整数恰好是模 $2^{t+1}$ 余 $2^t-1$ 的整数，算法按首项和公差统计其在 $[0,n-1]$ 中的数量。只有 $t=0$ 时首项为 $0$，算法将其扣除，故最终范围恰为 $[1,n-1]$。

每个正整数的末尾连续 1 数量唯一，因此各组不重不漏地划分了所有边的左端点。由引理 1，每组使用了正确边权；由引理 2，每组数量也正确。所以累加结果等于题目要求的路径权值和，取模不改变模意义下的答案。

Python ACM 题解

import sys


MOD = 10 ** 9 + 7


def path_weight_sum(n):
    last = n - 1
    answer = 0

    for t in range(61):
        first = (1 << t) - 1
        if first > last:
            break

        step = 1 << (t + 1)
        count = (last - first) // step + 1
        if t == 0:
            count -= 1  # 排除不在 [1, n - 1] 内的 i = 0

        answer = (answer + count % MOD * ((step - 1) % MOD)) % MOD

    return answer


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    t = data[0]
    answers = [str(path_weight_sum(n)) for n in data[1:t + 1]]
    sys.stdout.write("\n".join(answers))


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：每组为 $O(\log n)$，全部测试为 $O(T\log n)$。

空间复杂度：除输入和输出缓冲区外为 $O(1)$；计入缓冲区为 $O(T)$。

易错点

求和范围是 $1\le i\le n-1$，不是从 $i=0$ 开始；
$t=0$ 这一组按余数公式会包含 $i=0$，必须将它排除；
$n=1$ 时没有任何边，答案应为 $0$；
单条边权是 $2^{t+1}-1$，不是 $2^t-1$；
其他语言中计数可达 $10^{18}$，乘法前应先取模或使用足够宽的整数类型。

第 3 题：循环血量怪物最少讨伐天数

题目描述

有 $m$ 个怪物。给定长度为 $n$ 的数组 $a$，第 $D$ 天（从 $1$ 开始）所有仍存活怪物的血量都会统一重置为

\[a_{((D-1)\bmod n)+1}.\]

勇者的初始攻击力为 $k$，攻击力每经过完整的 $n$ 天增加 $1$。因此第 $D$ 天的攻击力为

\[k+\left\lfloor\frac{D-1}{n}\right\rfloor.\]

每天至多选择一个怪物攻击一次：若当日攻击力不小于怪物的当日血量，则打败该怪物；否则攻击失败，没有怪物被打败。第二天，所有存活怪物的血量仍按上述循环规则统一重置。

求打败全部 $m$ 个怪物最少需要多少天。

输入描述

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

\[1\le T\le 10^3.\]

每组测试数据包含两行：

第一行输入三个整数 $n,m,k$，满足 $1\le n\le 2\times 10^5$，$1\le m\le 10^{12}$，$0\le k\le 10^{12}$；
第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $1\le a_i\le 10^{12}$。

保证所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

输出描述

对每组测试数据输出一行一个整数，表示打败全部 $m$ 个怪物所需的最少天数。

样例

输入

输出

6
6

样例解释：第一组中，第 $1$ 至 $3$ 天攻击力为 $2$，血量依次为 $1,3,2$，可在第 $1$、$3$ 天各打败一只；第 $4$ 至 $6$ 天攻击力为 $3$，三天都能成功，故第 $6$ 天清空。第二组血量始终为 $5$，攻击力从 $0$ 开始每天增加 $1$，到第 $6$ 天攻击力首次达到 $5$，当天打败唯一怪物。

算法

把每连续 $n$ 天看作一个阶段，阶段从 $j=0$ 开始编号。阶段 $j$ 中攻击力恒为 $k+j$，且 $n$ 天的血量依次为 $a_1,\ldots,a_n$。

对周期位置 $i$，令

\[d_i=\max(0,a_i-k).\]

这表示从阶段 $d_i$ 起，该位置对应的那一天可以成功击杀。到阶段 $j$ 结束时，该位置贡献的可击杀天数为

\[\max(0,j-d_i+1).\]

因此，从阶段 $0$ 到阶段 $j$ 的全部可击杀天数为

\[S(j)=\sum_{i=1}^{n}\max(0,j-d_i+1).\]

每天最多击杀一只，而怪物在各天没有个体差异，所以前若干天最多能击杀的数量就是其中成功日的数量，上限再受剩余怪物数限制。于是答案所在的最小阶段就是满足 $S(j)\ge m$ 的最小 $j$。

为快速计算 $S(j)$，将 $d_i$ 排序为 $d’1\le\cdots\le d’_n$，并建立前缀和 $P_c=\sum{i=1}^c d’_i$。二分得到满足 $d’_i\le j$ 的元素个数 $c$，则

\[S(j)=c(j+1)-P_c.\]

$S(j)$ 单调不减，可以二分最小阶段 $j$。上界取 $d’_1+m-1$：最容易成功的周期位置从阶段 $d’_1$ 开始，每阶段至少贡献一次，连续 $m$ 个阶段一定足够。

找到阶段 $j$ 后，先计算前 $j-1$ 个阶段已经出现的成功日数，还差

\[r=m-S(j-1)\]

只怪物。在阶段 $j$ 内按原数组顺序扫描，找到第 $r$ 个满足 $a_i\le k+j$ 的位置 $i$，最终答案为 $jn+i$。

正确性证明

引理 1：周期位置 $i$ 从阶段 $d_i=\max(0,a_i-k)$ 起，每个阶段都对应一个成功日，在更早阶段均不成功。

证明：阶段 $j$ 的攻击力为 $k+j$。该位置成功当且仅当 $k+j\ge a_i$，即 $j\ge a_i-k$。又因阶段编号非负，最早阶段恰为 $\max(0,a_i-k)=d_i$。攻击力随后单调增加，所以此后每阶段都成功。

引理 2：$S(j)$ 等于阶段 $0$ 至 $j$ 中成功日的总数。

证明：由引理 1，当 $j<d_i$ 时位置 $i$ 尚无成功日，贡献 $0$；当 $j\ge d_i$ 时，它在阶段 $d_i,d_i+1,\ldots,j$ 各贡献一天，共 $j-d_i+1$ 天。对全部周期位置求和即得 $S(j)$。

引理 3：二分得到的 $j$ 是最终击杀发生的阶段。

证明：每个成功日至多击杀一只怪物，且在仍有怪物时总可以选择一只击杀，因此累计可击杀数量与累计成功日数一致，直到达到 $m$。最小满足 $S(j)\ge m$ 的阶段 $j$ 之前，成功日不足 $m$，不可能清空；阶段 $j$ 结束前成功日已达到 $m$，一定能够清空。因此最终击杀发生在阶段 $j$。

进入阶段 $j$ 时还需要第 $r=m-S(j-1)$ 个成功日。算法按该阶段真实日期顺序扫描原数组，返回第 $r$ 个成功位置 $i$，所以此前成功日总数为 $m-1$，第 $jn+i$ 天恰好击杀最后一只怪物。故算法返回最少天数。

Python ACM 题解

import sys
from bisect import bisect_right


def min_days(n, monster_count, initial_power, health):
    thresholds = sorted(max(0, value - initial_power) for value in health)
    prefix = [0] * (n + 1)
    for i, value in enumerate(thresholds):
        prefix[i + 1] = prefix[i] + value

    def successful_days(stage):
        if stage < 0:
            return 0
        count = bisect_right(thresholds, stage)
        return count * (stage + 1) - prefix[count]

    low = 0
    high = thresholds[0] + monster_count - 1
    while low < high:
        middle = (low + high) // 2
        if successful_days(middle) >= monster_count:
            high = middle
        else:
            low = middle + 1

    stage = low
    remaining = monster_count - successful_days(stage - 1)
    power = initial_power + stage

    for index, value in enumerate(health, start=1):
        if value <= power:
            remaining -= 1
            if remaining == 0:
                return stage * n + index


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    test_cases = data[0]
    position = 1
    answers = []

    for _ in range(test_cases):
        n, monster_count, initial_power = data[position:position + 3]
        position += 3
        health = data[position:position + n]
        position += n
        answers.append(str(min_days(n, monster_count, initial_power, health)))

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


if __name__ == "__main__":
    solve()

复杂度分析

单组数据中，排序耗时 $O(n\log n)$；二分阶段进行 $O(\log(d_{\min}+m))$ 次检查，每次用二分查找在 $O(\log n)$ 时间计算 $S(j)$；最后扫描一个阶段耗时 $O(n)$。

时间复杂度：

\[O\bigl(n\log n+\log(d_{\min}+m)\log n\bigr),\]

在给定范围内也可简写为 $O(n\log n)$。

空间复杂度：$O(n)$，用于阈值数组和前缀和。

易错点

第 $D$ 天所在阶段是 $\lfloor(D-1)/n\rfloor$，日期和数组下标都存在偏移；
血量每天会统一重置，不是在上一次攻击后的血量上继续扣除；
每天最多击杀一只，即使攻击力足够，也不能同一天击杀多只；
$d_i$ 必须写成 $\max(0,a_i-k)$，初始攻击力已经足够时阈值为 $0$；
排序后的数组只用于计算累计成功日，定位最后一天时必须按原始 $a_i$ 顺序扫描；
successful_days(stage - 1) 需要正确处理 stage = 0；
天数及累计成功日可能远超 32 位整数范围，非 Python 语言应使用 64 位整数。

复盘建议

删除操作题先寻找操作保持不变的量，再分别证明必要性与充分性；
相邻整数异或可从“加一导致哪些二进制位翻转”入手，并按末尾连续位分组；
遇到周期状态与阶段增长同时存在时，可先以完整周期为阶段压缩时间轴；
二分答案前要明确单调函数，并证明所选上界一定可行；
排序用于聚合统计时，不要丢失最终答案对原时间顺序的依赖。

这篇文章有帮助吗？

| GitHub 留言