UVa 11401 Triangle Counting

2017-01-13 19:11:54来源:CSDN作者:SenyeLicone人点击

You are given n rods of length 1, 2, . . . , n. You have to pick any 3 of them and build a triangle. How
many distinct triangles can you make? Note that, two triangles will be considered different if they have
at least 1 pair of arms with different length.
Input
The input for each case will have only a single positive integer n (3 ≤ n ≤ 1000000). The end of input
will be indicated by a case with n < 3. This case should not be processed.
Output
For each test case, print the number of distinct triangles you can make.
Sample Input
5
8
0
Sample Output
3

22

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

数论~

首先,这个题一定要枚举最大边长度,用最小边长度的话没法递推预处理。

然后,列一些数据找规律,就能发现规律,比如最长边为8,那么次长边为7时,2~6都可以组成;次长边为6时,3~5都可以……是一个等差数列,注意边角求和就可以了。

最后,计算过程中一定要乘1ll之类,否则会WA……


#include<cstdio>#define ll long longint n;ll ans[1000001];int main(){	for(int i=4;i<=1000000;i++)	{		ans[i]=(1ll*i*i-4ll*i+4ll)/4ll;ans[i]+=ans[i-1];	}	while(scanf("%d",&n)==1 && n>2) printf("%lld/n",ans[n]);	return 0;}


最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台