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

zyh2333 · 2019-01-20 09:09:18 · 题解

这道题是老师上午老师讲课时觉得他太啰嗦，自己写的一篇（我才不说这个老师是洛谷管理员）

简单的迭代加深(ID)算法,递增搜索深度,然后在当前确定的搜索深度下做普通的dfs即可，难点就在于bfs时要求下一层的上界和下界.  

下界: max(当前分母+1, 原分母/原分子向下取整)  

上界:当后面所有的数都为当前分母时还是小于左边的数,则后面不可能有结果(分母越来越大,值越来越小).

#include <algorithm>
#include <iostream>
#include <sstream>
#include <utility>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <cstdio>
#include <cmath>
#define met(a,b) memset(a, b, sizeof(a));
#define IN freopen("in.txt", "r", stdin);
#define OT freopen("out.txt", "w", stdout);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int maxn = 1e3 + 10;
const int INF = 0x7fffffff;
const int dir[5][2] = {0,0,-1,0,1,0,0,-1,0,1};

LL a, b, k, c, r[maxn], maxd, st, ans[maxn], aid, res[maxn], rid = 0, step;

LL gcd(LL x, LL y) {
    if(y == 0) return x;
    return gcd(y, x%y);
}

bool dfs(LL x, LL y, LL deep) {
    if(deep == maxd) {
        if(x != 1 || (y <1100 && r[y] == 1)) return 0;
        ans[aid++] = y;
        int f = 0;
        for(LL i = aid-1; i >= 0; --i) {
            if(ans[i] == res[i]) continue;
            if(ans[i] < res[i] || res[i] == -1) { f = 1; break; }
            else break;
        }
        if(f==1) memcpy(res, ans, sizeof(res)), rid = aid;
        --aid; return 1;
    }
    bool ok = 0;
    st = max(st, (y-1)/x+1);
    for(LL i = st; ; ++i) {
        if(y*(maxd-deep+1) <= x*i) break;
        LL ta = x*i - y, tb = y*i, tc = gcd(ta, tb);
        ta /= tc; tb /= tc;
        if(i > 1000 || r[i] == 0) {
            ans[aid++] = i; LL tmp = st; st = i+1;
            if(dfs(ta, tb, deep+1)) ok = 1;
            --aid; st = tmp;
        }
    }
    return ok;

}

void IDAS() {
    maxd = 1; st = (b-1)/a+1;
    for(maxd = 1; ; ++maxd) {
        st = (b-1)/a+1; aid = 0; fill(res,res+maxn, INF); rid = 0;
        if(dfs(a, b, 0)) break;
    }
    printf("1/%lld", res[0]);
    for(LL i = 1; i < rid; ++i) printf("+1/%lld", res[i]); printf("\n");
}
int main() {
    #ifdef _LOCAL
    IN; //OT;
    #endif // _LOCAL

    int kase = 0, t; cin >> t;
    while(t--) {
        scanf("%lld%lld%lld", &a, &b, &k); met(r, 0);
        for(int i = 0; i < k; ++i) scanf("%lld", &c), r[c] = 1;
        printf("Case %lld: %lld/%lld=", ++kase, a, b);
        IDAS();
    }


    return 0;
}