[ TCO2016 Round 2B DIV1 Easy ] TriangleTriples

题意:给出\(a,b,c,1<=a,b,c<=10^9\),求所有的满足\(1 \leq x \leq a,1 \leq y \leq b,1 \leq z \leq c\)且由\(x,y,z\)为三边长能组成三角形的方案数。(\(a,b,c,x,y,z\)均为整数)

题解:用容斥做这道题目会比较简单。首先设\(a \leq b \leq c\)。考虑容斥,答案即\(abc\)减去所有\(x \geq y+z,y \geq x+z,z \geq x+y\)的方案数。由于\(x \geq y+z,y \geq x+z,z \geq x+y\)是独立的,所以可以分别计算。

考虑\(x \geq y+z\),由于\(y+z \leq a\),那么显然有\begin{aligned}1 \leq x \leq a \\ 1 \leq y \leq a \\ 1 \leq z \leq a \end{aligned}答案显然为\(\sum_{i=1}^{a-1}{\frac{i(i+1)}{2}}=\frac{a(a+1)(a-1)}{6}=C_{a+1}^{3}\),后面的组合数可以理解为在\(0…a\)中选出三个点\(x_0,x_1,x_2,0 \leq x_0<x_1<x_2 \leq a\),取\(x=x_2,y=x_2-x_1,z=x_1-x_0\),这样构成一种方案。这里就把\(x \geq y+z\)的情况给算完了。

接下来令\(f(x)=C_{x+1}^{3}\)。

考虑\(y \geq x+z\),如果用\begin{aligned}1 \leq x \leq b \\ 1 \leq y \leq b \\ 1 \leq z \leq b \end{aligned},即\(f(b)\)来计算,则会多算\(a+1 \leq x \leq b\)的部分。不等式两边同时减去\(a\),即\(y-a \geq x-a+z\),那么多算的部分为\begin{aligned}1 \leq x \leq b-a \\ 1 \leq y \leq b-a\\ 1 \leq z \leq b-a \end{aligned},即\(f(b-a)\),该情况的方案数为\(f(b)-f(b-a)\)。

同理,\(z \geq x+y\)的方案数也可用上述方法计算。如果\(c \leq a+b\)的话,方案数即\(f(c)-f(c-a)-f(c-b)\),如果\(c>a+b)\)还要再加上一个\(f(c-a-b)\)。

所以答案即为\[abc-f(a)-f(b)-f(c)-f(b-a)-f(c-a)-f(c-b)+f(c-a-b)[c>a+b]\]


page views : 33 views

发表评论

电子邮件地址不会被公开。 必填项已用*标注