1.题目描述：点击打开链接
2.解题思路：本题利用代数分析和加法原理解决。根据题目给定的范围，只能使用O(N)级别的算法，直接枚举肯定是会超时的。我们设c(x)表示最大边长为x的三角形的个数。设另外两条边为y,z。根据三角形不等式，有y+z>x。所以z的范围是x-y<z<x。
根据这个不等式，我们可以改变参变量y的值来得到z的个数。当y=1时显然无解。当y=2时，，有一个解。当y=3时，有2个解。。。直到y=x-1，有x-2个解。根据等差数列的求和公式，一共有0+1+2+…+(x-3)+(x-2)=(x-1)(x-2)/2个解。
然而，这样算出来的并不是正确的c(x)的值，根据y和z的对称性，我们发现，凡是在y!=z的地方，我们都重复计算了一次，因此我们要想办法扣除重复计算的部分。首先统计y==z的情况。y的值从x/2+1开始到x-1为止，一共有(x-1)-x/2=(x-1)/2个解。因此把这部分扣除，再除以2才是正确的结果。即c(x)={(x-1)(x-2)/2-(x-1)/2}/2。（因为题目中要求三角形的三条边长度各不相同，因此要取出y==z的情况）。
这样，设“最大边长不超过n的三角形数目”为f(n)，那么根据加法原理，f(n)=c(1)+c(2)+…+c(n)。写成递推式就是f(n)=f(n-1)+c(n)。注意本题应该使用long long类型。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int, int> P;typedef pair<long long, long long> PL;#define N 1000010ll f[N];//注意要使用llint main(){//freopen("t.txt", "r", stdin);f[3] = 0;for (ll x = 4; x <= 1000000; x++)f[x] = f[x – 1] + ((x – 1)*(x – 2) / 2 – (x – 1) / 2) / 2;int n;while (cin >> n){if (n < 3)break;cout << f[n] << endl;}return 0;}
但一定要背上几本书，在花海里，草丛旁悠然品味，
