本篇文章個人在深圳喝咖啡的時候突然想到的...最近就有想寫幾篇關于地址變形的文章，所以回家到之后就奮筆疾書的寫出來發表了

????題目地址：? http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2396

????

????思路：

????這里確定不能用O(n^3)的算法，只能找法則

????設最大的數為x，另外兩條為z,y，所以有z+y>x，變形得x-y<z<x

????當y=1時，x無解。

????當y=2時，x有一個解。

????..........

????當y=x-1時，x有x-2個解。

????所以有(x-1)*(x-2)/2個解，然后去掉重復的

????y=z的情況，y的取值從x/2+1開始到x-1

????而且每一個三角形算了兩變。

????所以c(i)=((i-1)*(i-2)/2-(i-1)/2)/2.

????f[i]=f[i-1]+c(i)

????

????代碼如下：

    #include<iostream>

#include<vector>

#include<list>

#include<deque>

#include<queue>

#include<stack>

#include<map>

#include<set>

#include<algorithm>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<cmath>

using namespace std;



const int N=1000010;

typedef long long LL;



int n;

LL xh[N];



int main()

{

    xh[3]=0;

    for(LL i=4;i<=1000000;i++)

        xh[i]=xh[i-1]+((i-1)*(i-2)/2-(i-1)/2)/2;

    while(scanf("%d",&n))

    {

        if(n<3)

            break;

        printf("%lld\n",xh[n]);

    }

    return 0;

}
  

文章結束給大家分享下程序員的一些笑話語錄： 騰訊總舵主馬化騰，有人曾經戲稱如果在Z國選舉總統，馬化騰一定當選，因為只要QQ來一個彈窗”投馬總，送Q幣”即可。

地址變形Uva 11401 - Triangle Counting