2026 华为OD机试真题 8月9日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

小明设计了一条灯带，该灯带中共有 16 盏灯（编号 到 15），每盏灯有两种颜色：红色（用字符 R 表示）和绿色（用字符 G 表示）。每过一秒，灯带中的灯都会按照以下规则进行一次颜色变换：

1. 如果上一秒灯 lights[i] 的两个相邻灯 lights[i-1] 和 lights[i+1] 颜色一致，则灯 lights[i] 在当前秒需要设置为绿色。
2. 其他场景（相邻灯颜色不一致、或灯只有单一邻居），则该灯在当前秒需要设置为红色。

注意：灯带中编号为 的灯和编号为 15 的灯是不相邻的（线性灯带，首尾不相连）。因此编号 的灯只有右邻居，编号 15 的灯只有左邻居。

给定一个灯带的初始状态，请你输出 t 秒后灯带中各灯的颜色。

2026 华为OD机试真题 8月9日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

输入描述

单行输入，格式为：

"lights",t

其中 lights 为用英文双引号包围的长度为 16 的字符串，t 为整数。两者用逗号分隔。

输出描述

输出一个用英文双引号包围的长度为 16 的字符串。

• lights 长度固定为 16。
• lights 中每个字符为 R 或 G。
• 1 <= t <= 10000000。

示例1

输入

"RRRRRRRRRRRRRRRR",1

输出

"RGGGGGGGGGGGGGGR"

示例2

输入

"RRRRRRRRRRRRRRRR",2

输出

"RRGGGGGGGGGGGGRR"

示例3

输入

"RGGGRGGGRGGGRGGG",1

输出

"RRGRGRGRGRGRGRGR"

解题思路

核心思想

灯带长度固定为 16，可以用一个 16 位整数表示状态：R=0，G=1。每次变换只看左右邻居是否相同，边界灯没有两个邻居，所以必定变为红色。由于状态最多只有 2^16 种，当 t 很大时一定会出现循环，可以记录每个状态首次出现的秒数并快速跳转。

算法步骤

1. 将初始灯带字符串转为 16 位整数状态。
2. 用 seen 记录状态首次出现时间，用 history 保存历史状态。
3. 每一秒根据上一状态计算下一状态：
   • 位置 和 15 保持为红色；
   • 位置 1 到 14 若左右邻居颜色一致，则设为绿色。
4. 若新状态曾经出现过，根据循环长度跳过剩余秒数。
5. 将最终整数状态还原为 16 位灯带字符串并加双引号输出。

复杂度分析

状态数最多 2^16，灯带长度固定为 16。

• 时间复杂度：O(min(t, 2^16) * 16)，可视为常数级。
• 空间复杂度：O(2^16)，用于记录状