POJ 1840 - Eqs | 眈眈探求

算法

原创

发布日期: 2011-06-27

更新日期: 2026-04-28

文章字数: 873

阅读时长: 3 分

阅读次数:

POJ 1840 - Eqs
Time: 5000MS
Memory: 65536K
难度: 初级
分类: 高效查找法

问题描述

给出一个五元三次方程，输入其 5 个系数，求它的解的个数。

其中系数 ai ∈ [-50, 50]，自变量 xi ∈ [-50, 0) ∪ (0, 50]。

注意： 若 x1 = a, x2 = b, x3 = c, x4 = d, x5 = e 时，与 x1 = b, x2 = a, x3 = c, x4 = d, x5 = e 代入方程后都得到值 0，那么它们视为不同的解。

解题思路

直观思路是暴力枚举，时间复杂度为 O(n^5)。

题目 Time Limit = 5000ms，按 1ms 大约可执行 1000 条语句估算，那么 5000ms 最多执行 500W 次。

每个变量都有 100 种可能值，暴力枚举 5 层循环，需要执行 100^5 = 100E 次，必然会 TLE。

要 AC 这题，就要先对方程做变形：

等价于：

即先枚举 x1 和 x2 的组合，把所有出现过的左值记录下来；再枚举 x3、x4、x5 的组合得到右值。如果某个右值等于已经出现过的左值，那么我们就得到了一个解。

时间复杂度从 O(n^5) 降低到 O(n^2 + n^3)，大约执行 100W 次。

我们先定义一个映射数组 hash[]，初始化为 0。

对于方程左边，当 x1 = m、x2 = n 时得到 sum，则用 hash[] 记录它：hash[sum]++，表示 sum 这个值出现了 1 次。

之所以记录“次数”，而不是记录“是否已出现”，

是因为我们 不能保证 函数的映射为 1 对 1 映射，更多情况是 多对 1 映射。

例如当 a1 = a2 时，x1 = m、x2 = n 会得到 sum，而 x1 = n、x2 = m 时也会得到同样的 sum。但这两个解在题意中是不同的，这就是多对 1 的情况。如果仅记录 sum 是否出现过，就会使解的个数减少。

其次，为了让“搜索 sum 是否出现”的操作达到 O(1)，我们直接把 sum 作为下标。那么 hash 数组的上界就取决于 a1、a2、x1、x2 的组合，四个量的极端值均为 50。

因此上界为 50 * 50^3 + 50 * 50^3 = 12500000。由于 sum 也可能为负数，因此把 hash[] 的范围扩展到 25000000。当 sum < 0 时，令 sum += 25000000 后再存储到 hash[]。

由于数组很大，必须使用全局定义。
同时由于数组很大，用 int 定义必然会 MLE，因此要用 char 或 short 定义数组，推荐 short。

AC 源码

//Memory Time
//49188K 532MS 

#include<iostream>
using namespace std;

short hash[25000001];  //hash[sum]表示值等于sum的的解的个数(多对1映射)

int main(void)
{
    int a1,a2,a3,a4,a5;  //系数
    while(cin>>a1>>a2>>a3>>a4>>a5)
    {
        memset(hash,0,sizeof(hash));

        for(int x1=-50;x1<=50;x1++)
        {
            if(!x1)
                continue;

            for(int x2=-50;x2<=50;x2++)
            {
                if(!x2)
                    continue;
                int sum=(a1*x1*x1*x1 + a2*x2*x2*x2)*(-1);
                if(sum<0)
                    sum+=25000000;
                hash[sum]++;
            }
        }

        int solution=0;

        for(int x3=-50;x3<=50;x3++)
        {
            if(!x3)
                continue;
            for(int x4=-50;x4<=50;x4++)
            {
                if(!x4)
                    continue;
                for(int x5=-50;x5<=50;x5++)
                {
                    if(!x5)
                        continue;
                    int sum=a3*x3*x3*x3 + a4*x4*x4*x4 + a5*x5*x5*x5;
                    if(sum<0)
                        sum+=25000000;
                    if(hash[sum])
                        solution+=hash[sum];
                }
            }
        }

        cout<<solution<<endl;
    }                
    return 0;
}