题解：P10494 [USACO02FEB] Power Hungry Cows

· · 题解

思路

读完题，我们不难发现此题中的 x 是障眼法，我们其实只需要考虑两个数的幂之间的运算即可。因此，该题的题意等价于：给定两个数 1 和 0，两个数可以互相加减，最少计算多少次可以得到 p。

为什么是加减呢？我们知道：

x^n \times x^m = x^{n+m} x^n \div x^m = x^{n-m}

而我们计算的是幂，当然是加减啦。

代码分析

本题是一道显然的搜索。但使用 dfs 会由于深度太大而 TLE，使用 bfs 则会 MLE（如果你用了 bitset 就当我没说）。即使卡过此题评测，其效率也不够优秀。那么，我们能否将两者结合呢？这种算法就是著名的 IDDFS。

IDDFS 就是给定一个深度，然后在该深度内进行 dfs，既有 dfs 空间小的优点，又结合了 bfs 速度快的优点，用来解决此题是非常合适的。

但是此题如果只使用 IDDFS 而不优化的话，还是会导致 TLE。因此，我们要对 IDDFS 进行剪枝。

接下来，我们称两幂中较大的一项为 x，较小的一项为 y。IDDFS 限制的操作最大次数为 Maxdep，当前操作次数为 dep。

优化 1： 如果 x^{Maxdep-dep} < p，那么无需继续 IDDFS。

证明：容易证明，x 最快增长的方式是倍增。连最快的增长方式都无法得到 p，就无需继续了。

优化 2： 如果 \gcd(x,y) \nmid p，那么无需继续 IDDFS。

证明：感性理解应该不难接受，如果希望获得严谨的证明，请右转 P4549 题解区。

于是我们可以开开心心的开始 IDDFS 了。

AC Code 1

#include<bits/stdc++.h>
using namespace std;
int ansdep,p;
bool IDA(int x,int y,int dep){
    if(x<y) swap(x,y); //保证x不小于y
    if(dep==ansdep){ //到达设置深度
        if(x==p||y==p) return 1; //返回有解
        else return 0;
    }
    if(x<<(ansdep-dep)<p) return 0; //剪枝1
    if(__gcd(x,y)>0&&p%__gcd(x,y)>0) return 0; //剪枝2
    if(IDA(x*2,y,dep+1)) return 1;
    if(IDA(x*2,x,dep+1)) return 1;
    if(IDA(x-y,y,dep+1)) return 1;
    if(IDA(x+y,y,dep+1)) return 1;
    if(IDA(x-y,x,dep+1)) return 1;
    if(IDA(x,y*2,dep+1)) return 1;
    if(IDA(x,y+x,dep+1)) return 1;
    if(IDA(y,y*2,dep+1)) return 1; //枚举所有情况。由于x不小于y，因此不考虑x-y。
    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>p;
    while(!IDA(1,0,0)) //枚举最大深度
        ++ansdep;
    cout<<ansdep;
    return 0;
}

再看一眼数据，诶，好像可以打表！

于是：

Code 2（由于代码长度限制无法 AC，仅供娱乐！）

注 1：为什么 IDDFS 每次增加深度都不保存上一层的结论，效率仍然优秀？因为每一次增加深度，新的节点数量会远超上一层的节点。就像此题，每层的 1 个节点将拓展为 8 个节点，即使有剪枝，也仍然远超上一层的节点数。因此，不记录结果对 IDDFS 影响不大，并且，IDDFS 还有自己独有的剪枝（即本题中的剪枝1），完全可以抵消了。

注 2：第一份代码通过了讨论区的 hack。