这篇文章为洛谷P1763埃及分数的题解
本题解主要介绍朴素 IDA* 的解法( 360ms )
首先我们需要明白啥玩意是 IDA*
简单来说 IDA* = 迭代加深搜索 + 剪枝
由于我们不清楚本题需要多少个分子为1的分数去拼凑这个答案
所以我们需要用到迭代加深搜索
从1开始枚举深度，直到找到答案
思路
由题面我们不难看出分数是递减的
下一级分数肯定比上一级分数小
本蒟蒻采用从 a/b 减去枚举的分数，直到达到深度作为边界的方法
枚举深度的同时枚举分母，且该分数刚刚好小于上一级所减去的剩下的 a/b
(下文的 get_first 函数)
我们需要保证分子为 1
所以我们在边界的时候做处理:
1 . 当经过上一级处理剩下的 a/b 分子不为 1 ，return false
2 . 若为 1 ，则将该分母直接作为答案
此时我们得到的解肯定是最优的
( 类比 bfs )
需要用到的函数有 ：
1 . gcd 函数 ( 便于约分 )
2 . better 函数 ( 更新答案 )
3 . get_firs t函数( 返回 ( 1 / c ) <= ( num / deo )的最小正整数 c )
4 . dfs 函数
兼职学习英语 ：
Numerator 分子
Denominator 分母
朴素的迭代代码如下 ：
( 请原谅本蒟蒻害怕溢出时刻用 long long )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000005;
ll a,b;
ll v[maxn],ans[maxn];
ll gcd(ll a,ll b){
if(b==0) return a;
else return gcd(b,a%b);
}
ll get_first(ll a,ll b){
for(ll i=1;;i++) if(double(1.0*1/i)<double(1.0*a/b)) return i;
}
ll better(ll dep){
if(v[dep]<ans[dep]) for(ll i=1;i<=dep;i++) ans[i]=v[i];
}
bool dfs(ll dep,ll c,ll num,ll deo,ll maxd){
if(dep==maxd){
if(deo%num) return false;
v[dep]=deo/num;将该分母直接作为答案
better(dep);
return true;
}
bool ok=false;
c=max(c,get_first(num,deo));
for(ll i=c;;i++){
ll x=num*i-deo;
ll y=deo*i;
ll d=gcd(x,y);
v[dep]=i;
if(dfs(dep+1,i+1,x/d,y/d,maxd)) ok=true;
}
return ok;
}
int main(){
scanf("%lld%lld",&a,&b);
ll tot;
ll c=get_first(a,b);
memset(ans,127,sizeof(ans));
for(ll maxd=1;;maxd++) if(dfs(1,c,a,b,maxd)){tot=maxd;break;}
for(int i=1;i<=tot;i++) printf("%lld ",ans[i]);
return 0;
}
|
但是本题的数据可能不允许你用朴素的迭代写法
后果如下 ：
剪枝
所以我们需要 剪枝
剪枝语句十分简单
当我们枚举分母的时候，分数随着分母增大而减少
所以当我们枚举到前面这个分母 ，此时即使后面所有的数都是该分数 ，减去仍然大于 0 , 那么继续dfs下去也没什么意义
所以只需要在枚举分母时添加上剪枝语句即可
1
2
3
4
5
6
7
8
| for(ll i=c;;i++){
if(deo*(maxd-dep+1)<=num*i) break;
ll x=num*i-deo;
ll y=deo*i;
ll d=gcd(x,y);
v[dep]=i;
if(dfs(dep+1,i+1,x/d,y/d,maxd)) ok=true;
}
|
这样就可以 AC 啦 ~
希望这篇题解对你有所帮助和启发
