51nod 1109 01组成的N的倍数(宽搜+剪枝)

本文主要是介绍51nod 1109 01组成的N的倍数(宽搜+剪枝)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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。

Input示例

4

Output示例

100

解题思路

有一个很关键的剪枝——余数的标记，当一个余数已经出现过一次后，在放到队列里继续搜索是多余的运算。加上之后MLE的问题就解决了。

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 1000007
bool vis[maxn];
struct node
{string str;int mod;
} temp,ne;
int n;
int main()
{ios::sync_with_stdio(false);memset(vis,0,sizeof(vis));cin>>n;if(n==1)cout<<"1"<<endl;else{queue<node>qu;temp.str="1";temp.mod=1;vis[1]=1;qu.push(temp);while(!qu.empty()){temp=qu.front();qu.pop();if(temp.mod==0){cout<<temp.str<<endl;break;}ne.str=temp.str+"0";ne.mod=(temp.mod*(10%n))%n;if(!vis[ne.mod]){qu.push(ne);vis[ne.mod]=1;}ne.str=temp.str+"1";ne.mod=(temp.mod*(10%n)+1)%n;if(!vis[ne.mod]){qu.push(ne);vis[ne.mod]=1;}}}return 0;
}

这篇关于51nod 1109 01组成的N的倍数(宽搜+剪枝)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---