C - Find The Multiple

说实话,开始一脸懵,主要是不知道怎样往最短路径上想象。。。

【题意】:在一个仅有0,1所组成的数字中找n的最小倍数(所以开头为0当然是不行的),不超过200位(但我做题是没管,也AC了)

【思路】:因为要找n的倍数,当然从最小的一直增大到想要的数字;对于增大的数有两种情况,*10以及*10+1;所以可以采用遍历的方法(看到这里是不是觉得不用搜索似乎也能做,但会超限哦);所以用队列来存取,看作找最小倍数,两种运动方法:及刚才的情况。

【注意】我之前错误是因为忘了每次队列完成后没有清空,造成了内存超限;

代码;

C - Find The Multiple
#include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int n;
//long long ans;
//因为位数可能很大,所以用了long long 
void bfs(long long x)
{
    queue<long long> q;
    q.push(1);
    while(q.size()){
        long long x=q.front();
        q.pop();
        if(x%n==0){
            printf("%lld\n",x);
            return ;
        }
        else {
            q.push(x*10);
            q.push(x*10+1);
                    //当然也可以用循环
                    /*for(int i=0;i<2;i++){
                q.push(x*10+i);
            }*/
        }
    }
    while(q.size()){//搜索完成后要清空的哦
        q.pop();
    }
    return ;    
}

int main(){
        ios_base::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n)
    {
       
        if(n==0) break;
        bfs(1);
        //cout<<bfs(1)<<"\n";
        
    }
    return 0;
}
View Code
上一篇:POJ 1426 Find The Multiple


下一篇:Find The Multiple BFS入门