UVA12558 埃及分数

Daniel_7216 · 2021-07-21 21:54:49 · 题解

十年 OI 一场空，不开 long long 见 **

一、分析

先不考虑这道题最坑爹关键的数据范围，这道题乍一看似乎是一道搜索题，但是如果开始着手去做，就有一个问题：搜索没有深度限制，而且每一个数理论上也可以分成无限多的数！所以，我们就要从一开始不断往上枚举深度上限，然后找到第一个可以按规定分完的最小上限，这样就能够满足题目中要求的拆分出的数尽量少。通过一些小学分数知识可以证明，一定可以在有限个分数内凑出合法解。但是毕竟有时间限制（虽然有 15 秒），所以要开始第二个部分，剪枝。

二、剪枝

对于每一个阶段，我们只关心三个问题：当前的深度、现在所允许的最大的分母、当前还需凑出来的分数和。所以我们有以下的剪枝：

• 我们设要枚举的分母要从 c 开始，那么它一定是所有满足 \frac{1}{c} \le \frac{a}{b} 中最小的，稍微变一下， c 表示的就是 b \le ac 中最小的，所以我们可以先在每一次枚举前找到这个数，这样就不用每次从头枚举了。

• 题目中要求最优解，怎么更新？我们不妨用最朴素的方法，每一次搜索都把答案存到一个数组，最终答案在另一个数组，每一次搜索的深度到达最大限制，就更新答案。如果这一轮的答案和当前答案不同，且在相同位上当前答案更优则进行更新。

• 在第一部分我们提到，理论上每一个数也可以分成无限多的数。但是如果规定了最大深度的话，当枚举到分母为 i 、剩余的分数为 \frac{a}{b} 、第 deep 层，且满足 b(maxdeep - deep + 1) \le a \times i 时就可以停止了，显而易见的平凡，读者自证不难请读者自证。

三、范围问题

这个题不要看 a 和 b 好像都没超过一千，但是如果分到后面分母真的很大！所以，请在开 long long 和 WA 中二选一吧。

相信这一点很多 OIer 都可以避开了，但是这个题有一个隐形的天坑！在题目中， 有 k 个数 q_i 都不能做分母。虽然范围只在一千以内，但是千万别在搜索时用布尔数组判断！不然，你会 RE 的！因为你要判断的是分母是否可用，而我们知道分母在题中都是 long long 范围的，所以会越界而且你自己都不知道你是哪里错了。在这里感谢老师指出我的这个问题 (づ￣3￣)づ╭❤～

四、你猜是什么？

AC 代码献上，题解未尽细节都应该好懂：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
long long tmp, k, q, a, b, t, min_first, a1, b1;
int maxdeep;
long long ans[200001], now[200001];
map<long long ,bool>panduan;
int get_first(long long a, long long b) {
    for (int i = 2; ; i++) {
        if (b <= a * i) return i;
    }
}
long long gcd(long long a, long long b) {
    return b == 0? a : gcd(b, a % b);
}
bool is_good(int deep) {
    for (int i = deep; i >= 0; i--) {
        if (ans[i] != now[i]) return ans[i] == -1 || now[i] < ans[i];
    }
    return false;
}
bool dfs(int deep, int min_a, long long a, long long b) {
    if (deep == maxdeep) {
        if (a == 0) return false;
        if (b % a != 0) return false;
        if (panduan[b/a]) return false;
        now[deep] = b / a;
        if (is_good(deep)) {
            for (int i = 0; i <= deep; i++) {
                ans[i] = now[i];
            }
        }
        return true;
    }
    bool can = false;
    for (int i = max(min_a, get_first(a, b)); ; i++) {
        if (b * (maxdeep - deep + 1) <= i * a) break;
        if (!panduan[i]) {
            now[deep] = i;
            b1 = b * i;
            a1 = a * i - b;
            tmp = gcd(a1, b1);
            if (tmp == 0) tmp = 1;
            if(dfs(deep + 1, i + 1, a1/tmp, b1/tmp)) can =  true;
        }
    }
    return can;
}
int main() {
    scanf("%d", &t);
    for (int T = 1; T <= t; T++) {
        panduan.clear();
        scanf("%d%d%d", &a, &b, &k);
        min_first = get_first(a, b);
        for (int i = 0; i < k; i++) {
            scanf("%d", &q);
            panduan[q] = true;
        }
        for (maxdeep = 1; ; maxdeep++) {
            memset(ans, -1, sizeof(ans));
            if (dfs(0, min_first, a, b)) break;
        }
        printf("Case %d: %d/%d=", T, a, b);
        for (int i = 0; i < maxdeep; i++) {
            printf("1/%d+", ans[i]);
        }
        printf("1/%d", ans[maxdeep]);
        printf("\n");
    }
    return 0;
}

如果有不理解欢迎在讨论区留言，最后，点个赞再走吧 QWQ