夜雨聆风写在前面
本次给大家带来2026年8月6日百度算法笔试题的3道题，本场机考题目均可在咱们平台上在线刷题。
第一题：扫一遍取全局最大最小，答案就是「极差 × 长度」——切开任何一段都不会更优
第二题：均分额度后做一次异或即可得到最小对冲值（偶数直接为 0）。
第三题：把排列拆成若干环，对每个环求字符串转回原样的最短步数，再对所有环的步数取最小公倍数并取模。
塔子哥的配套刷题网站:codefun2000.com
第1题-波动贡献最大化
题目内容
运维侧拿到一条长度为 的整型指标序列 ，需要按连续子段做汇总评估。要求子段非空、首尾相接且覆盖整条序列，并使所有子段的「波动贡献」之和尽量大。对子段 ，其长度为
波动贡献定义为
请给出可达到的最大总和。
输入描述
首先一行：序列长度 。
随后一行： 个整型值构成的列表 。
输出描述
写出一个非负整型结果，表示该序列划分下能得到的最大总价值。
样例1
输入
32 5 1输出
12说明
将整段 作为一个子段：长度为 ，最大值为 ，最小值为 ，波动贡献为 ，即为最优总价值。
样例2
输入
41 5 2 4输出
16说明
将整段 作为一个子段：长度为 ，最大值为 ，最小值为 ，波动贡献为 ，即为最优总价值。
题解
解题思路
本题考查对区间贡献函数的上界分析与一次性观察，不必真的做区间 DP。
设全局最大值为 ，全局最小值为 。将整条序列作为一个子段时，贡献为 对任意合法划分，每一段 都有因此该段贡献不超过 。把各段相加，总贡献不超过 上界可被「整段不切」取到，故最优答案恒为 。实现时扫一遍数组求 即可。
常见假解：
写出区间 DP / 单调栈等复杂划分，常数或复杂度吃不消（正解只需 ）； 答案只输出 ，漏乘长度 ； 用 位整数计算 ，在 与 同时偏大时溢出； 误以为切开「尖峰」更优：切开后各段极差更小，总和不会超过整段。
复杂度分析
时间复杂度：，单次遍历求最值。 空间复杂度： 额外空间（不计读入数组）。
代码实现
python代码(C++和JAVA代码见在线OJ网址)
defmax_fluctuation(n: int, v: list[int]) -> int:# 整段作为唯一子段即可达到上界 (max-min)*nreturn (max(v) - min(v)) * ndefmain() -> None: n = int(input()) v = list(map(int, input().split())) print(max_fluctuation(n, v))if __name__ == "__main__": main()第2题-最小对冲值
题目内容
调度模块要把一个非负整型额度 拆成两份：任选整型 （），另一份为 。定义这次拆分的「对冲值」为
其中 为按位异或（对应二进制位相同得 、不同得 ）。例如 与 满足 。现给定若干个额度，请对每个 求出可取到的最小对冲值。
输入描述
第一行一个整型 ，表示随后有 行额度。
接下来 行，每行一个整型 。
请对每个 逐一计算其最小对冲值。
输出描述
共输出 行；对于每一个 ，写出一个非负整型，即
样例1
输入
34511输出
013说明
三个额度依次为 ：取 时 ；取 时 ；取 时 。
样例2
输入
227输出
07说明
额度 ：取 得 。额度 ：枚举可知最小对冲值为 。
题解
解题思路
本题考查位运算恒等式与对「拆分后异或」的一次观察，不必对每个 枚举 。
设 ，，则 ，且目标为 利用恒等式可得因此最小化异或等价于最大化 。 取 （即尽量均分）时， 达到最大。于是答案为 特例：当 为偶数时，，答案恒为 ；当 （二进制全 ）时，任意拆分都有 ，答案为 本身。
常见假解：
对每个 暴力枚举 （ 直接超时）； 误以为答案恒为 的最低位 （对 会得到 ，正确为 ）； 只处理偶数得 ，奇数直接输出 （漏掉 等更大答案）； 用 位整数读 （ 可达 ）。
复杂度分析
时间复杂度：，每个额度 计算。 空间复杂度： 额外空间。
代码实现
python代码(C++和JAVA代码见在线OJ网址)
defmin_hedge(m: int) -> int:# 均分后异或即为最小对冲值return (m // 2) ^ ((m + 1) // 2)defmain() -> None: n = int(input())for _ in range(n): m = int(input()) print(min_hedge(m))if __name__ == "__main__": main()第3题-报文置换归位
题目内容
报文流水线按固定置换反复重排字符串。给定长度为 的字符串 ，以及长度为 的排列 （下标从 开始）。一次操作生成等长新串 ：对每个位置 （）有 ，再令 。无限重复该操作，求最少的正整数次数 ，使字符串回到最初形态；输出 。
长度为 的排列：由 各出现恰好一次构成的序列。例如 是长度为 的排列；而 不是（元素 出现两次， 未出现）， 也不是（出现了超出 范围的 ）。
输入描述
第一行一个整型 。
第二行一个长度为 、仅含小写字母的字符串 。
第三行 个整型，给出排列 。
输出描述
新起一行写出一个非负整型，即最少操作次数对 取模后的结果。
样例1
输入
2xy2 1输出
2说明
排列形成循环 。操作一次得到 yx，再操作一次回到 xy，故 。
样例2
输入
3zzz2 3 1输出
1说明
排列为循环 ，但三位字母相同，操作一次后仍为 zzz，故 。
样例3
输入
5hello2 3 4 5 1输出
5说明
排列为单一循环 ，字符串五位在循环上两两不同，需操作 次才回到 hello。
题解
解题思路
本题考查排列的环分解与字符串最小周期，答案是各环贡献的最小公倍数。
一次操作把位置 上的字符换成原串位置 上的字符。反复操作等价于沿置换 的函数图移动。 将 拆成若干互不相交的环。对长度为 的环，环上字符形成一个长度为 的圆串；操作一次相当于把圆串旋转一格。 该环恢复原状的最小正旋转步数，等于圆串的最小周期 ：在整除 的因子中，找最小的 ，使环上字符串由长度为 的块重复 次得到。若环上字符全相同，则 。 整串恢复当且仅当每个环都恢复，故总次数 为所有环的 的最小公倍数。输出 。注意 可能远超 位，需用高精度或质因数分解累乘取模。
常见假解：
直接对环长取 LCM，忽略环上字符串自身周期（如全相同字符时答案应为 ）； 只取最长环长度； 用 位整数直接累乘 LCM 导致溢出； 把「已经不变」误判为 次（题目要求最少正整数次数）。
复杂度分析
时间复杂度： 量级（遍历环；对每个环长 检查约 个因子并 验证，总和可接受）；取 LCM 时质因数分解或高精度另计。 空间复杂度：。
代码实现
python代码(C++和JAVA代码见在线OJ网址)
import mathMOD = 10**9 + 7defcycle_period(chars: list[str]) -> int:# 环上字符串的最小正旋转周期 m = len(chars)for d in range(1, m + 1):if m % d != 0:continueif all(chars[i] == chars[i % d] for i in range(m)):return dreturn mdefsolve(n: int, u: str, p: list[int]) -> int: vis = [False] * n ans = 1for i in range(n):if vis[i]:continue cycle = [] x = iwhilenot vis[x]: vis[x] = True cycle.append(u[x]) x = p[x] per = cycle_period(cycle) ans = ans // math.gcd(ans, per) * per # 高精度 LCMreturn ans % MODdefmain() -> None: n = int(input()) u = input().strip() p = [int(x) - 1for x in input().split()] print(solve(n, u, p))if __name__ == "__main__": main()
