首页 > 宝石装箱

Lskkkno1

发表于 2020-05-22 22:00:21

宝石装箱题目描述有个带标号盒子和球，每个球都有一个盒子不能放进去（不一定是排列）。问每一个盒子里都有一个球的方案数。正解每一个球都有一个限制（一个盒子不能放）。这个问题类似于错排，而错排有一种容斥的解法。设表示至少有条限制不满足的方案数, 表示恰好有条限制不满展开全文

lalalaterraria

发表于 2020-05-23 12:10:29

这里给出一种容斥+多项式的做法复杂度为是n^2/2 大家一般是容斥+背包啊，我觉得这里多项式也蛮好写的。容斥应该不用多说了，设为第i个球合法的情况。套一套下面两个公式。我们要求的是第二个公式的左半，用第一个公式带入第二个公式的右边第二项。所得公式的右半边从左向右数第i项(不考虑符号)，表展开全文

氧气少年Kevin

发表于 2022-06-21 11:14:11

牛客5633D - 宝石装箱链接：https://ac.nowcoder.com/acm/contest/5633/D 知识点：线性容斥、背包DP 难度：蓝题意将 nnn 个物品装进 nnn 个箱子，每个箱子恰好装一个物品。要求第 iii 个物品不能装入第 aia_iai 个箱子展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛