题解 SP867 【CUBES - Perfect Cubes】

· · 题解

这道题明显是一道暴力。

暴力枚举每一个 a, b, c, d

所以我就写了一个暴力。每个 a, b, c, d 都从 1 枚举到 100

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define line cout << endl
using namespace std;
int lf(int x) {
    return x * x * x;
}
int main() {
    for (int a = 1; a <= 100; a++) {
        for (int b = 1; b <= 100; b++) {
            for (int c = 1; c <= 100; c++) {
                for (int d = 1; d <= 100; d++) {
                    if (lf(a) == lf(b) + lf(c) + lf(d)) {
                        cout << "Cube = " << a << ", Triple = (" << b << "," << c << "," << d << ")";
                        line;
                    }
                }
            }
        }
    }
    return 0;
}

结果，成功的 WA 掉了（（（

为什么？

我们仔细观察题目给出的前几个样例：

Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)

而再看上面的程序输出的前几个：

Cube = 6, Triple = (3,4,5)
Cube = 6, Triple = (3,5,4)
Cube = 6, Triple = (4,3,5)
Cube = 6, Triple = (4,5,3)
Cube = 6, Triple = (5,3,4)
Cube = 6, Triple = (5,4,3)
Cube = 9, Triple = (1,6,8)
Cube = 9, Triple = (1,8,6)
Cube = 9, Triple = (6,1,8)
Cube = 9, Triple = (6,8,1)
Cube = 9, Triple = (8,1,6)
Cube = 9, Triple = (8,6,1)

发现什么问题了吗？ 相信 全谷最聪明的你 已经发现了问题。

仔细观察 Cube = 6 的情况：

我的程序：

Cube = 6, Triple = (3,4,5)
Cube = 6, Triple = (3,5,4)
Cube = 6, Triple = (4,3,5)
Cube = 6, Triple = (4,5,3)
Cube = 6, Triple = (5,3,4)
Cube = 6, Triple = (5,4,3)

正确答案：

Cube = 6, Triple = (3,4,5)

有可能题目没有翻译清晰

发现每个 Cube 只需要输出一组，那么我们就可以改变一下循环的初始状态。

将 a,b 从 2 到 100 枚举，将 c 从 b 到 100 枚举，将 d 从 c 到 100 枚举。

最后放上代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define line cout << endl
using namespace std;
int lf(int x) {//立方的函数
    return x * x * x;
}
int main() {
//  freopen("1.out", "w", stdout);
    for (int a = 2; a <= 100; a++) {
        for (int b = 2; b <= 100; b++) {
            for (int c = b; c <= 100; c++) {
                for (int d = c; d <= 100; d++) {
                    if (lf(a) == lf(b) + lf(c) + lf(d)) {
                        cout << "Cube = " << a << ", Triple = (" << b << "," << c << "," << d << ")";
                        line;
                    }
                }
            }
        }
    }
    return 0;
}