HDU 1407 测试你是否和LTC水平一样高枚举、二分、hash

http://acm.hdu.edu.cn/showproblem.php?pid=1407

计算方程x^2+y^2+z^2= num的一个正整数解。num为不大于10000的正整数

思路：

方法一、直接三重循环暴力 234MS

方法二、枚举x和y，对z进行二分查找。62MS

方法三、枚举x和y，对z用hash判断是否存在 15MS

方法二和方法三都是枚举x和y，但是二分查找为O(log(n))而hash为O(1）

可以看到，方法一和方法三差了十几倍！

还有就是用goto从内重循环直接跳出简洁而优雅。

方法一：直接三重循环暴力 234MS

#include<cstdio>

#include<cmath>

int res[101];

int main()

{

    int n;

    for(int i=1;i<=100;i++)

        res[i]=i*i;

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

    {

        for(int x=1;x<=100;x++)

            for(int y=1;y<=100;y++)

                for(int z=1;z<=100;z++)

                    if( res[x]+res[y]+res[z]==n)

                    {

                        printf("%d %d %d\n",x,y,z);

                        goto end;

                    }

        end:;

    }

    return 0;

}

方法二：枚举x和y，对z进行二分查找。62MS

#include<cstdio>

#include<cmath>

int res[101];

int search(int n)

{

    int L=1,R=101;

    while(L<R)

    {

        int m=(L+R)>>1;

        if(res[m]==n)

            return m;

        else if(res[m] < n)

            L=m+1;

        else

            R=m;

    }

    return -1;

}

int main()

{

    int n;

    for(int i=1;i<=100;i++)

        res[i]=i*i;

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

    {

        for(int x=1;x<=100;x++)

        {

            for(int y=1;res[x]+res[y]<n;y++)

            {

                int z=search(n-res[x]-res[y]);

                if(z!=-1)

                {

                    printf("%d %d %d\n",x,y,z);

                goto end;

                }

            }

        }

end:;

    }

    return 0;

}

方法三：枚举x和y，对z用hash判断是否存在 15MS

#include<cstdio>

#include<cmath>

const int MAXN=10001;

int res[101];

struct HASH

{

    bool exist;

    int index;

}hash[MAXN];

int main()

{

    int n;

    for(int i=1;i<=100;i++)

    {

        res[i]=i*i;

        hash[ res[i] ].exist=true;

        hash[ res[i] ].index=i;

    }

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

    {

        for(int x=1;x<=100;x++)

        {

            for(int y=1;res[x]+res[y]<n;y++)

            {

                int id=n-res[x]-res[y];

                if(hash[id].exist)

                {

                    printf("%d %d %d\n",x,y,hash[id].index);

                goto end;

                }

            }

        }

end:;

    }

    return 0;

}

巴特西

HDU 1407 测试你是否和LTC水平一样高枚举、二分、hash

最新文章

热门文章

巴特西

HDU 1407 测试你是否和LTC水平一样高 枚举、二分、hash

最新文章

热门文章

HDU 1407 测试你是否和LTC水平一样高枚举、二分、hash