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

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

????

????思路：

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

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

????當(dāng)y=1時(shí)，x無解。

????當(dāng)y=2時(shí)，x有一個(gè)解。

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

????當(dāng)y=x-1時(shí)，x有x-2個(gè)解。

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

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

????而且每一個(gè)三角形算了兩變。

????所以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;

}
  

文章結(jié)束給大家分享下程序員的一些笑話語錄： 騰訊總舵主馬化騰，有人曾經(jīng)戲稱如果在Z國選舉總統(tǒng)，馬化騰一定當(dāng)選，因?yàn)橹灰猀Q來一個(gè)彈窗”投馬總，送Q幣”即可。

地址變形Uva 11401 - Triangle Counting