学步园

1

35

题目链接： http://codeforces.com/problemset/problem/304/A

题意：给出一个n 让你找出有多少组 a,b,c  满足 1≤a≤b≤c≤n  而且 a2+b2=c2

感想：因为 n 最大也只有为10^4 而且时间有3000ms （感觉这题给的时间太宽了  不然很多队都一次性过不了了 因为都是超过了 1s 的）可以直接用 O（n^2) 的暴力过  稍微优化了一点 最后390ms   不过LOR队只有15ms  大家可以去参考下他们的代码  他们是打表做的  就是用一个程序（一般是TML的程序）把结果算出来输出到一个文件里  然后直接在另外一个程序中 搞个数组 ans[]={ 复制 } 就够了  这种方法对时间要求小数据量小的题目很有用  表示又学习了一招 

思路：用了递推的思想 对c循环 每次算出 c=i 时能组合成的 a,b,c 组合  然后存到一 num[] 数组中  然后要求的答案即为 num[] 的前n项和s[n]

下面贴我的代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#define e sqrt(2.0)
using namespace std;

int num[10005],s[10005];   // num[i] 相当于数列的ai  s[i] 相当于si(前i项和)

int main()
{
    int i,j,b,c,temp,t,n,t1,t2;
    double d1,d2;
    memset(num,0,sizeof(num));    // 初始化num[]
    s[0]=s[1]=s[2]=s[3]=s[4]=0;   // s[]的前4项均为0 
    for(c=5;c<=10000;c++)         // 对c循环 每次计算出满足条件的 a,b,c
    {
        t=c;
        temp=(int)(t*1.0/e+0.5);  // e为根号2  由于b>a 故可得出b>=(c/根号2)  +0.5后取整是为了防止精度损失
        for(b=c-1;b>=temp;b--)    // 对b循环 从c-1开始 因为a不能为0 故b不能等于c   ps：枚举b要快一些  若枚举a则要 从1到c/根号2  要慢一些
        {
            d1=d2=sqrt((c+b)*(c-b)*1.0);   // 计算c^2-b^2开根号 即计算a
            if((int)(d2+0.5)==d1)          // 判断a是否为整数 是则num[]++
            {
                num[c]++;
            }
        }
        s[c]=s[c-1]+num[c];      // 计算num[]时同时计算 s[]
    }
    while(~scanf("%d",&n))
    {
        printf("%d\n",s[n]);    // 答案存好后直接输出就够了 这样比每次进来算答案要快
    }
    return 0;
}