SPOJ 370 - 一分零(ONEZERO)

Question

我正在尝试解决SPOJ问题"Ones and zero":

某些正整数的十进制表示只包含1和0,并且至少有一个数字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然后你找到由0和1组成的最小数字,x当除以n时给出余数.

2. 你总是把如此获得的字符串传递给孩子,这不仅增加了记忆,也增加了时间.为了避免这种情况,只需再使用两个数组,value[]并且parent[]大小为n.

   parent[i]存储母模数i.

   value[i]存储,它是对应于模数的当前位i(0 <= i <n).

   最后,您可以回溯以形成整数,仅适用于模数= 0.

   此外,在进行更改后,您的代码将给WA,因为您必须首先通过在结尾处附加'0'来获得所获得的子项,然后通过在结尾附加'1'来获得子项.(你可以自己证明).