c++ - SPOJ 370 - 一和零 (ONEZERO)

Question

我正在尝试解决 SPOJ problem "Ones and zeros" :

Certain positive integers have their decimal representation consisting only of ones and zeros, and having at least one digit one, e.g. 101. If a positive integer does not have such a property, one can try to multiply it by some positive integer to find out whether the product has this property.

我解决这个问题的方法就是简单地进行 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 然后你找到最小的数字由 0 和 1 组成，当除以 n 时得到 x 作为余数。

2. 你总是把这样得到的字符串传给 child ，这不仅增加了内存，也增加了时间。为避免这种情况，只需再取两个数组，例如 value[] 和 parent[]，它们的大小均为 n。

   parent[i] 存储模数 i 的父模数。

   value[i] 存储对应于模 i (0 <= i < n) 的当前位。

   最后你可以回溯到模数=0的整数。

   此外，在进行更改后，您的代码将给出 WA，因为您必须首先推送通过在末尾附加“0”获得的子级，然后推送通过在末尾附加“1”获得的子级。 (你可以自己证明)。