题解 UVA12558 【Egyptian Fractions (HARD version)】

songhn · 2018-03-19 22:07:55 · 题解

这其实就是一个埃及分数问题，可以用迭代加深来处理，不过题目给了限制使用的数，不过可以直接用set来处理STL大法好注释在代码里

#include<bits/stdc++.h>//萌萌的万能头 
using namespace std;
const int maxn=1e5+10;
set<int> pan; //判断是否被使用 
long long a,b;
long long ans[maxn],l[maxn];//ans记录答案路径 l记录dfs时路径 
int n,ok,deep;//deep为深度限制 
long long gcd(long long a,long long b) {return b==0?a:gcd(b,a%b);}//gcd 
long long getfirst(long long a,long long b){return b/a+1;}//找到比a/b小的最大分母 
bool better(int d)//判断最优解 
{
    for(int i=d;i>=0;i--)
    {
        if(ans[i]!=l[i])
        {
            return ans[i]==-1||l[i]<ans[i]; 
        }
    }
    return false;
}
void dfs(int cur,long long from,long long a,long long b)//cur为层数 from为开始分母 a b表示a/b 
{
    if(cur==deep)
    {
        if(b%a||pan.count(b/a)) return;
        l[cur]=b;
        if(better(cur)) memcpy(ans,l,sizeof(long long)*(cur+1));
        ok=true;
        return;
    }
    from=max(from,getfirst(a,b));
    for(int i=from;;i++)
    {
        if(a*i>=b*(deep-cur+1)) return;//剪枝操作 如果后面深度分母全为i都比a/b小则不需要继续深搜 
        if(pan.count(i)) continue;//判重 
        l[cur]=i;                 //a/b-1/i的通分约分操作 
        long long a1=a*i-b,b1=b*i;
        long long temp=gcd(a1,b1);
        dfs(cur+1,i+1,a1/temp,b1/temp);
    }
    return;
}
int main()
{
    int t,c=1;
    scanf("%d",&t);
    while(t--)
    {
        pan.clear();
        scanf("%lld%lld%d",&a,&b,&n);
        for(int i=0;i<n;i++)
        {
            long long x;
            scanf("%lld",&x);
            pan.insert(x);
        }
        ok=false;
        for(deep=1;;deep++)
        {
            memset(ans,-1,sizeof(ans));
            dfs(0,getfirst(a,b),a,b);
            if(ok) break;
        }
        printf("Case %d: %lld/%lld=",c++,a,b);//一波输出 
        printf("1/%lld",ans[0]);
        for(int i=1;i<=deep;i++) printf("+1/%lld",ans[i]);
        printf("\n");
    }
    return 0;
}