UVA12558 埃及分数 Egyptian Fractions

_LPF_ · 2020-08-14 11:35:48 · 题解

题意描述

题目描述的翻译挺清楚的了。

和原题的区别是多了禁用的分母。（还有毒瘤输入输出）

算法分析

显然这道题没有什么很好的数学方法来解决，所以可以使用搜索。

由于不确定深度，深搜显然无穷无尽。

所以一开始考虑使用广搜，如果不加改变空间复杂度显然呈指数级增长。

1. 使用启发式搜索来实现，但是此题显然没有必要。（有兴趣的可以自行尝试实验）
2. 使用迭代加深（ID）实现，代码较上一方法更容易实现。

不熟悉 ID 的同学可以先找别的题目了解一下。

假设当前已经到了 dep 个数，上一次使用的分母是 last，目前迭代的最深次数是 d。

目前得到的分数和的为 \frac{a}{b}，题目要求的总和是 \frac{x}{y}，当前选的分母是 num。

那么我们可以确定当前分母的上下界：

解释一下：

对于分母的最小值，由于分母单调递增，所以至少是上一个分母 +1。

但是由于显然 \frac{a}{b}+\frac{1}{num}\leq \frac{x}{y}，所以还要取 \min。

对于最大值，显然至少 (d-dep)\times \frac{1}{num}+\frac{a}{b}\geq \frac{x}{y}。

因为分母单调递增，如果即使全部使用当前分母还是不能达到 \frac{x}{y} 就剪枝。

当然为了精度问题，我们可以将其转化为：

注意一下这里 dep 指的是已经进行的个数（当前的未统计，也就是从 0 开始）。

到这里读者就可以开始尝试代码实现了，但是还要注意两点：

1. 分数要约分。
2. 十年 OI 一场空。

代码实现

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set> 
#define int long long
using namespace std;

int x,y,q,T,dep,tot=0;
bool vis[1010];
vector<int>now,ans;
set<int>s;

int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
    return x*f; 
}

int gcd(int x,int y){//最大公约数用来约分。
    while(y^=x^=y^=x%=y);
    return x;
}

void chck(){//更新答案。
    if(ans.empty() || ans.size()>now.size()){ans=now;return;}
    if(now.size()>ans.size()) return;
    for(int i=(int)now.size()-1;i>=0;i--){
        if(now[i]<ans[i]){
            ans=now;return;
        } else if(now[i]>ans[i])
            return;
    }
    return;
}

void dfs(int d,int last,int a,int b){
    //printf("%d %d %d %d\n",d,last,a,b);
    if(a*y>b*x) return;//貌似没什么用的小剪枝，避免出现 a/b>x/y 的现象。
    if(d>=dep){
        if(a*y==b*x) chck();
        return;
    }
    int p=gcd(a,b);//约分。
    a/=p,b/=p;
    int head=max(last,y*b/(x*b-y*a));//最小值。
    for(int i=head;b*y*(dep-d)+a*i*y>=x*b*i;i++){//最大值。
        if(s.count(i)) continue;//禁用的不用。
        now.push_back(i);
        dfs(d+1,i+1,a*i+b,b*i);//加上 1/i 继续 dfs。
        now.pop_back();//回溯。
    }
    return;
}

void init(){//多组数据记得清零。
    now.clear();ans.clear();
    memset(vis,false,sizeof(vis));
    s.clear();
    return;
}

void work(){
    init();
    x=read(),y=read(),q=read();
    int k;
    while(q--){k=read();s.insert(k);}//判断是否禁用。
    int p=gcd(x,y);x/=p,y/=p;//记得约分。
    for(dep=1;ans.empty();dep++)
        dfs(0,2,0,1);//注意初值。
    printf("Case %d: %d/%d=",++tot,x,y);//毒瘤输出。
    printf("1/%d",ans[0]);
    for(int i=1;i<(int)ans.size();i++)
        printf("+1/%d",ans[i]);
    puts("");
    return;
}

signed main(){
    T=read();
    while(T--) work();
    return 0;
}

安利蒟蒻的blog。

完结撒❀。