题解 UVA12558 【埃及分数 Egyptian Fractions (HARD version)】

blct · 2019-01-28 19:09:38 · 题解

题目

蒟蒻认为此题难度挺大，（dalao除外）不过要用搜索大家应该还是看得出来的。（dfs）

任何一个真分数a/b（且a小于b）一定能表示成埃及分数之和，因此一定能搜索到解。
但是不剪枝的话是会T掉的哦~~
按a/b可拆分成的单位分数的个数进行循环搜索。
1）先将a/b分子分母消去因子，化为最简形式。
2）如果a=1则直接输出b。
3）否则从拆分成2个项开始尝试。如果2个单位分数无法拼凑成a/b，则试3个……依此类推。那么我们搜索得到的第一个解一定会满足加数个数最少这个要求。
4）如果当加数个数等于n项，且当前正在试探第m项（m大于等于1，且小于等于n）的时候，因此应从最小分母开始试探。

先定义符号：
n为需要的单位分数个数，n从2个开始尝试，不成功而后3个……
m表示当前正在搜索第m个分数（m从1到n）
egp【m】存储当前搜索得到的第m个分数的分母
a/b为题目输入的真分数

蒟蒻之前做的题是用最好的埃及分数表示法来表示分数中的分母，从小到大依次输出。

所以说程序直接交是过不了的哦，起码也要自己改一下：

#include <bits/stdc++.h>
const int m = 100;
int d = 0 , min , c;
int ans[m] , out[m];
void find(int a , int b , int x) {
    if (d >= c || x >= min) {
        return;  
    }
    if (b % a == 0) {
        b /= a;
        if (b < x || b >= min) {
            return;
        }
        ans[d] = b;
        min = b;
        memcpy(out , ans , (d + 1) * sizeof(int));
        return;
    } else {
        if (d >= c - 1) {
            return;
        }
        while (a * x <= b && x < min) {
            x++;
        }
        while (x < min) {
            if (a * x >= b * (c - d)) {
                break;
            }
            ans[d] = x;
            d++;
            find(a * x - b , b * x , x + 1);
            d--;
            x++;
        }
    }
    return;
}
int main() {
    int a , b;
    cin >> a >> b;
    min = 1000000;
    for (c = 1;c <= m;c++) {
        find(a , b , 1);
        if(min < 1000000) {
            break;
        }
    }
    for (int k = 0;k < c - 1;k++) {
        cout << out[k];
    }
    cout << out[c - 1];
    return 0;
}

这是蒟蒻第二次正式发题解（第一次没过），dalao们多多指教哦~~（如果能过的话QAQ）