acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 状压DP

    userId_undefined
    瀚高祖
    题解仙人时间刺客空间掌握者时空双修者秩序白银
    1阅读
    0回复
    0点赞
  • T13:GEPPETTO

    解题思路 把每种原材料看成一个点,冲突看成一条边。 一份披萨就是选择一些原材料的集合,要求集合里任意两种原材料不冲突,也就是图中的一个独立集。 题目问“最多能做多少种不同披萨”,等价于: * 统计这个图一共有多少个独立集(包含空集) 因为 N ≤ 20,可以直接用二进制枚举所有子集,判断是否为独立集即可。 做法 1. 用 ban[i] 记录与 i 冲突的点集合(一个 bitmask)。 2. 枚举所有子集 mask(0 到 2^N - 1)。 3. 判断 mask 是否为独立集: 可以用“逐个取出 mask 中的点”来检查是否出现冲突: * 取出一个点 v * 如果 mask 里还包含 ban[v] 里的点,则冲突,失败 4. 统计通过的子集数量。 复杂度大约是 O(N * 2^N),N=20 时大约两千多万次操作,1 秒一般能过。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C++ 代码(普通数组版)

    userId_undefined
    知予
    倔强青铜
    0阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页