Category Archives: 容斥

某某训练赛

Problem A UVALive 5108 Playing Field 一个n个点的凸包,q个询问a,b,在 …

LightOj 1161 Extreme GCD (容吃原理)

给出n <= 10000 个数字,每个数字<= 10000,计算n个数字中存在多少个四对的数字他们 …

HDU 5838 Mountain (状压dp,容斥)

给出n * m的格子,X表示盆地(四周的数字都比他大)。可以用1 – n * m的数字去填这些格子 …

2016 Multi-University Training Contest 6

1001 – A Boring Question 推公式的题目,打个表能看出是个等比数列前n项和。 …

51nod wangyurzee的树 (容斥原理)

wangyurzee有n个各不相同的节点,编号从1到n。wangyurzee想在它们之间连n-1条边,从而使它 …

2016 Multi-University Training Contest 4

1001 – Another Meaning 给出A串和B串,可以选择A串中被B串匹配的任意位置打 …

51nod lyk与gcd (容斥)

这天,lyk又和gcd杠上了。 它拥有一个n个数的数列,它想实现两种操作。 1:将 ai 改为b。 2:给定一 …

计蒜客 青云的机房组网方案(困难)(树分治,容斥)

给出一颗树,树上每个点都有一个权值,计算树上点对的距离和,前提是点对必须满足点权互质。 树分治下,存下每个数质 …

LightOJ 1170 Counting Perfect BST (容斥原理)

计算将a-b之间的power数(数字可以分解成x^y && x > 1 &&am …

UVA 1393 Highways (容斥)

一个n*m的矩阵,将两点两两连线,问存在几条线至少穿过两个点。 直接计算某个矩阵整体的线不容易计算,思考在某个 …