题解：P10494 [USACO02FEB] Power Hungry Cows

· · 题解

题目大意

给定一个目标 x^p，一个初始 x（记为 n，方便后面描述），求最少进行多少次操作能得到目标。

定义一次操作为：将当前 n^m 乘或除以之前已出现过的 n^k,使其变成 n^{m+k} 或 n^{m-k}。

分析

先必须知道一个公式：

n^x \cdot n^y=n^{x+y}

接下来介绍一下 IDDFS。

其实就是给传统 DFS 加上一个深度限制，搜索时超过深度限制就立即停止搜索，适用于搜索树很大而答案在一个比较小的深度内。

显然，本题刚好符合这个条件。

很容易想到可以用一个数组来存下已出现过的 n 的次方，再加一个剪枝。

code1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int p;
int mxdep;
const int P = 20010;
int a[P];

bool dfs(int x ,int dep)
{
    if (dep > mxdep) //如果超过就直接停止 
    {
        return false;
    }
    if (x == p) //搜到了，返回true 
    {
        return true;
    }
    if (x << (mxdep - dep) < p) //可行性剪枝：如果最快的倍增(mxdep - dep)次都到不了，那么直接返回false 
    {
        return false;
    }
    a[dep] = x; //记录下当前x的次方 
    for (int i = 0;i <= dep;i++)
    {
        if (dfs(x + a[i] ,dep + 1)) //乘上x^a[i] 
        {
            return true;
        }
        if (dfs(abs(x - a[i]) ,dep + 1)) //除以x^a[i]，注意要加绝对值，不然有可能会成负数 
        {
            return true;
        }
    }
    return false;
}

int main()
{
    scanf("%d",&p);

    while (!dfs(1 ,0))
    {
        mxdep++; //当前深度限制下搜不到结果，深度限制+1 
    }

    printf("%d\n",mxdep); //第一个满足的深度限制就是最小的答案 

    return 0;
}

结果发现愉快超时了，还要更优。

优化

我们可以省略掉数组 a，把记录次方的参数变成两个，记为 x 和 y，然后搜下一层时对 x 和 y 多讨论几种情况（例如 x 变为 x+y，就相当于 n^x \cdot n^y），也可以做到和数组同样的效果。

当然，这样做并不只是为了省空间，还有一个重要的剪枝：

当 p \bmod \gcd(x,y) \ne 0 时，可以直接返回 false，为什么呢？

令 a=\gcd(x,y)，x=a \cdot m_1，y=a \cdot m_2，则 x+y=a \cdot (m_1+m_2)，x-y=a \cdot (m_1-m_2)，x 和 y 无论怎么加减，都有因数 a，而 p 没有因数 a，所以永远不可能得到 p。

最后就是一些细节问题了（具体简单代码）。

AC code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int p;
int mxdep;

bool dfs(int x ,int y ,int dep)
{
    if (x < y) //防止后面x-y出现负数 
    {
        swap(x ,y);
    }
    if (dep >= mxdep)
    {
        if (x == p || y == p) //x和y有一个等于p就行了 
        {
            return true;
        }
        return false;
    }
    if (x << (mxdep - dep) < p) //剪枝1 
    {
        return false;
    }
    if (__gcd(x ,y) > 0 && p % __gcd(x ,y) != 0) //剪枝2 
    {
        return false;
    }

    //讨论多种情况 
    //乘 
    if (dfs(x * 2 ,y ,dep + 1)) return true;
    if (dfs(x * 2 ,x ,dep + 1)) return true;
    if (dfs(x ,y * 2 ,dep + 1)) return true;
    if (dfs(y ,y * 2 ,dep + 1)) return true;
    if (dfs(x + y ,x ,dep + 1)) return true;
    if (dfs(x + y ,y ,dep + 1)) return true;
    //除 
    if (dfs(x - y ,x ,dep + 1)) return true;
    if (dfs(x - y ,y ,dep + 1)) return true;
    return false;
}

int main()
{
    scanf("%d",&p);

    //和之前一样 
    while (!dfs(1 ,0 ,0))
    {
        mxdep++;
    }

    printf("%d\n",mxdep);

    return 0;
}