UVA12558 埃及分数

zsaskk · 2019-10-23 11:37:14 · 题解

这个题只有蓝色? 感觉难度还是有的。

很明显要用迭代加深搜索，毕竟直接搜索代价太过庞大。

不了解迭代加深的，可以先做一下 addition chains

有几个小点:

1.a/b>5/6,可以加一个小剪枝，虽然快不了多少。。

2.约分

3.关于通分

a/b-1/c=(a*c/b*c-b/c*b);
-->
next: a=a*c-b,b=b*c;

4.另一个小的剪枝：

检查答案是非否合法，可以在倒数第二层搜索进行。

5.用map判断是否与题目限制冲突

6.界限

分母下界：
mymax(b[dep]+1,m/n)//搜索的单调性与一次取完
分子上界
n*i<(lim-dep+1)*m//可以理解为均分

上代码：

//自认为略微压行不影响代码可读性。
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define int long long
#define chk_digit(c) (c>='0'&&c<='9')
inline int read(){
    reg int x=0,f=1;reg char c=getchar();
    while(!chk_digit(c)) { if(c=='-') f=-1;c=getchar(); }
    while(chk_digit(c)) { x=x*10+c-'0',c=getchar(); }
    return x*f;
}
int t,n,m,k,tim,minl,b[102],ans[102],ok;//ans 答案数组，b 临时数组
map<int,int> vis;
inline int mymax(int x,int y) { return x>=y?x:y; }
inline int gcd(int x,int y) { return y==0?x:gcd(y,x%y); }//两个小函数
inline void chk(int len){
    if(!ans[1]) { for(reg int i=1;i<=len;++i) ans[i]=b[i]; }
    else {
        int flag=0;
        for(reg int i=len;i>=1;--i) {//判断更优解
            if(flag) ans[i]=b[i];
            else {
                if(b[i]>ans[i]) return;
                else if(b[i]<ans[i]) ans[i]=b[i],flag=1;
            }
        }
    }
}
inline void dfs(int n,int m,int dep,int lim){
    if(n<0||m<0) return;
    if(dep==lim-1){//小的剪枝
        if(n!=1||m<=b[dep]) return;
        if(vis.find(m)!=vis.end()) return;
        b[lim]=m;chk(lim);ok=1;return;
    }
    if(n==0) return;
    for(reg int i=mymax(b[dep]+1,m/n);n*i<(lim-dep+1)*m;++i){//上下界
        if(vis.find(i)!=vis.end()) continue;
        int next_a=n*i-m,next_b=m*i,g=gcd(next_a,next_b);
        next_a/=g,next_b/=g;//约分
        b[dep+1]=i;
        dfs(next_a,next_b,dep+1,lim);
    }
}
signed main(){
    t=read();
    while(t--){
        n=read(),m=read(),k=read(),++tim,minl=2,vis.clear();
        printf("Case %lld: %lld/%lld=",tim,n,m);
        int g=gcd(n,m);n/=g,m/=g;
        if(6*n>5*m)  minl=3;//小剪枝
        if(n==1) { printf("%lld/%lld",n,m);continue; }
        for(reg int i=1;i<=k;++i){ int x=read();vis[x]=1; }
        reg int i;
        memset(ans,0,sizeof(ans)),ok=0;
        for(i=minl;;++i){
            memset(b,0,sizeof(b));
            dfs(n,m,0,i);
            if(ok) break;
        }
        for(reg int j=1;j<i;++j) { printf("1/%lld+",ans[j]); }
        printf("1/%lld\n",ans[i]);
    }
}