codeforces #345 div 2 C. Watchmen (容斥)

题目链接
题意:求曼哈顿距离和平方根距离相等的点的对数?
思路:化简发现是绝对值乘积等于0,容斥搞搞。

hdu 3929 Big Coefficients (递归形式的容斥原理+lucas定理的结论)

题意:F(x) = (1+x)^a1 + (1+x)^a2 + … + (1+x)^am,求系数是奇数的项的个数。
思路:解题报告 涉及到的由lucas定理得到的推论的证明lucas定理证明 以及这篇理解里有递归形式的容斥定理的一般写法。。递归形式的容斥定理

第一次接触递归形式的容斥定理…还不是特别理解,据说要比循环的写法少一层msk(应该是少一个1<

hdu 1796 How many integers can you find (容斥原理)

hdu1796
题意:给出n(<=2^31)以及m(<=10)个元素组成的无重复元素集合,集合元素0<=a[i]<=20,问有多少个小于n的数能至少被集合中的一个元素整除。

思路:容斥,找到能被一个元素的,被两个元素的…加加减减。
一个元素的最小公倍数定义成自己,然后多个元素的就两个两个算…

一个坑点是,a[i]有0,而一个数除以0没有意义。。。所以读入的时候处理下。。。把0删掉(个人觉得这个坑点毫无技术含量。。。。0不能作为除数这种事情呵呵呵)  并且如果只有一个数且为0,那么删掉后集合就为空了,特判输出0.

 

另一个坑点是,别看每个数都很小。。但是求多个数的最小公倍数的时候会爆int…

虽然最后结果没有爆,但是中间量会爆掉,要开long long 

 

20160305update:也写个递归版本的,好简洁有木有。

hdu 4336 Card Collector (2012多校 #4) (容斥原理模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=4336

题意:有n种卡片,买一包干脆面得到第i种卡片的概率是p[i],每包干脆面最多有一张卡片,问收集齐所有卡片要买的干脆面的包数的数学期望。

思路:容斥模板题。1.0/p[i]就是拿到某张卡片需要买的包数的数学期望

注意体会这种具体应用容斥的模拟方法,把1<<n转化成二进制来模拟有1个元素的集合,有2个元素的集合…有n个元素的集合。
核心代码:

 

20160305update:前几天有道题没写递归形式tle掉了。。。所以来学习一下容斥原理的递归形式。

以及这道题用递归的形式写了一遍。

hdu 5213 lucky (莫队算法)

http://acm.hdu.edu.cn/showproblem.php?pid=5213
题意:n个数,m个查询,每个查询由4个数l1,r1,l2,r2构成,询问分别从[l1,r1]和[l2,r2]中各取一个数,和为给定的常数k的方案数。

思路:首先分别由两个区间取数不好搞,我们可以用容斥原理对区间变换。这是这道题最关键的一步。

官方题解:这道题需要一些莫队算法的知识 定义记号f(A,B)f(A,B)表示询问区间A,B时的答案 用记号+表示集合的并 利用莫队算法我们可以计算出任意f(A,A)f(A,A)的值 不妨假设A=[l1,r1],B=[l2,r2],C=[r1+1,l2-1]A=[l1,r1],B=[l2,r2],C=[r1+1,l21]容易知道(并没有很容易f(A,B)=f(A+B+C,A+B+C)+f(C,C)-f(A+C,A+C)-f(C+B,C+B)f(A,B)=f(A+B+C,A+B+C)+f(C,C)f(A+C,A+C)f(C+B,C+B) 因此一个询问被拆成四个可以用莫队算法做的询问 总的时间复杂度为O(msqrt(n))O(msqrt(n))

然后就是莫队算法的内容。值得一提的是,被拆成的四个子询问不必做四次莫队,可以合在一起,因为每一次询问对答案的贡献都不会受顺序影响,而且这样用时更短。

然后初始构造的时候用构造函数比赋值要方便许多。

还要记得多组数据记得清空各种数组。。。(因为忘记清空ans数组wa到死。。。)

最最关键的是,对于求两个数a+b==k这类问题(不一定是加,就是和两个数满足一个关系的时候),我们可以转换思维。a==k-b.也就是统计的时候是cnt[b]++,更新答案的时候,由于现在是b,我需要找有多少个a,也就是多少个k-b,所以是ans+=cnt[k-b];(要注意保证k-b>0)