[原创]容斥原理习题
[原创]容斥原理习题
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
显然能够知道题目要求的是
满足的数量
由于数据量不大 ,可以枚举n值然后计算[1,m]中与n不互质的数的个数,然后用m减去即可
对于计算[1,m]中与n不互质的数的个数,我们还是要用到容斥原理,
最大公约数因子个数最大也就是8 因为2357111317*19 > 1e6
所以爆搜也不会超时
POJ 3695 Rectangles
乱搞题,首先居然是想到线段树,要不是做专题就陷进去了。
然后想到求多个矩形相交面积的方法搞,因为n比较小但(1<< n)远大于1e5,所以不用预处理出所有情况,只要对待查询的情况容斥原理计算就好.
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 tabris的博客!
评论