51nod 1109 01组成的N的倍数 (bfs)

Description

给定一个自然数 N ,找出一个 M ,使得 M > 0 且 M 是 N 的倍数,并且 M 的 10 进制表示只包含 0 或 1 ,求最小的 M 。

例如:N = 4,M = 100。

 

Input

输入 1 个数 N 。(1 <= N <= 10^6)

 

Output

输出符合条件的最小的 M 。

 

Sample Input

4

 

Sample Output

100

 

思路

POJ 1426 的强化版本,主要是数据的增加。

随着数据范围的扩大,我们搜索的解空间也会相应的成指数级上升,于是这里要考虑一个很好的剪枝:

我们知道, $13\%3=((1 \times 10)\%3+3)\%3$

即,两个数的前缀模一个数的结果相等时,最终结果是否相等由其后缀唯一决定。

于是,我们在考虑搜索时,存在相同的前缀模即剪枝的条件。

PS:C++ 中的 string 类型虽然好用,但只有最后一组数据不能通过(TLE),最后一组数据是 738169

PPS:单纯用数组来存储会 MTE ,我们需要考虑动态分配内存。

PPPS:有种暴力的感觉,当然存在更优秀的解法啦~(出门右拐某大神博客

 

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef __int64 LL;
const int maxn = 1e6+10;
int n,tot;
bool vis[maxn];
queue<char*>sk;

int multget(char* s,int len)
{
    int ans=0;
    for(int i=0; i<len; i++)
        ans=(ans*10+s[i]-'0')%n;
    return ans;
}

void push(const char* s,int len,char c)
{
    char *ne = (char*)malloc(len+2);
    strcpy(ne,s);
    ne[len]=c;
    ne[len+1]=0;
    sk.push(ne);
}

void bfs()
{
    push("",0,'1');
    while(!sk.empty())
    {
        char* s=sk.front();
        sk.pop();
        int len = strlen(s);
        int num = multget(s,len);
        if(num==0)
        {
            puts(s);
            return;
        }
        if(!vis[num])
        {
            push(s,len,'0');
            push(s,len,'1');
            vis[num]=true;
        }
        free(s);
    }
}

int main()
{
    cin>>n;
    bfs();
    return 0;
}