Compete

I can't fall down before I die
  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  11 Posts :: 3 Stories :: 2 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜
POJ 1840 (EQS)

典型哈希题，但我写的哈希在自己机子上跑不出来，编译OK运行就出现警告，后来又看别人的BLOG发现自己竟忘了STL，上次用STL还是在去年，今年一次也没用，不光忘了学STL还忘了有这东西在。╮(╯▽╰)╭

少说废话，直接看题

给出5个数a1   a2  a3  a4  a5  作为输入
还有5个数 x1  x2  x3  x4  x5，求出这五个数有多少种组合情况能满足方程x1 * a1^3 + x2 * a2^3 + x3 * a3^3 + x4*a4^3 + x5*a5^3=0

已知各个数字范围在[-50,50]

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>s1,s2;
int cub[110];
int a[6];

int main()
{
    int i,k,j;
    j=0;
    int ans=0;
    for(i=-50;i<=50;i++)
    {
        if(i==0) continue;
        cub[++j]=i*i*i;
    }
    int pos;
    for(i=1;i<=5;i++)
        cin>>a[i];
    for(i=1;i<=100;i++)
    {
        for(j=1;j<=100;j++)
        {
            pos=-(a[1]*cub[i]+a[2]*cub[j]);
            s1.push_back(pos);
        }
    }
    for(i=1;i<=100;i++)
    {
        for(j=1;j<=100;j++)
        {
            for(k=1;k<=100;k++)
            {
                pos=a[3]*cub[i]+a[4]*cub[j]+a[5]*cub[k];
                s2.push_back(pos);
            }
        }
    }
    sort(s1.begin(),s1.end());
    sort(s2.begin(),s2.end());
    for(i=0,j=0;i<s1.size()&&j<s2.size();)
    {
        if(s1[i]==s2[j])
        {
            k=i;
            while(s1[k++]==s2[j])
                ans++;
            j++;
        }
        else if(s1[i]<s2[j])
            i++;
        else j++;
    }
    cout<<ans<<endl;
    return 0;
}

后来用了个bool 型大数组开到25000000大，虽然自己机子上运行不了但提交到POJ却一百多毫秒A掉，比起上面这个省了几倍时间
核心代码：

bool hash[25000010];
int half=12500000;
int neg_half=-12500000;

    for(i = 0; i < 100; i ++)
    {
        for(j = 0; j < 100; j ++)
        {
            pos = -(a[0]*cube[i] + a[1]*cube[j]);
            hash[pos + 12500000] ++;
        }
    }
    ans = 0;
    for(i =1;i<=100;i++)
    {
        for(j=1;j<=100;j++)
        {
            for(k =0;k<100;k++)
            {
                pos=a[3]*cube[i]+a[4]*cube[j]+a[5]*cube[k];
                if(pos<neg_half || pos>half)
                    continue;
                ans+=hash[pos+half];
            }
        }
    }


posted on 2010-08-14 16:53 丁立洋 阅读(159) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理