大厂真题 / 百度

百度 2026-8-6 笔试真题 - 算法岗

本场考试概述

考试时间：2026年8月6日

考试岗位：算法岗

难度评级：中等

考点分析：

• 第一题：极差与区间合并贪心（难度简单）
• 第二题：异或、按位与和二进制进位（难度中等）
• 第三题：置换环、KMP 最小循环节、质因数分解求最小公倍数（难度中等偏难）

建议策略：

• 第一题先比较一段被切开前后的贡献，证明合并相邻段不会变差，便可直接计算整段贡献。
• 第二题利用 $x+y=(x\oplus y)+2(x\mathbin{\&}y)$，把问题转化为二进制低位的必要条件。
• 第三题不能只对置换环长求最小公倍数；字符可能在环上提前重复，必须先求每个环的字符序列最小循环节。

第 1 题：平衡度划分

题目描述

给定长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$。需要把整个序列划分为若干个非空连续子段，每个元素恰好属于一个子段。

对于子段 $[l,r]$，定义其平衡度为

一次划分的总价值是所有子段平衡度之和。求所有合法划分中的最大总价值。

输入描述

第一行输入整数 $T$，表示测试数据组数，满足 $1\le T\le 10^4$。

每组测试数据包含两行：

• 第一行输入整数 $n$，满足 $1\le n\le 3\times 10^5$；
• 第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $1\le a_i\le 10^9$。

保证单个测试文件中所有测试数据的 $n$ 之和不超过 $3\times 10^5$。

输出描述

对每组测试数据输出一行一个整数，表示最大总价值。

样例

输入

3
5
1 3 2 5 4
1
7
4
2 2 2 2

输出

20
0
0

第一组把整个序列作为一个子段时，平衡度为 $(5-1)\times 5=20$。

思路分析

设某个子段的最大值、最小值和长度分别为 $M,m,L$。若从中间把它切成两个非空子段，并记两段的信息为 $(M_1,m_1,L_1)$ 和 $(M_2,m_2,L_2)$，则

所以两个新子段的极差都不会超过原子段的极差：

切开后的总贡献满足

因此，切一刀只可能使价值减小或保持不变。反过来看，合并任意两个相邻子段不会让总价值下降。把任意划分持续合并，最终会得到只含整个序列的一个子段，而且价值不小于原划分。

于是最优方案就是不切，答案为

正确性证明

引理：将任意一个子段划分成两个非空连续子段后，两段平衡度之和不大于原子段平衡度。

证明：两段的最大值均不大于原段最大值，两段的最小值均不小于原段最小值，故两段极差均不大于原段极差。分别乘以两段长度再相加，得到的上界恰好是原段极差乘以两段长度之和，也就是原段平衡度。引理得证。

定理：算法输出的是最大总价值。

证明：对任意合法划分，反复合并相邻子段。由引理的逆向表述，每次合并都不会减小价值。最终只剩整个序列这一个子段，所以整段不切的价值不小于任意划分的价值。算法计算的正是该价值，因此答案最优。定理得证。

ACM Python 代码

import sys


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

    for _ in range(test_count):
        n = next(it)
        first = next(it)
        minimum = first
        maximum = first

        for _ in range(n - 1):
            value = next(it)
            if value < minimum:
                minimum = value
            if value > maximum:
                maximum = value

        answers.append(str((maximum - minimum) * n))

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


if __name__ == '__main__':
    solve()

复杂度分析

设当前测试的序列长度为 $n$。

时间复杂度：$O(n)$，只需扫描序列一次。

空间复杂度：除读入与输出缓冲外为 $O(1)$；若计入一次性读入的数据，则为 $O(\sum n)$。

易错点

• 不需要区间 DP；$n$ 达到 $3\times 10^5$，平方复杂度无法通过。
• 答案最大约为 $(10^9-1)\times 3\times10^5$，固定宽度语言必须使用 64 位整数。
• $n=1$ 或所有元素相等时答案自然为 $0$，无需额外构造划分。

第 2 题：最小爆发值

题目描述

给定正整数 $n$。选择整数 $x$，满足 $0\le x\le n$，并把 $n$ 分成 $x$ 与 $n-x$ 两部分。

定义这次分割的爆发值为

其中 $\oplus$ 表示按位异或。求最小可能的爆发值，即

输入描述

第一行输入整数 $T$，表示测试数据组数，满足 $1\le T\le 10^5$。

接下来 $T$ 行，每行输入一个整数 $n$，满足 $1\le n\le 10^{18}$。

输出描述

对每组测试数据输出一行一个整数，表示最小爆发值。

样例

输入

5
1
4
11
7
1000000000000000000

输出

1
0
3
7
0

例如 $n=11$ 时，可以取 $x=4$，另一部分为 $7$，爆发值为 $4\oplus7=3$。

思路分析

记

二进制加法恒等式给出

并且 $s\mathbin{\&}c=0$：同一位不可能既表示 $x,y$ 不同，又表示二者都为 $1$。

设 $n$ 的二进制末尾恰有 $t$ 个连续的 $1$。也就是说，$n$ 的第 $0$ 至第 $t-1$ 位为 $1$，第 $t$ 位为 $0$；当 $n$ 为偶数时 $t=0$。

下面考察等式 $n=s+2c$ 的低位：

• 第 $0$ 位中，$2c$ 恒为 $0$，所以当 $t\ge1$ 时，$s$ 的第 $0$ 位必须为 $1$；再由 $s\mathbin{\&}c=0$，$c$ 的第 $0$ 位必须为 $0$。
• 假设 $s$ 的前 $i$ 位都是 $1$、$c$ 的前 $i$ 位都是 $0$。这些低位相加不会产生进位；在第 $i$ 位，$2c$ 取的是 $c$ 的第 $i-1$ 位，仍为 $0$。由于 $n$ 的第 $i$ 位为 $1$，$s$ 的第 $i$ 位只能为 $1$，进而 $c$ 的第 $i$ 位只能为 $0$。

归纳可知，$s$ 的低 $t$ 位必须全为 $1$，因此

这个下界可以达到。取

由于 $n$ 的二进制末尾恰为 $t$ 个 $1$，$n-s$ 是 $2^{t+1}$ 的倍数，所以 $c$ 的低 $t$ 位全为 $0$，从而 $s\mathbin{\&}c=0$。令 $x=s+c,y=c$，便有 $x\oplus y=s$ 且 $x+y=n$。

因此答案就是 $n$ 二进制末尾连续 $1$ 组成的数 $2^t-1$。而 $n+1$ 的末尾恰有 $t$ 个 $0$，故

最终得到闭式

正确性证明

引理 1：任意合法分割的爆发值 $s$ 的低 $t$ 位均为 $1$，其中 $t$ 是 $n$ 末尾连续 $1$ 的数量。

证明：由 $n=s+2c$ 与 $s\mathbin{\&}c=0$，从最低位开始归纳。每一位上，之前没有产生进位，且 $2c$ 的当前位由已证明为 $0$ 的 $c$ 的前一位提供；为得到 $n$ 当前位的 $1$，$s$ 当前位必须为 $1$，继而 $c$ 当前位必须为 $0$。归纳覆盖低 $t$ 位。引理得证。

引理 2：存在爆发值为 $2^t-1$ 的合法分割。

证明：令 $s=2^t-1,c=(n-s)/2$。由尾随位结构可知 $c$ 的低 $t$ 位全为 $0$，所以 $s\mathbin{\&}c=0$。取 $x=s+c,y=c$，在二进制中 $s$ 与 $c$ 没有重叠的 $1$，故 $x=s+c=s\oplus c$，于是 $x\oplus y=s$，同时 $x+y=s+2c=n$。引理得证。

定理：算法输出最小爆发值。

证明：引理 1 给出任何答案都不小于 $2^t-1$；引理 2 构造出恰好达到该下界的分割。算法用 lowbit(n + 1) - 1 计算该值，所以输出最优。定理得证。

ACM Python 代码

import sys


def minimum_burst(n):
    value = n + 1
    return (value & -value) - 1


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

    for i in range(1, test_count + 1):
        answers.append(str(minimum_burst(data[i])))

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


if __name__ == '__main__':
    solve()

复杂度分析

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

空间复杂度：除输入输出缓冲外为 $O(1)$；代码中的答案缓冲为 $O(T)$。

易错点

• $x$ 可以取 $0$ 或 $n$，不要错误地限制为两部分都为正数。
• 偶数 $n$ 的答案是 $0$，对应 $x=n/2$；公式也会自然得到 $0$。
• 不要枚举 $x$，因为 $n$ 可达 $10^{18}$。
• 应对 n + 1 求 lowbit，而不是对 n 求 lowbit。

第 3 题：旋转跳跃

题目描述

给定长度为 $n$、仅由小写英文字母组成的字符串 $s$，以及 $1$ 到 $n$ 的一个排列 $a_1,a_2,\ldots,a_n$。字符串下标从 $1$ 开始。

一次操作生成新字符串 $t$，其中对每个 $1\le i\le n$ 都有

随后用 $t$ 替换 $s$。不断重复同一操作，求字符串第一次恢复成初始字符串所需的最少正整数操作次数 $k$。由于 $k$ 可能非常大，输出 $k\bmod(10^9+7)$。

输入描述

第一行输入整数 $T$，表示测试数据组数，满足 $1\le T\le 2\times10^5$。

每组测试数据包含三行：

• 第一行输入整数 $n$，满足 $1\le n\le 2\times10^5$；
• 第二行输入长度为 $n$ 的小写字母字符串 $s$；
• 第三行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，它们构成 $1$ 到 $n$ 的排列。

保证单个测试文件中所有测试数据的 $n$ 之和不超过 $2\times10^5$。

输出描述

对每组测试数据输出一行一个整数，表示最少正操作次数对 $10^9+7$ 取模的结果。

样例

输入

3
5
abcde
2 3 1 5 4
4
aaaa
2 1 4 3
4
abab
2 3 4 1

输出

6
1
2

第一组的排列环为 $1\to2\to3\to1$ 与 $4\to5\to4$，对应字符序列的最小循环节分别为 $3$ 和 $2$，答案为 $\operatorname{lcm}(3,2)=6$。第三组虽然只有一个长度为 $4$ 的环，但环上字符是 abab，旋转 $2$ 位就会重合。

思路分析

1. 把多次操作写成排列复合

一次操作后，新位置 $i$ 的字符来自旧位置 $a_i$。连续执行 $k$ 次后，位置 $i$ 的字符来自初始位置 $a^k(i)$，因此恢复条件是

因为 $a$ 是排列，所有位置可拆成互不相交的置换环，每个字符只会在所属环内移动。

2. 每个环只需要字符序列的最小循环节

沿映射 $i\to a_i$ 遍历一个长度为 $L$ 的环，将初始字符依次记为

执行 $k$ 次后，该环恢复的条件为

这表示环上字符序列循环移动 $k$ 位后与自身相同。满足条件的最小正位移，正是该字符序列的最小循环节 $d$。之后所有可行位移都是 $d$ 的倍数。

注意 $d$ 不一定等于环长。例如 abab 所在环长度为 $4$，但最小循环节是 $2$。

3. 用 KMP 求最小循环节

对长度为 $L$ 的字符序列计算 KMP 前缀函数 prefix。候选周期为

只有当 $d_0\mid L$ 时，整个序列才能由长度为 $d_0$ 的模式完整重复得到。因此

4. 合并所有环的要求

若各环最小循环节为 $d_1,d_2,\ldots$，整个字符串同时恢复要求 $k$ 是每个 $d_i$ 的倍数，所以

真实的最小公倍数可能极大，不能先取模再计算 gcd 或 lcm，因为取模会破坏整除关系。

预处理不超过 $2\times10^5$ 的每个整数的最小质因子。把每个 $d_i$ 分解为

则最小公倍数为

只需记录每个质数出现过的最大指数，最后使用快速幂计算上式对 $10^9+7$ 的余数。

正确性证明

引理 1：执行 $k$ 次操作后，位置 $i$ 的字符为初始字符串的 $s_{a^k(i)}$。

证明：$k=1$ 时由操作定义成立。若执行 $k$ 次后结论成立，再执行一次，新位置 $i$ 读取此前位置 $a_i$ 的字符，即初始位置 $a^k(a_i)=a^{k+1}(i)$ 的字符。由归纳法得证。

引理 2：对于一个置换环，使环上字符恢复的最小正操作次数等于其字符序列的最小循环节 $d$。

证明：由引理 1，执行 $k$ 次等价于把环上字符序列循环移动 $k$ 位。序列恢复当且仅当对所有 $j$ 有 $c_{(j+k)\bmod L}=c_j$。根据循环节定义，满足该式的正位移恰为最小循环节 $d$ 的正倍数，其中最小者就是 $d$。引理得证。

引理 3：整个字符串在第 $k$ 次操作后恢复，当且仅当 $k$ 是所有环的最小循环节的公倍数。

证明：置换环互不相交。由引理 2，环 $i$ 恢复当且仅当 $d_i\mid k$。整个字符串恢复等价于所有环同时恢复，也就等价于每个 $d_i$ 都整除 $k$。引理得证。

定理：算法输出最少正操作次数对 $10^9+7$ 取模的结果。

证明：算法准确拆出全部置换环，并由 KMP 得到每个环字符序列的最小循环节。根据引理 3，最少操作次数是这些周期的最小公倍数。算法在质因数指数上逐质数取最大值，得到的恰是该最小公倍数的标准分解，最后才取模。因此输出正确。定理得证。

ACM Python 代码

import sys

MOD = 10 ** 9 + 7
MAX_N = 200000


def build_smallest_prime_factor(limit):
    spf = list(range(limit + 1))
    if limit >= 1:
        spf[1] = 1
    i = 2
    while i * i <= limit:
        if spf[i] == i:
            for multiple in range(i * i, limit + 1, i):
                if spf[multiple] == multiple:
                    spf[multiple] = i
        i += 1
    return spf


SPF = build_smallest_prime_factor(MAX_N)


def minimum_period(chars):
    length = len(chars)
    prefix = [0] * length

    for i in range(1, length):
        matched = prefix[i - 1]
        while matched > 0 and chars[i] != chars[matched]:
            matched = prefix[matched - 1]
        if chars[i] == chars[matched]:
            matched += 1
        prefix[i] = matched

    candidate = length - prefix[-1]
    if length % candidate == 0:
        return candidate
    return length


def solve_case(n, string, permutation):
    visited = [False] * n
    maximum_exponent = {}

    for start in range(n):
        if visited[start]:
            continue

        cycle_chars = []
        current = start
        while not visited[current]:
            visited[current] = True
            cycle_chars.append(string[current])
            current = permutation[current]

        period = minimum_period(cycle_chars)
        while period > 1:
            prime = SPF[period]
            exponent = 0
            while period % prime == 0:
                period //= prime
                exponent += 1
            if exponent > maximum_exponent.get(prime, 0):
                maximum_exponent[prime] = exponent

    answer = 1
    for prime, exponent in maximum_exponent.items():
        answer = answer * pow(prime, exponent, MOD) % MOD
    return answer


def solve():
    input = sys.stdin.buffer.readline
    test_count = int(input())
    answers = []

    for _ in range(test_count):
        n = int(input())
        string = input().strip().decode()
        permutation = [value - 1 for value in map(int, input().split())]
        answers.append(str(solve_case(n, string, permutation)))

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


if __name__ == '__main__':
    solve()

复杂度分析

令 $V=2\times10^5$，当前测试的字符串长度为 $n$。

时间复杂度：最小质因子筛预处理为 $O(V\log\log V)$，全局只执行一次；拆环与所有 KMP 计算的总长度均为 $n$，周期分解至多带来 $O(n\log n)$ 的宽松上界，因此单组为 $O(n\log n)$，所有测试为 $O(\sum n\log n)$。

空间复杂度：$O(V+n)$，包括最小质因子表、访问数组、KMP 数组和质因数指数表。

易错点

• 操作方向必须按 $t_i=s_{a_i}$ 理解；代码沿 $i\to a_i$ 拆环，并将输入排列转为零下标。
• 不能只取置换环长度。重复字符会让环提前恢复，必须对环上字符求最小循环节。
• KMP 得到的 $L-prefix[L-1]$ 只有整除 $L$ 时才是真正循环节，否则周期是 $L$。
• 不能对已经取模的数求最小公倍数；应先合并质因数最高指数，最后统一取模。
• 最小操作次数要求为正数。所有环周期均为 $1$ 时，答案应为 $1$，不是 $0$。
• 最小质因子表应只预处理一次，不能对最多 $2\times10^5$ 组数据反复筛表。

小结

• 平衡度划分中，切开一段不会增加贡献，因此整段不切就是最优方案。
• 最小爆发值由 $n$ 的二进制尾随连续 $1$ 决定，可用 lowbit(n + 1) - 1 常数时间计算。
• 旋转跳跃先把排列拆环，再求环上字符序列的最小循环节；所有周期的最小公倍数通过质因数最高指数安全合并。