POJ 1840 Eqs解题报告

时间：2010-06-04 来源：华南理工大学

一、问题描述

http://acm.pku.edu.cn/JudgeOnline/problem?id=1840

二、解题思路

首先想到的思路是用五个循环遍历，再加一些剪枝条件，结果半天都没有出结果。遍历应该是行不通的了。

这里用到的思路是将方程分开，即：

-(a1X13+a2X23)=(a3X33+a4X43+a5X53)

首先计算左边的所有可能的结果，并放在一个数组里，然后进行排序。

然后计算左边的结果，同时在数组中查找（二分查找）这个结果是否存在，如果存在，计算出存在多少个。这样需要10000个存储空间，和100万次二分查找。提交结果显示用了1063MS。

三、代码

#include<iostream>
#include<algorithm>
using namespace std;
int d[6][105];
int H[10005];
const int MAX=100;
int len;
int cmp(const void * a,const void * b)
{
    return *(int *)a-*(int *)b;
}
int search_binary(int key,int s,int t)
{
    int m;
    while(s<=t)
    {
        m=(s+t)/2;
        if(H[m]==key)
        {
            int c;
            int d;
            c=d=0;
            int tt=m-1;
            while(tt>=s && H[tt--]==key)
                c++;
            tt=m+1;
            while(tt<=t && H[tt++]==key)
                d++;
            return c+d+1;
        }
        else
        {
            if(H[m]>key)
                t=m-1;
            else
                s=m+1;
        }
    }
    return -1;
}
int main()
{
    int i,j,k,l,m;
    int a[6];
    int temp;
    scanf("%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5]);
    for(i=0;i<50;++i)
    {
        temp=(i-50)*(i-50)*(i-50);
        for(j=1;j<=5;j++)
            d[j][i]=a[j]*temp;
    }
    for(i=51;i<=MAX;++i)
    {
        temp=(i-50)*(i-50)*(i-50);
        for(j=1;j<=5;j++)
            d[j][i-1]=a[j]*temp;
    }

    //int L1,L2,L3,L4;

    len=0;
    for(i=0;i<MAX;++i)
    {
        for(j=0;j<MAX;++j)
        {
            H[len++]=(0-(d[1][i]+d[2][j]));
        }
    }
    sort(H,H+len);
    //qsort(H,len,sizeof(H[0]),cmp);//排序

    int sum=0;
    for(k=0;k<MAX;++k)
    {
        for(l=0;l<MAX;++l)
        {
            for(m=0;m<MAX;++m)
            {
                temp=d[3][k]+d[4][l]+d[5][m];
                int times=search_binary(temp,0,len-1);
                if(times!=-1)
                    sum+=times;
            }
        }
    }
    printf("%d\n",sum);
    return 0;
}