容斥原理,是指在计数的时候,先不考虑重复问题,先把包含某种对象的统计出来,再把重复的排除掉。
比如说,考试,15人数学满分,12人语文满分,并且有4人语文和数学都满分,求至少有一个人满分的同学有多少个?
答案是15 + 12 - 4。
理解起来就是,重复的部分被多加了一次,最后再减去重复的人即可。
再如小于某个数x中,能被3或者5整除的数有多少?答案是 x/3 + x / 5 - x /3x5。同样是重复的计算了两次,减去一次即可。
容斥原理,不复杂,也不能单独用来求解问题,一般都是用于统计计数。
相关问题
题目 | 题解 | 说明 |
---|---|---|
878. 第 N 个神奇数字 | 题解 | |
1201. 丑数 III | 题解 | |
题解 |