题解-UVA12558

· · 题解

UVA12558 埃及分数 Egyptian Fractions (HARD version)

就迭代加深搜索板子（

迭代加深

DFS: 空间消耗小，时间大
BFS: 空间消耗大，时间小

为什么 DFS 空间消耗小？因为只需要存当前这条路径的信息，这也决定了它很难有高效的优化。
为什么 BFS 空间消耗大？因为需要存从搜索树第一层到当前层的所有东西，也很难有优化。

迭代加深搜索算法 (IDDFS) ，就是用 BFS 的方法跑 DFS 可以同时优化时间、空间。

算法的过程是：从小到大枚举搜索树的深度，每次对于一个深度跑 DFS。

枚举深度和 BFS 很像，但是我们考虑的是跑 DFS，同时提前知道深度可以用来剪枝。

什么题型适合使用迭代加深搜索呢？对于

的题，就可以采用 IDDFS。

题解

题意：把 \dfrac{y}{x} 分成 \dfrac{1}{a_1}+\dfrac{1}{a_2}+\cdots + \dfrac{1}{a_n} 的形式，使得 a_1\lt a_2\lt\cdots\lt a_n 且其中不得出现 q_1,q_2,\cdots,q_k 中任意一个整数。最后保证 n 最小的同时 a 的字典序最小。

solution

这不是简单 DFS + 回溯吗？

但是一想，a_i 没有上界，虽然我们要求的 n 肯定是不大的，但是理论是可以搜到无穷大。那么这个算法一定会超时。

考虑使用 IDDFS，搜索树的深度可以理解为使用了几个分数。

由于讲的是 IDDFS，关键点就是：使用已知的深度进行剪枝，假如我们已经找到 i 个分数 \dfrac{1}{a_1},\dfrac{1}{a_2},\cdots,\dfrac{1}{a_i}，可以用剩余和与 \dfrac{dep-i+1}{a_{i+1}} 作比较，如果不小于，那么可以直接跳过。

其它就是正常的 DFS。

// author: One_Zzz
#include<stdio.h>
#include<string.h>
#include<vector>
#include<unordered_set>// unordered_set 其实只是哈希实现set，功能相同，没有排序
#define int long long
const int& max2(const int& a,const int& b){return a > b ? a : b;}
const int& min2(const int& a,const int& b){return a < b ? a : b;}
inline int gcd(int a,int b){return b == 0 ? a : gcd(b,a % b);}
inline int read(){
    register int x = 0;
    register char c = getchar();
    for(;c < '0' || c > '9';c = getchar());
    for(;c >= '0' && c <= '9';c = getchar())
        x = x * 10 + (c ^ '0');
    return x;
}
std::unordered_set<int> s;// 保存q数组，使用.count(x)避免q中出现x
int dep;// 当前深度
int n,m,k,a[10001],res[10001];
// a:当前的a,res:答案
bool good(){// 判断当前是否比答案更优
    for(int i = dep;i >= 0;--i)
        if(a[i] != res[i]) return !res[i] || a[i] < res[i];
    return false;
}
bool dfs(int d,int x,int y,int last){
    if(d == dep){// 搜完了
        if(y % x) return false;// 如果剩下不是1/(y/x)，返回
        if(s.count(y / x)) return false;// 如果q中出现了
        a[d] = y;// 记录答案
        if(good()){// 如果更优，更新答案
            for(int i = 0;i <= dep;++i)
                res[i] = a[i];
        }
        return true;
    } 
    bool flg = false;// 是否找到
    for(int i = max2(last + 1,y / x + 1);;++i){
        if(s.count(i)) continue;// 出现过就跳过
        if(y * (dep - d + 1) <= i * x) break;// 剪枝，由于判断的是两个分数大小，所以可以乘上两个分母
        a[d] = i;// 记录i
        // 计算 x/y-1/i，使用通分，答案=y*i/x*i-y
        int newx = x * i - y,newy = y * i;
        int GCD = gcd(newx,newy);// 除以gcd
        newx /= GCD,newy /= GCD;
        flg |= dfs(d + 1,newx,newy,i);
    }
    return flg;// 返回是否找到
} 
bool iddfs(){
    for(dep = 1;;++dep){// 枚举深度
        memset(res,0,sizeof res);// 每个深度都要清空答案
        if(dfs(0,n,m,m / n)) return true;// 找到了赶紧走！
    }
}
signed main(){
    int T = read(),Case = 0;
    while(T--){
        n = read(),m = read(),k = read();
        s.clear();
        for(int i = 1;i <= k;++i) s.insert(read());// 插入set
        iddfs();// IDDFS主体函数
        // 毒瘤输出
        printf("Case %lld: %lld/%lld=1/%lld",++Case,n,m,res[0]);
        for(int i = 1;i <= dep;++i) printf("+1/%lld",res[i]);
        printf("\n");
    }
    return 0;
}