nyoj 982
Triangle Counting
時間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 難度：3 描述22
解題思路：這道題目的題意很簡單，給出n條線段，長度為1-n，問有多少種方法可以從這n條線段中取出3條不同的線段，使得以它們?yōu)槿呴L可以組成三角形。這是一個純數(shù)學(xué)推理問題。我們首先假設(shè)最大邊為x，其余兩邊為y，z那么有不等式y(tǒng)+z>x。那么z的范圍是x-y<z<x，接下來的工作就是枚舉y的范圍，然后看z能夠取多少。
假設(shè)C(x)為最大邊為x時，能得到的三角形個數(shù)，假設(shè)y從1-（x-1）枚舉一遍，那么z所能取到的個數(shù)分別為0,1,2,......,x-2;所以總共有(x-1)(x-2)/2個，但是還沒完，題目中的三條邊都不能相等，但這里面出現(xiàn)了y=z的情況，所以要將這種情況去掉，并且每個三角形重復(fù)了一次，所以最后還要除以2。。要保證y=z的情況出現(xiàn)，那么y只能從最小的x/2+1開始，一直到x-1為止，總共出現(xiàn)了（x-1）-（x/2+1)+1=x/2-1，考慮到x的奇偶性，有 （x-1）/2個y=z的情況出現(xiàn)。。那么C(x)=((x-1)*(x-2)/2-(x-1)/2)/2。f(n) = C(1)+C(2)+......+C(n) = f(n-1)+C(n)。。
AC:
#include<iostream> using namespace std;long long f[1000005]; int main() {f[1] = f[2] = f[3] = 0;for(int i = 4; i <= 1000000; i++)f[i] = f[i-1] + ((i-1)*(i-2)/2 - (i-1)/2)/2;int n;while(cin>>n){if(n < 1) break;cout<<f[n]<<endl;}return 0; }
總結(jié)
- 上一篇： 开发指南专题十八：Navicat 数据库
- 下一篇： UI标签库专题六：JEECG智能开发平台