题解 P2841 【A*B Problem】

F3_Dy · 2021-05-16 18:06:23 · 题解

这道题真的是一道非常有趣的搜索题呢，非常适合使用迭代加深搜索来解决这个问题。

不过看到题解里没有人用迭代加深搜索方法来解这道题，那就我来介绍一下迭代加深搜索的写法!

一般人都会想到这道题的一种搜索写法：枚举a \times b的最小值，然后据此输出b的数值，即可解决问题。但大家可以很明显的注意到，如果使用宽度优先搜索，很可能会有爆空间的风险；如果使用深度优先搜索，则因搜索深度无上限而不可行。

这时候，我们就可以考虑一下：

迭代加深搜索！

1.题意分析

对于本题而言：由于a \times b的规模有限，而且a \times b一定是由0和1两种数字组成，所以使用搜索时解答树并不会过于庞大。因为题意要求找到最小的b，而a为定值，则只要找到最小的a \times b时，b也会最小。

于是，我们可以将本题的题意改写为：找到一个最小的a \times b，使得a \times b\ \% \ a =0。

2.迭代加深搜索

所谓迭代加深搜索，就是一个对于深度优先搜索的一个优化。我们考虑从小到大枚举深度优先搜索的深度上限maxd，每次执行只考虑深度不超过maxd的结点。这样，只要解的深度有限，则一定可以在有限时间内枚举到。

3.一些优化

有了这样的思路，我们可以轻松拿到80分的好成绩。我们接下来考虑如何剪枝。我们可以对当前每一个搜索状态的当前成果进行研究：如果一个状态深度比当前深度浅，或者对应a \times b数值比当前小，且对a取模的数值相同，则当前状态不可能是最优解。

这样，我们可以写出如下代码：

#include<iostream>
#include<cstdio>
using namespace std;
int a,d;
int b[100010];
int m[10010];
int cnt(int x)
{
    if(!x) return 0;
    return cnt(x/10)+1;
}
int dfs(int dep,int o)
{
    if(dep>d)
    {
        if(o==0)
        {
            int f=0,c=0;
            for(int i=1;i<=d;i++)
            {
                c=c*10+b[i];
                if(c>=a)
                {
                    f=1;
                }
                if(f)
                {
                    printf("%d",c/a);
                }
                c%=a;
            }
            printf(" ");
            for(int i=1;i<=d;i++)
            {
                printf("%d",b[i]);
            }
            printf("\n",c/a);
            return 1;
        }
        return 0;
    }
    if(m[o]<=dep&&m[o])
    {
        return 0;
    }
    m[o]=dep;
    if(dep!=1)
    {
        b[dep]=0;
        if(dfs(dep+1,o*10%a))
        {
            return 1;
        }
    }
    b[dep]=1;
    return dfs(dep+1,(o*10+1)%a);
}
void iddfs()
{
    for(d=cnt(a);;d++)
    {
        fill(m,m+a,0);
        if(dfs(1,0))
        {
            break;
        }
    }
}
int main()
{
    cin>>a;
    iddfs();
    return 0;
}