TOJ--3456--数学题

这题 做出来真的好爽啊... it is cool  although it is easy

虽然 已经是大概1 2点的事了 我拖到现在才写是因为------lol 终于赢一把了 ---

先贴下题目：

　　touch me

嗯  我一开始 用的是 3重for 我以为32767的数据量 是很小的....   结果 TLE。。

OK 那么 我们只能换种方法了  看它里面的关系

假如 现在告诉你三角形的周长是 L 有个很重要又很基础的定理 ---  任意两条边之和大于第三边

你知道一个固定周长的三角形 最长边最短是在什么时候吗？  那就是----  等边三角形的时候 即 L/3 的时候

那么最大的时候呢？  自然是L/2 的时候  这里我的（ L/2 )是不严密的  没有考虑 L的 奇偶性..

然后 我一开始的问题 就是出在这里了

因为当L为偶数的时候 L/2最长边 与 剩余的2边之和L/2 是相同的 这应该是排除的

　　当L为奇数的时候 L/2最长边 小于 剩余的2边之和（L/2+1） 这是成立的

这边 我们可以进行一个小处理之后就不用 把奇偶性分开考虑  假设 x 是最长边 那么x的范围就是

x -> L/3 ~ (L+1)/2   或 L/3 ~ (L-1)/2 第一个是<  第二个是<= 我个人还是喜欢第一种~

现在 我们已经完成了对于最长边的取值范围的剪枝

然后就是相对应的  当最长边取值为X时 剩余2条边的取值可能组合方案数 设剩余总和为y  cnt为组合数

假设y为8 那么它有(1,7) (2,6),(3,5),(4,4)这4种可能- 设为z

但并不是直接加上就好 因为要考虑边的最大值问题与等边三角形问题

有一点 要知道 对于一个y 拆成2个正整数之和的方案是 y/2

那么z应该怎么考虑呢？

z-(y-x-1) 这里 我不知道怎么解释了   因为我当时是 写了几个式子 观察出来的-----但感觉 就是那么回事  可是 我解释不了啊 =-=

 

啰嗦了好多没用的话~ 上 code

#include 
using namespace std;

int main()
{
    int n;
    int cnt;
    while( ~scanf("%d",&n) )
    {
        cnt = 0;
        for( int i = n/3+1 ; i<(n+1)/2 ; i++ )
        {
            int j = n-i;
            cnt = cnt + j/2 - (j-i-1);
        }
        printf( "%d
",cnt );
    }
    return 0;
}