1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

解题思路

设彩灯颜色在集合 {1,2,3,4,5} 上循环。按某个节点一次,会使该节点及其整棵子树的颜色都加 1(模 5)。

把颜色映射为 0…4 更便于计算:令 c0 = c - 1,则每次点击相当于对子树的颜色 “+1(mod 5)”。 若从根到当前节点一共累计了 inc 次加 1(mod 5),则当前节点颜色为 (initial0 + inc) % 5。要让它变成 target0,最少还需在当前节点再按

d = (target0 - initial0 - inc) mod 5   (取 0..4 之间)

P3848.第2题-挂满彩灯的二叉树

    1000ms Tried: 78 Accepted: 37 Difficulty: 5 所属公司 : 拼多多
    算法与标签>贪心算法

题目内容

圣诞节快到了,有一棵挂满彩灯的二叉树,需要你来按照图纸装饰。彩灯有 555 种颜色变化,分别用 1−51-51−5 表示。

111 表示红色,222 表示黄色,333 表示蓝色,444 表示紫色,555 表示绿色。

每个节点都一个颜色控制器,每按一下,就会将当前彩灯以及以当前节点为根节点的子树上的所有节点,切换到下一个颜色(红->黄 ->蓝->紫>绿->红...)循环切换。

给定二叉树的初始状态 initialinitialinitial 和 目标状态 targettargettarget ,两者都以层序遍历产出的一维数组表示。数组元素对应对应位置节点的颜色,000 表示该节点没有彩灯。

请给出从 initialinitialinitial 状态切换至 targettargettarget 状态需要的最少控制器点击次数。

注意: 控制器按一下,不只影响当前节点,也会影响以当前节点为根节点的子树上所有节点切换到下一个颜色(最终不一定是同一个颜色)。

输入描述

第一行输入为一个整数 nnn ,代表 intialintialintial 和 targettargettarget 数组的大小。

第二行输入为 nnn 个整数,代表 initialinitialinitial 数组。

第三行输入为 nnn 个整数,如果 initial[i]==0initial[i]==0initial[i]==0 , 则 targt[i]targt[i]targt[i] 也一定为 000 。

1<=initial.length<=1061 <=initial.length <= 10^61<=initial.length<=106

输出描述

一个整数,表示最少点击次数

样例1

输入

5
1 2 3 0 1
2 3 1 0 2

输出

3

样例2

输入

7
1 2 3 1 2 3 1
3 1 2 3 1 2 1

输出

10

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 2, 38ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?