7

SPOJの問題「1と0」を解決しようとしています:

特定の正の整数は、1 と 0 のみで構成される 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;
}
4

2 に答える 2

6

問題を解決しました。スニペットは投稿しませんが、コードが遅い理由を指摘します

  1. sukunrt が言ったように、サイズ n の訪問済みの配列を保持する必要があります。ここでは、現在取得されているモジュラスを訪問済みとしてマークして、再度訪問しないようにすることができます。既に訪問済みのモジュラスにいる場合は考慮する必要がないためです。数値を大きくするだけなので（最小値が必要です）、これまでに取得された文字列の一部。つまり、モジュラスにアクセスすると、nで割ったときに剰余としてx得られる0と1で構成される最小の数値が見つかることを意味します。x

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

    parent[i]モジュラスの親モジュラスを格納しiます。

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

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

    また、変更を行った後、最初に最後に「0」を追加して取得した子をプッシュし、次に最後に「1」を追加して取得した子をプッシュする必要があるため、コードは WA を提供します。（自分で証明できます）。

于 2013-06-05T19:40:23.133 に答える
4

ここにヒントがあります。このように考えてください：

必要な数値が X であるとします。X mod N = 0 です。

したがって、N 個の状態、つまり 0-n-1 のみを保存する必要があります。1. から始めて、bfs を実行します。前と同じ残りを持つブランチを破棄する必要があります。その証拠をあなたに残します。

于 2013-06-05T18:27:32.697 に答える