树形图计数之容斥原理练习题

时间：2022-07-13 06:38:21 其他范文收藏本文下载本文

下面就是小编给大家整理的树形图计数之容斥原理练习题，本文共3篇，希望您能喜欢！

树形图计数之容斥原理练习题

篇1：树形图计数之容斥原理练习题

树形图计数专题之容斥原理练习题

1.十一中学图书馆有中、外文科技和文艺图书6000册，其中中文书4560册，文艺书3060，外文科技书840册。问：一共有多少本外文书?有多少本中文文艺书?

2.某小学的统计数字表明：学校共有学生1200名，其中男生650名，高年级学生300名，三好学生100名，男生中的三好学生60名，高年级学生中男生160名，高年级女生中三好学生20名，非高年级女生中不是三好学生的400名。试证明：这个统计数字一定有错误。

3.学校举行棋类比赛，设象棋、围棋和军棋三项，每人最多参加两项。根据报名的人数，学校决定对象棋的前六名、围棋的前四名和军棋的前三名发放奖品。问：获奖人数最多为几人?最少为几人?

4.试求：在1000以内(含1000)的自然数中，不能被3、5、8任何一个整除的数的个数。

5.在前200个自然数中，能被2或3或5整除的有多少个?

6.在1到10000这10000个自然数中，即不能被8整除也不能被125整除的数有多少个?

7.以105为分母的最简真分数共有多少个?

8.全班有25个学生，其中17人会骑自行车，13人会游泳，8人会滑冰，这三个运动项目没有人全会。至少会这三项运动之一的学生数学成绩都及格了，但又都不是优秀。如果全班有6个人数学不及格，问：(1)全班数学成绩优秀的有几名?(2)全班有几个人即会游泳又会滑冰?

9.二年一班共42名同学，其中少先队员33人。这个班男生20人，女生中有4人不是少先队员，求男生中有多少人是少先队员。

10.某班有学生46人，在调查他们家中是否有电子琴和小提琴时发现，有电子琴的22人，两种琴都没有的14人，只有小提琴的与两种琴都有的人数之比是5∶3。问：只有电子琴的有多少人?

11.课堂上同学们都在复习语文或数学，只复习语文的占48%，只复习数学的是只复习语文的人数的50%。问：两门功课都复习了的人数占总数的百分之几?

12.全班45人每人都订了《少年报》或《学与玩》，已知有2/3的人订了《少年报》，有5/9的人订了《学与玩》，求只订《学与玩》的.人有多少?

13.某工厂一季度有80%的人全勤，二季度有85%的人全勤，三季度有95%的人全勤，四季度有90%的人全勤。问：全年全勤的人至多占全厂人数的百分之几?至少占百分之几?

14.一次数学测验，甲答错了题目总数的1/4，乙答错了3道题，两人都答错的题目是题目总数的1/6。求甲、乙都答对的题目数。

15.一次数学速算练习，甲答错题目总数的1/9，乙答对7道题，两人都答对的题目是题目总数的1/6。问：甲答对了多少道题?

16.某年级60人中有2/3的同学爱打乒乓球，3/4的同学爱踢足球，4/5的同学爱打蓝球，这三项运动都爱好的有22人。问：这个年级最多有多少人这三项运动都不爱好?

17.某班共有学生48人，其中27人会游泳，33人会骑自行车，40人会打乒乓球。那么，这个班至少有多少学生这三项运动都会?

篇2：计数之加法原理练习题

最新计数专题之加法原理练习题

小格纸(如图)上有一只小虫,从直线AB上一点O出发,沿方格纸上的横线或竖线爬行.方格纸上每小段的'长为1厘米.小虫爬过若干小段后仍回到直线AB上,但不一定回到O点.如果小虫一共爬过3厘米,那么小虫爬行路线有多少种?

当小虫第一步向上爬行时,第二步有三个可行的方向:向下、向左或向右.若第二步向下,则第三步有左、右两个方向;若第二步向左或向右,则第三步都只能向下.故共有2+1+1=4(种)路线.显然小虫第一步向下爬行也有4种路线.

当小虫第一步向左爬行时,它的第二步可以有四个方向.当它第二步向上或向下时,第三步只能向下或向上一种选择;当它第二步向左或向右时,都还有向左向右两种选择.故一共有2+22=6(种)路线.显然当小它第一步向右爬行时,也有6种路线.

综上所述,小虫可以选择路线一共有42+62=20(种).

篇3：hdu 5212（容斥原理）

Code

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 77 Accepted Submission(s): 27

Problem Description WLD likes playing with codes.One day he is writing a function.Howerver,his computer breaks down because the function is too powerful.He is very sad.Can you help him?

The function:

int calc

{

int res=0;

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

{

res+=gcd(a[i],a[j])*(gcd(a[i],a[j])-1);

res%=10007;

}

return res;

}

Input There are Multiple Cases.(At MOST10)

For each case:

The first line contains an integerN(1≤N≤10000).

The next line containsNintegersa1,a2,...,aN(1≤ai≤10000).

Output For each case:

Print an integer,denoting what the function returns.

Sample Input

51 3 4 2 4

Sample Output

64Hintgcd(x,y) means the greatest common divisor of x and y.

Source BestCoder Round #39 ($)

Recommend hujie | We have carefully selected several similar problems for you: 5213 5209 5208 5205 5204

给你一个a数组，让你计算那段代码的结果，用容斥原理就ok，莫比乌斯反演也行，不过不会莫比乌斯反演（也是容斥原理）orz，

hdu 5212（容斥原理）

，

。。改天学习下。

代码如下：

#include#include#include#include#include#includeusing namespace std;typedef long long ll;const int maxn = 1e4 + 10;const ll mod = 10007;#define rep(i,a,b) for(int i=(a);i<(b);i++)#define pb push_backint cnt[maxn],a[maxn];ll d[maxn];int main(){ int n; while(~scanf(“%d”,&n)) {int Mgcd = 1;for(int i = 0; i < n; i++) { int x; scanf(“%d”,&x); Mgcd = max(Mgcd,x); a[i] = x;}memset(cnt,0,sizeof(cnt[0])*Mgcd+20);for(int i = 0; i < n; i++)cnt[a[i]]++;ll ans = 0,res = 0;/*d[i]表示任取两数gcd为i的方案数*/for(ll i = Mgcd; i > 0; i--) { ll tot = 0; for(ll j = i; j <= Mgcd; j+= i) { tot += cnt[j]; d[i] = (d[i]-d[j])%mod;/*减去gcd为i的倍数的方案数(容斥原理)*/ } /*gcd为i的方法数等于任选两个数(可重)是i的倍数的方案除去gcd为i的倍数的情况(前面已经减掉了)*/ d[i] = (d[i] + tot*tot)%mod; ans = (d[i]*i*i)%mod; res = (res+i*d[i])%mod;}cout<<((ans-res)%mod+mod)%mod<

★抽屉原理练习题

★分类加法计数原理与分步乘法计数原理的说课稿