UVa 11401 数三角形(组合数学)

2017年07月19日 9点热度 0人点赞 0条评论

数三角形(Triangle Counting, UVa 11401
有多少种方法可以从
1
23
n中选出3个不同的整数, 使得以
它们为三边长可以组成三角形? 比如
n5时有3种方法, 即(2
3
4) , (2
35) , (3
45) 。
n8时有22种方法。
【输入格式】
输入包含多组测试数据, 每组数据的第一行为整数
n3≤n≤1000000) 。 输入用n3的标志结束。
170
【输出格式】
对于每组数据, 输出其方案总数。
【分析】
三重循环的时间复杂度为
On3) , 采用这种方法肯定超时。 这样的
规模即使是
On2) 时间的算法都很难承受, 那么只能进行一些数学分析
了。
用加法原理, 设最大边长为
x的三角形有cx) 个, 另外两条边长分
别为
yz, 根据三角形不等式[2]yzx
所以
z的范围是xyzx
根据这个不等式, 当
y1x1zx
显然无解;
y2时只有一个
解(
zx1) ;
y3时有两个解(zx1或者zx2
……直到yx
1时有x2个解。 根据等差数列求和公式, 一共有012+(x3
+(
x2) =(x1
x2
/2个解。
可惜, 这并不是
cx) 的正确数值, 因为上面的解包含了yz的情
况, 而且每个三角形算了两遍(想一想, 为什么) 。 解决方案很简单,
首先统计
yz的情况。
y的取值从x/21开始到x1为止,
一共有
x1
x/2=(x1
/2个解, 然后把这部分解扣除, 再除以2, 即
原题要求的实际上是
最大边长不超过n的三角形数目”fn
。 根据
加法原理,
fn) =c1
c2) +cn
。 可以写成递推式

fn) =fn1
cn) 。 代码如下。

#include
using namespace std;
long long f[1000010];
int main(){
	f[3]=0;
	for(long long x=4;x<=1000000;++x)
	f[x]=f[x-1]+((x-1)*(x-2)/2-(x-1)/2)/2;
	int n;
	while(cin>>n&&n>=3) cout<
未经允许不得转载!UVa 11401 数三角形(组合数学)

update

纸上得来终觉浅, 绝知此事须躬行。