宽容原则(二进制枚举法)
在计数时,必须注意无一重复,无一遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。
两个集合的容斥关系公式:A∪B = A+B – A∩B (∩:重合的部分)
三个集合的容斥关系公式:A∪B∪C = A+B+C – A∩B – B∩C – C∩A +A∩B∩C
详细推理如下:
1、 等式右边改造 = {[(A+B – A∩B)+C – B∩C] – C∩A }+ A∩B∩C
2、文氏图分块标记如右图图:1245构成A,2356构成B,4567构成C
3、等式右边()里指的是下图的1+2+3+4+5+6六部分:
那么A∪B∪C还缺部分7。
4、等式右边[]号里+C(4+5+6+7)后,相当于A∪B∪C多加了4+5+6三部分,
减去B∩C(即5+6两部分)后,还多加了部分4。
5、等式右边{}里减去C∩A (即4+5两部分)后,A∪B∪C又多减了部分5,
则加上A∩B∩C(即5)刚好是A∪B∪C。
在这里我要说的是一个二进制枚举。
正文
所谓二进制枚举 就是一种暴力的方式,用0,1来代表一个数字存在或不存在。
例如 0101 可以理解为 第一个物品要了,第二个不要,第三个要了,第四个不要。
那么这个和容斥原理有什么关系呢?
我们都知道容斥原理的公式为:
可能很多刚刚接触的小伙伴不太了解,其实有很多的问题需要容斥来解决,我举一个例子:
如果求100以内的除了 2的倍数 和 3的倍数的数 有多少个,我们可以很容易知道 2的倍数的个数是100/2,而3的倍数是100/3,“答案“是100-50-33 = 17
这显然是不对的 以6为例 6既是2的倍数也是三的倍数,显然减重了。 但是我们有人就要说了,我可以每个数都判断一下。
#include<iostream>
using namespace std;
int main(){
int ans = 0;
for(int i = 1;i<+100;i++){
if(i%2==0 || i%3==0){
ans++;
}
}
cout<<ans<<endl;
}
但是,当n很大的时候,要O(n)时间复杂度。显然是不符合实际的。
这里我先引入容斥原理的概念
我们回到刚才的那个问题,我们有没有办法解决减重的情况?
这里我们就要运用容斥原理解决这个问题了,
100-2的倍数-3的倍数+6的倍数
减重复的加回来就好了,这个6是二和三的最小公倍数
好了这个问题我们已经很好的解决了,但是我们真的解决问题了吗?
我们在举一个例子 :
100以内的数 求 2 3 5 7 11 的倍数,我们还是用刚才方法,
2的倍数+3的倍数+5的倍数+7的倍数+11的倍数- 。。。。。。。
这个时候我们犯难了 要减的有2∩3,减2∩5......还要加回减多的2∩3∩5.....
太麻烦了,明明这么简单的一道题,怎么解决?
这里我们就要引入二进制枚举的概念了:
根据上面的公式:
上面的公式有2^m-1种情况。
我们把二进制表示2,3,5,7,11五个数。为什么可以这样呢?
这就是二进制枚举的好处了。因为有5个数,所以5个数组成的倍数有2^5-1种。
比如2的倍数:我们表示为00001
2∩3的倍数:00011
5∩11的倍数:10100
就是说,1~2^5每一个二进制位(0表示没选,1表示选定)表示2,3,5,7,11的选不选定。初学者还是有点难理解的,认认真真看代码,看是怎么实现的,花点时间认真弄明白。
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int a[] = {2,3,5,7,11};
int main(){
int n;
int lena = 5;
while(~scanf("%d",&n)){
int ans = 0;
for(int i = 1;i<(1<<lena);i++){
///每个数都有2种状态 ,在或不在 在本题中的意思是2,3,5,7,11的倍数或不是,
///一共有2^5-1种可能
int tmp=0;
int lcm=1;
for(int j = 0;j<lena;j++){
if((1<<j)&i){///选第j个b倍数子;与i的二进制的第j位比较,看是否为1,是则选中
tmp++;//标志变量计算i中1的个数,也就是倍数的个数
lcm*=a[j];///相乘
}
}
if(tmp%2==1) ans+=n/lcm; //奇数是加 偶数是减
else ans-=n/lcm;printf("%d\n",ans);
}
cout<<ans<<endl;
}
}
简单应用:
由0 到9 数字组成排列,要求第一个数大于1,最一个数小于8,一共有几种排列。
思路:
求逆问题,第一个数<=1,最后一个数>=8
由容斥原理,
则有 事件A(第一个数<=1) = 2*9!, 事件B(最后一个数>=8) = 2*9!, 事件C(A交B) C= 2*2*8!
所以逆问题的结果是 A+B-C
则问题的答案是 10!-(A+B-C)。
经典例题:
例题1:
给出一个数N,求1至N中,有多少个数不是2 3 5 7的倍数。 例如N = 10,只有1不是2 3 5 7的倍数。
- 1
- 2
Input
输入1个数N(1 <= N <= 10^18)。
Output
输出不是2 3 5 7的倍数的数共有多少。
Sample Input
10
- 1
- 2
Sample Output
1
- 1
- 2
包含排斥原理,就是那道公式。
四个圆圈的并,是四个的单独面积的总和,减去四个分别两两相交的两层的面积,加上四个分别三三相交的三层的面积,再减去四个相交的面积。最后就是并了。这道题,也是这个意思,只不过数多一点。
#include<stdio.h>
int main(){
long long num=0,n,a,b,c,d,ab,ac,ad,bc,bd,cd,abc,abd,acd,bcd,abcd;
scanf("%lld",&n);
a=n/2;
b=n/3;
c=n/5;
d=n/7;
ab=n/6;
ac=n/10;
ad=n/14;
bc=n/15;
bd=n/21;
cd=n/35;
abc=n/30;
abd=n/42;
acd=n/70;
bcd=n/105;
abcd=n/210;
num=a+b+c+d-ab-ac-ad-bc-bd-cd+abc+abd+acd+bcd-abcd;
printf("%I64d\n",n-num);
}
这次还有就是看数据量可不可以暴力过,可以的话,直接暴力就解决了。这就是考察你会不会进行估算。
自己可以用二进制枚举写一下。
上一篇: 基础数学] 容差原理
下一篇: 如何实施小火箭 ios 的具体步骤