1 条题解

  • 0
    @ 2026-11-15 21:09:44

    40pts

    一共只有 33 个点,手动讨论两个人的选择情况,时间复杂度为 O(1)O(1)。

    80pts

    考虑 f[S][T]f[S][T] 表示 Alice 目前把 SS 集合染成了黑色,Bob 目前把 TT 集合染成了白色两人采取最优策略的最终答案。

    如果为 Alice 的回合,一定选所有后继状态中的最大值,如果为 Bob 的回合,一定选后继状态的最小值,每个点只有黑色/白色或还未被染色,时间复杂度不超过 O(3n)O(3^n)。

    100pts

    如果一条边最终不是黑边也不是白边,我们看成两人分别得到了这条边边权的一半。

    所以把每个点的点权看作所有邻边的边权之和的一半,按照点权两人从大到小依次取即为最优策略。

    • 1

    信息

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