1 条题解

  • 0
    @ 2026-11-15 13:33:24

    题目分析

    30 分

    各种暴力搜索都行。

    链

    发现每次操作相当于是在染一个后缀。

    于是考虑从左往右染,如果 ci=ci−1c_i=c_{i-1} 说明 ii 不需要再染,否则就需要重新染。

    菊花

    注意到先染节点 11 一定最优,然后一次检查其他点与节点 11 颜色是否相同,不同就重新染。

    正解

    根据链和菊花的解法受到启发,发现对于树的情况从上往下染即可,即 cu=cpuc_u=c_{p_u} 说明不需要再染,否则就重新染。

    • 1

    信息

    ID
    65
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者