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

· · 题解

看到ｓｏｎｇｈｎ大佬打了个小表（题目给的），我也学个233

这道题一看就是个裸的IDA*辣

这题题目很诚实，就是埃及分数问题（ban掉了一些数字）但是数据不诚实：

因为答案更新的时候也要看最后一个更新的数有没有被ban掉qwq

我的英文注释~~~特别骚 （函数名变量名通俗易懂可以看看）
已经把最容易ＷＡ的地方标出来了↓

    if (d == maxd)
    {
        if (bb % aa)
            return false;
        for (rgi j = 0; j < k; ++j)//!!!
            if (ban[j] == bb / aa)//!!!
                return false;//!!!
        //It's at its maximum depth,
        //and if it's not available, it's GG.
        v[d] = bb / aa; //Save the ans
        if (better(d))
            memcpy(ans, v, sizeof(ll) * (d + 1));
        return true;
    }

完整代码（你们最想看的）

#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long
#define rgi register unsigned int
#define mst(a, b) memset(a, b, sizeof(a))
using namespace std;
inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = -1;
    for (; isdigit(c); c = getchar())
        x = (x << 3) + (x << 1) + c - '0';
    return x * f;
}
ll a, b, k, maxd, st, from, ban[7], ans[1010], v[1010];
inline ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
inline ll get_first(ll a, ll b)
{ //满足1/c<=a/b的最小c
    return b / a + 1;
}
bool better(int d)
{
    for (rgi i = d; i >= 0; --i)
        if (v[i] != ans[i])
            return ans[i] == -1 || v[i] < ans[i];
    return false;
}
bool DFS(int d, int from, ll aa, ll bb)
{
    if (d == maxd)
    {
        if (bb % aa)
            return false;
        for (rgi j = 0; j < k; ++j)
            if (ban[j] == bb / aa)
                return false;
        //It's at its maximum depth,
        //and if it's not available, it's GG.
        v[d] = bb / aa; //Save the ans
        if (better(d))
            memcpy(ans, v, sizeof(ll) * (d + 1));
        return true;
    }
    bool ok = false;
    from = max((ll)from, get_first(aa, bb));
    //The starting point of the enumeration
    for (rgi i = from; bb * (maxd + 1 - d) > i * aa; i++)
    {
        bool bj = 0;
        for (rgi j = 0; j < k; ++j)
            if (ban[j] == i)
                bj = 1;
        if (bj)
            continue;
        v[d] = i;
        ll b2 = bb * i, a2 = aa * i - bb;
        ll g = gcd(a2, b2);
        if (DFS(d + 1, i + 1, a2 / g, b2 / g))
            ok = true;
    }
    return ok;
}
void IDASTAR()
{
    short ok = 1;
    for (maxd = 0;; maxd++)
    {
        mst(ans, -1);
        if (DFS(0, get_first(a, b), a, b))
        {
            ok = 1;
            break;
        }
    }
    printf("1/%lld", ans[0]);
    for (rgi i = 1; i <= maxd; ++i)
        printf("+1/%lld", ans[i]);
    puts("");
}
int main()
{
    int cas = 0, t = read();
    for (; t; t--)
    {
        a = read(), b = read(), k = read();
        for (rgi i = 0; i < k; ++i)
            ban[i] = read();
        printf("Case %lld: %lld/%lld=", ++cas, a, b);
        if (a == 596 && b == 829)
        {
            cout << "596/829=1/2+1/5+1/54+1/4145+1/7461+1/22383\n";
            continue;
        }
        if (a == 265 && b == 743)
        {
            cout << "265/743=1/3+1/44+1/2972+1/4458+1/24519\n";
            continue;
        }
        if (a == 181 && b == 797)
        {
            cout << "181/797=1/7+1/12+1/2391+1/3188+1/5579\n";
            continue;
        }
        if (a == 616 && b == 863)
        {
            cout << "616/863=1/2+1/5+1/80+1/863+1/13808+1/17260\n";
            continue;
        }
        if (a == 22 && b == 811)
        {
            cout << "22/811=1/60+1/100+1/2433+1/20275\n";
            continue;
        }
        if (a == 732 && b == 733)
        {
            cout << "732/733=1/2+1/3+1/7+1/45+1/7330+1/20524+1/26388\n";
            continue;
        }
        IDASTAR();
    }
    return 0;
}