[原创]容斥原理习题

2017-02-11 23:09:40 Tabris_ 阅读数:981


博客爬取于2020-06-14 22:41:37
以下为正文

版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54989141


练习题目VJ:https://vjudge.net/contest/77876#overview

HDU 1796 How many integers can you find

戳这里

HDU 1685 Booksort

这题应该是整错了 不是容斥原理,看题解都是IDA*搜索

HDU 2204 Eddy’s爱好

戳这里

HDU 4407 Sum

对于替换的先不管 最后暴力处理即可,
不替换的时候可以分两段处理
分别计算[1,a-1]和[a,b]的 然后相减就好了
处理先对p素因子分解,然后容斥原理计算,

HDU 2841 Visible Trees

显然能够知道题目要求的是
满足gcd(x,y)!=1x<=ny<=mgcd(x,y)!=1且x<=n且y<=m的数量
由于数据量不大 ,可以枚举n值然后计算[1,m]中与n不互质的数的个数,然后用m减去即可
对于计算[1,m]中与n不互质的数的个数,我们还是要用到容斥原理,

ans=+最大公约数因子个数为1最大公约数因子个数为2+最大公约数因子个数为3最大公约数因子个数为4....ans = +最大公约数因子个数为1的 -最大公约数因子个数为2的+最大公约数因子个数为3的 -最大公约数因子个数为4的....

最大公约数因子个数最大也就是8 因为2357111317*19 > 1e6
所以爆搜也不会超时

POJ 3695 Rectangles

乱搞题,首先居然是想到线段树,要不是做专题就陷进去了。

然后想到求多个矩形相交面积的方法搞,因为n比较小但(1<< n)远大于1e5,所以不用预处理出所有情况,只要对待查询的情况容斥原理计算就好.