生物网站建设/网站免费推广

题意：由1,2,3...n组成的序列中找三个数，且以这三个数为变长能组成三角形，求这样的三角形个数。

思路：当每次输入n时重新都计算一遍会TLE。。。先预处理，将结果存入ans数组。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
#define INF 0x7fffffff
long long ans[1000100];
int main(){long long i,n,temp,k;ans[3] = 0;for(i=4;i<=1000000;i++){n = i;temp = 0;if(i%2==0){temp = (n*(n-2)/4)/2;temp += (n-2)*(n-4)/8;}else{temp = ((n-1)*(n-3)/4)/2;temp += (n-1)*(n-3)/8;}ans[i] = temp + ans[i-1];}while(scanf("%lld",&n) == 1 && n >= 3)printf("%lld\n",ans[n]);return 0;
}