大厂真题 / OPPO

OPPO 8.8 笔试真题 - 算法岗

本场考试概述

考试时间：2026年8月8日

考试岗位：算法岗

考试方向：编程题

难度评级：中等偏简单

本页收录考点：

• 第一题：字符串、线性扫描、端点选择（难度简单）
• 第二题：绝对值拆分、数学变形、极值预处理（难度中等）

建议策略：

• 第一题不要枚举子串。合法性只取决于首尾字符，因此最靠前和最靠后的幻觉字符一定构成最优区间
• 第二题先把绝对值拆成两个一次式，再把与核心位置无关的两个最大值预处理出来
• 两题均包含多组数据，且所有测试数据的总规模可达 $2\times 10^5$，应采用线性算法和快速读入

第 1 题：幻觉字符串

题目描述

将小写字母 o、大写字母 O 和数字 0 视为同一个字符，并把这三个字符统称为幻觉字符。

如果一个字符串以幻觉字符开头且以幻觉字符结尾，那么称它为幻觉字符串。字符串中间的字符没有任何限制；长度为 $1$ 的幻觉字符也同时满足开头和结尾条件。

给定一个由大小写字母和数字组成的字符串 $s$，求它的所有连续子串中，最长幻觉字符串的长度。如果不存在幻觉字符串，输出 $0$。

输入描述

第一行输入一个整数 $T$，表示测试数据组数，其中 $1\le T\le 2\times 10^5$。

每组测试数据包含两行：

• 第一行输入一个整数 $n$，表示字符串长度，其中 $1\le n\le 10^5$
• 第二行输入一个长度为 $n$ 的字符串 $s$，字符串仅由小写字母、大写字母和数字组成

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

输出描述

对于每组测试数据，输出一行一个整数，表示最长幻觉字符串的长度；若不存在则输出 $0$。

样例

输入

3
1
o
10
helloW0rld
10
aob0cOdoOo

输出

1
3
9

样例解释

• 第一组中，o 本身就是幻觉字符串，长度为 $1$
• 第二组中，幻觉字符只出现在第 $5$ 位 o 和第 $7$ 位 0，最长合法子串为 oW0，长度为 $3$
• 第三组中，最靠前的幻觉字符位于第 $2$ 位，最靠后的幻觉字符位于第 $10$ 位，取子串 ob0cOdoOo，长度为 $10-2+1=9$

思路分析

一个子串是否合法，只取决于它的第一个字符和最后一个字符是否属于集合 {o, O, 0}，中间字符完全不受限制。

设所有幻觉字符在原串中的下标集合为 $S$，下标从 $0$ 开始。若 $S$ 为空，显然无解，答案为 $0$。否则记：

任意合法子串 $s[i\ldots j]$ 的两个端点都必须是幻觉字符，因此 $i,j\in S$，必有：

所以它的长度满足：

另一方面，$s[l\ldots r]$ 的首尾恰好都是幻觉字符，因此它本身合法，并且长度正好达到这个上界。故只需在线性扫描中找到第一个和最后一个幻觉字符，答案就是 $r-l+1$。

正确性证明

下面证明算法输出的是最长幻觉字符串的长度。

若原串中没有幻觉字符，则任何非空子串都无法以幻觉字符开头并结尾，算法输出 $0$，结论正确。

若原串中存在幻觉字符，设最靠前和最靠后的幻觉字符下标分别为 $l$ 和 $r$：

1. 可行性：$s[l]$ 和 $s[r]$ 都是幻觉字符，因此子串 $s[l\ldots r]$ 是幻觉字符串，长度为 $r-l+1$
2. 最优性：对任意幻觉子串 $s[i\ldots j]$，其首尾下标都对应幻觉字符。由 $l$、$r$ 的定义，有 $l\le i\le j\le r$，所以 $j-i+1\le r-l+1$

算法构造出了长度为 $r-l+1$ 的合法子串，同时任何合法子串都不可能更长，因此算法输出的答案最优。

题解代码

import sys


MAGIC = {ord("o"), ord("O"), ord("0")}


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

    t = int(data[0])
    pos = 1
    answers = []

    for _ in range(t):
        n = int(data[pos])
        s = data[pos + 1]
        pos += 2

        first = -1
        last = -1
        for i, ch in enumerate(s):
            if ch in MAGIC:
                if first == -1:
                    first = i
                last = i

        answers.append("0" if first == -1 else str(last - first + 1))

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


if __name__ == "__main__":
    solve()

复杂度分析

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

时间复杂度：$O(N)$，每个字符只被扫描一次。

空间复杂度：算法本身的额外空间为 $O(1)$；若计入一次性读入的输入和输出缓冲区，则为 $O(N+T)$。

易错点

• 幻觉字符恰好是小写字母 o、大写字母 O 和数字 0，不要混淆字母与数字
• 中间字符没有限制，不需要判断子串内部是否全部为幻觉字符
• 只有一个幻觉字符时，它本身就是长度为 $1$ 的合法子串
• 完全没有幻觉字符时应输出 $0$，不能用未初始化的左右端点计算长度
• 不要枚举所有子串或所有端点对，否则最坏会达到 $O(n^2)$

第 2 题：防风核心

题目描述

在数轴的整数坐标 $1,2,\ldots,n$ 上依次种植着 $n$ 棵树苗，第 $i$ 棵树苗至少需要 $a_i$ 的防风值才能存活。

你可以且仅能在某个整数坐标 $p$ 建立一个能量为非负整数 $P$ 的防风核心，其中 $1\le p\le n$。核心对坐标 $i$ 处树苗提供的防风值为：

为了使所有树苗存活，需要对每个 $1\le i\le n$ 满足：

等价地，当核心放在 $p$ 时，能量至少为：

请最优地选择放置位置 $p$，求能够保护所有树苗存活的最小核心能量 $P$。

输入描述

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

每组测试数据包含两行：

• 第一行输入一个整数 $n$，表示树苗数量，其中 $1\le n\le 2\times 10^5$
• 第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $0\le a_i\le 10^9$

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

输出描述

对于每组测试数据，输出一行一个整数，表示最优放置防风核心时所需的最小能量 $P$。

样例

输入

2
5
2 1 4 2 3
3
10 0 10

输出

5
11

样例解释

第一组把核心放在 $p=4$ 时，各树苗对能量的要求 $a_i+\lvert i-p\rvert$ 依次为：

最大值为 $5$，且不存在能让最大值更小的放置位置，因此答案为 $5$。

第二组把核心放在 $p=2$ 时，各树苗对能量的要求依次为：

最大值为 $11$，所以答案为 $11$。

思路分析

固定核心位置 $p$ 后，所需的最小能量是：

直接枚举 $p$，再扫描所有树苗计算最大值，会产生 $O(n^2)$ 的时间复杂度。关键是拆开绝对值：

因此：

再对所有 $i$ 取最大值。定义两个与 $p$ 无关的量：

则：

只需扫描数组一次求出 $R$、$L$，之后枚举 $p=1,2,\ldots,n$，每个位置用 $O(1)$ 时间计算 $f(p)$，取其中最小值即可。两次线性扫描的总复杂度仍为 $O(n)$。

其中 $R-p$ 随 $p$ 增大而减小，$L+p$ 随 $p$ 增大而增大。虽然还可以利用两式交点只检查附近的整数位置，但直接枚举全部 $n$ 个位置已经满足线性复杂度，也更不容易出现取整或边界错误。

正确性证明

设算法预处理得到：

对任意合法放置位置 $p$，有：

所以算法对每个 $p$ 计算出的 need，恰好等于核心放在该位置时保护全部树苗所需的最小能量，而不是近似值。

题目允许的位置恰好是所有整数 $p\in[1,n]$。算法逐一枚举了这个集合中的每个位置，并取对应 need 的最小值，因此不会遗漏任何可行位置。故最终输出值等于：

即题目要求的最小防风核心能量。

题解代码

import sys


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

    t = data[0]
    pos = 1
    answers = []

    for _ in range(t):
        n = data[pos]
        pos += 1

        right_max = -10**30  # max(a_i + i)
        left_max = -10**30   # max(a_i - i)

        for i in range(1, n + 1):
            value = data[pos]
            pos += 1
            right_max = max(right_max, value + i)
            left_max = max(left_max, value - i)

        best = 10**30
        for p in range(1, n + 1):
            need = max(right_max - p, left_max + p)
            best = min(best, need)

        answers.append(str(best))

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


if __name__ == "__main__":
    solve()

复杂度分析

设所有测试数据的树苗数量之和为 $N$。

时间复杂度：$O(N)$。每组数据扫描 $a_i$ 一次并枚举核心位置一次。

空间复杂度：算法本身的额外空间为 $O(1)$；若计入一次性读入的整数数组和输出缓冲区，则为 $O(N+T)$。

易错点

• 树苗坐标从 $1$ 开始，计算 $a_i+i$ 和 $a_i-i$ 时不要误用从 $0$ 开始的数组下标
• 核心只能放在整数坐标 $1$ 到 $n$，不能直接把连续函数交点当成合法位置
• 拆分后是 $R-p$ 与 $L+p$，两个符号不要写反
• 对所有 $i$ 取最大值后，结果是 $\max(R-p,L+p)$，不是两项之和
• 即使所有 $a_i=0$，当 $n>1$ 时答案通常也不为 $0$，因为核心能量还需覆盖距离损耗
• 在固定宽度整数语言中，建议使用 64 位整数保存中间结果和答案

知识点总结

这两题都不依赖复杂数据结构，重点是识别目标函数中真正影响答案的信息。第一题把子串问题压缩为两个端点，第二题把每个位置对全部树苗的评估压缩为两个全局最大值；完成这两步后，都可以在线性时间内解决。