备战蓝桥杯---DFS基础刷题

话不多说，���接看题：

1.注意搜索顺序+枚举方式

首先，看到数据范围，我们就不可以直接每一轮3次的暴力。

我们可以发现a^2的大部分情况>2a以及a+1,并且，我们发现其实1的操作是没有必要的（因为2a以经包括了），因此，我们可以把枚举过程想象成只进行2/3操作，只有实在不行时才选1，注意，如果直接正着做会比较麻烦，如这组数据：

正着做的话存在一个问题那就是我们不知道何时+1，因为+1后可能使后面更优，于是我们考虑反着看就可以发现反着符合刚才说的：

我们考虑最后变成b的前一步，我们发现有只有两种情况，就是*2加上剩下的用加1的操作以及平方加上剩下的用加1的操作（或者就是b-a（当两种都会超b))。

同时加上记忆化搜索即可。

下面是AC代码：

#includeusing namespace std;int t;long long a,b;map mp;long long dfs(long long b){    if(b==a) return 0;    if(mp.count(b)!=0) return mp[b];    mp[b]=abs(b-a);    long long cc=sqrt(b);    if(cc>=a) mp[b]=min(dfs(cc)+1+b-cc*cc,mp[b]);    if(b/2>=a) mp[b]=min(dfs(b/2)+1+b%2,mp[b]);    return mp[b];    }int main(){    cin>>t;    while(t--){        mp.clear();        scanf("%lld%lld",&a,&b);        cout