浅析容斥原理
容斥原理，它的核心内容我觉得只能是代表一种逆向思维，并不是某一种固定得算法。它是把所有可能得情况先一并汇总，然后在一般情况下，对于问题的求解，汇总得解空间里面肯定是有重复部分得，然后我们可以把这个重复得部分当作斥从解空间中去除，那么我们就得到了最后的答案。
比如：前缀和求区间问题或者是特定排列的问题
对于前者，我们一般被询问到区间[l,r]，而我们直接把一到r这个区间的数全部加起来，最后减去斥的[1,l-1]这个区间的数就可以了。
对于后者，最简单的例子，如果我们有 n 个的成绩数据，要求所有不小于 m 分的人的总个数，这是一个简单的统计问题，我们直接统计全部大于 m 分的人数即可，这里就运用到了 不小于 的相反面去逆向解决问题。
在以后做题中可以多利用这种思想去为自己的代码剪枝或者简化问题，特别是给出条件摸棱两可或繁冗的。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！