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

· · 题解

这是蒟蒻的第一次发题解,如果有什么错误,dalao们多多指教

思路:

这道题是一道搜索题 (当然了) IDDFS(迭代加深搜索)

在一些搜索问题中，使用普通的DFS可能会让你把时间浪费,而BFS则不好记录状态,然后就有了IDDFS:以BFS的方法跑DFS.

在每次搜索是控制其搜索深度,使得第一次搜索到的解为最优解. 就像是用DFS每次去跑出BFS的某一层.

而DFS的搜索层数是指数增长的,第二层的搜索状态总数加上第一层的搜索状态总数,可能还没有第三层搜索状态总数多,所以说时间的开销其实不怎么大.

在这一道题中,控制的深度就是有几个单位分数了,那我们的思路就有了

代码:

贴出蒟蒻丑陋的代码

// UVA12558 埃及分数 Egyptian Fractions (HARD version)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>

#define MN 200

#define ll long long

using namespace std;

// 快读
inline ll read() {
  ll x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return x * f;
}

// gcd
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }

ll depth;            // 搜索深度
ll ans[MN], ls[MN];  // ans:答案数组  ls:状态数组
bool flag;           // 搜索成功为true
set<ll> fs;          // 如果被标记过放进去

// 判断当前答案是不是更好
inline bool isGood() {
  for (ll i = depth; i > 0; i--)
    if (!ans[i])
      return true;
    else if (ans[i] != ls[i])
      return ls[i] < ans[i];
  return false;
}

// a:分子,b:分母,bottom:最低从哪里开始搜索,d:搜索深度
inline void IDDFS(ll a, ll b, ll bottom, ll d) {
  // 已到达最后一层
  if (d == depth) {
    // 如果到了最后一层b还不能被a整除,或者b/a已经被使用了,就返回
    if (b % a || fs.count(b / a)) return;
    ls[d] = b / a;
    // 如果当前答案更好,那就存储当前答案
    if (isGood()) memcpy(ans, ls, sizeof(ls));
    // 已经有解
    flag = 1;
    return;
  }
  // i在bottom和b/a的最大单位分数里面取最大值,如果按照每一个分数都是比a/b还大,就可以break了
  for (ll i = max(bottom, b / a + 1); a * i < b * (depth - d + 1); i++) {
    // 如果当前i被使用了,就跳过
    if (fs.count(i)) continue;
    ll na = a * i - b, nb = b * i, g = gcd(na, nb);
    ls[d] = i;
    IDDFS(na / g, nb / g, i + 1, d + 1);
  }
}

int main() {
  ll t = read(), a, b, k;  // 见题意
  for (ll j = 1; j <= t; ++j) {
    a = read(), b = read(), k = read();
    // 初始化
    flag = false, fs.clear(), memset(ans, 0x0, sizeof(ans));
    for (ll i = 0; i < k; i++) fs.insert(read());
    for (depth = 2; !flag; depth++)
      memset(ls, 0, sizeof(ls)), IDDFS(a, b, a / b + 1, 1);
    printf("Case %lld: %lld/%lld=1/%lld", j, a, b, ans[1]);
    for (ll i = 2; i < depth; i++) printf("+1/%lld", ans[i]);
    printf("\n");
  }
  return 0;
}