SPOJ 370 - とゼロ（ONEZERO）

Question

は私がSPOJ problem "Ones and zeros"を解決しようとしています：例えば

一定の正の整数が彼らの10進表現が唯一のものとゼロから成る持っていると、少なくとも1つの数字1つを有します101.正の整数にこのようなプロパティがない場合は、正の整数で乗算して、このプロパティがあるかどうかを調べることができます。

この問題に対する私のアプローチは、単にBFSを実行することでした。 '1'のみを含む文字列を取得し、BFSを使用して各ステップで'1'と'0'を追加します。文字列形式の数字と今までの残りの部分を追跡します。余りがゼロの場合、その番号が見つかった。

私の問題は次のとおりです。テストケースでコードが長すぎます。 9999または99999.アルゴリズムの実行時間をどのように改善できますか？

// Shashank Jain 
/* 
    BFS 
*/ 
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <climits> 
#include <string> 
#include <algorithm> 
#include <vector> 
#include <cmath> 
#include <queue> 
#include <stack> 
#define LL long long int 
using namespace std; 
LL n; 
string ans; 

void bfs() 
{ 
    string str,first,second; 
    str+='1'; // number will start with '1' always 
    if(n==1) 
    { 
    ans=str; 
    return; 
    } 
    queue<pair<string,LL> >q; // pair of STRING(number) and long long int 
          // (to hold remainder till now) 
    pair<string,LL>p; 
    p=make_pair(str,1); 
    q.push(p); 
    LL rem,val,temp; 
    while(q.empty()==0) 
    { 
    p=q.front(); 
    q.pop(); 
    str=p.first; 
    val=p.second; 
    if(val==0) // remainder is zero means this is number 
    { 
     ans=str; 
     return ; 
    } 
    // adding 1 to present number  
    temp=val*10+1; 
    rem=(temp)%n; 
    firstone=str+'1'; 
    p=make_pair(firstone,rem); 
    q.push(p); 
    // adding 0 to present number  
    temp=val*10+0; 
    rem=(temp)%n; 
    secondone=str+'0'; 
    p=make_pair(secondone,rem); 
    q.push(p); 
    } 
} 

int main() 
{ 
    int t,i; 
    scanf("%d",&t); 
    while(t--) 
    { 
    scanf("%lld",&n);  
    bfs(); 
    for(i=0;i<ans.size();i++) 
    { 
     printf("%c",ans[i]);   
    } 
    printf("\n"); 
    } 
    return 0; 
} 

Answer 1

私はただ問題を解決しました。私は私のスニペットを投稿していないだろうが、あなたのコードが遅いですなぜ私はポイントを与える

1. としてsukunrtので、訪れたとして、あなたが現在取得率をマークすることができます大きさnの訪問配列を維持する必要があると述べましたすでに訪問されたモジュラスにいる場合は、数字が大きくなる（最低限必要）ため、今まで取得された文字列の部分を考慮する必要がないため、つまりもう一度訪問する必要はありません。あなたがxと言うモジュラスを訪問すると、nで割ったときに余りとしてxを与える0と1からなる最小の数が見つかる。

2. あなたは常にそのように得られた文字列を子に渡します。これはメモリを増やすだけでなく時間も増やします。これを避けるには、サイズがnの両方のvalue[]とparent[]という2つの配列を取るだけです。

   parent[i]は、モジュラスの親モジュラスiを格納する。

   value[i]は、モジュラスi（0 < = i < n）に対応する現在のビットを格納します。

   最後に、モジュラス= 0のためだけに整数をバックトラックすることができます。

   また、コードを変更すると、最後に「0」を追加して取得した子をプッシュし、最後に「1」を追加して取得した子をプッシュする必要があるため、WAが表示されます。 （あなたはそれを自分で証明することができます）。

Answer 2

ここはヒントです。それについてこのように考える：

は、あなたが望む数はX. Xのmod Nであると仮定= 0

ですからのみ格納する必要がNすなわち0-N-1を述べています。 1.で始まり、bfsを実行します。以前と同じ残りの部分を破棄する必要があります。私はあなたに証拠を残します。