SPOJ 370 - 一和零（ONEZERO） [英] SPOJ 370 - Ones and zeros (ONEZERO)

问题描述

我正在尝试解决 SPOJ问题一和零：

某些正整数的十进制表示仅由1和0组成，并且至少有一个数字，例如如果正整数没有这样的属性，可以尝试乘以一些正整数，以确定产品是否具有此属性。

我的做法是简单的做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 to 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）//余数为零表示这是数字
 {
 ans = str; 
 return 
} 
 //将1加到当前数
 temp = val * 10 + 1; 
 rem =（temp）％n; 
 firstone = str +'1'; 
 p = make_pair（firstone，rem）; 
 q.push（p）; 
 //将0加到当前数
 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  {
 printf（％c，ans [i]）; 
} 
 printf（\\\
）; 
} 
 return 0; 
} 
  

解决方案

1. 由于sukunrt表示您需要保留访问大小为n的数组，其中可以将当前获取的模数标记为已访问，以便您不再次访问它，因为如果您处于已访问的模数，则不需要考虑到现在为止获取的字符串部分因为它只是使数字更大（我们需要最小），即它意味着一旦你访问一个模数你说 x 那么你会发现最小的数字组成的0和1给出 x 作为余数除以n。




2. 这不仅增加了记忆，但也增加了时间。为了避免这种情况，只需要两个数组，例如两个大小为n的 value [] 和 parent [] p>
   
   

   parent [i] 存储父模数 i

   
   
   

   value [i] 是对应于模的当前位的存储 i （0 <= i
   
   

   最后，你可以回溯以形成整数，只是为了模数= 0。

   
   
   

   此外，在进行更改之后，您的代码将给予WA，因为您必须首先推送通过在末尾添加'0'获得的子项，然后通过追加'1 结束。 （你可以自己证明）。

I am trying to solve 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.

My approach to this problem was simply doing BFS. Taking string containing only '1' and then doing BFS with it and at each step adding '1' and '0'. Keeping track of number in string form and remainder till now. When remainder is zero, the number was found.

My problem is: My code is taking too long for test cases e.g. 9999 or 99999. How can I improve the runtime of the algorithm?

// 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;
}

解决方案

I just solved the problem. I would not post my snippet, but I will give the points why your code is slower

1. As sukunrt said you need to keep an array visited of size n, where you can mark the currently obtained modulus as visited so that you don't visit it again, because if you are at an already visited modulus you don't need to consider the part of string obtained till now as it only makes the number larger(we need minimum), i.e it means once you visit a modulus you say x then you find the least number composed of 0 and 1 that gives x as remainder when divide by n.

2. You always pass the string so obtained to the child, which not only increase the memory but time too. To avoid this, just take two more arrays say value[] and parent[] both of size n.

   parent[i] stores the parent modulus of modulus i.

   value[i] stores which is the current bit corresponding to modulus i (0 <= i < n).

   In the end you can just backtrack to form the whole number just for modulus=0.

   Also after making changes, your code will give WA because you have to first push the child obtained by appending '0' at end and then the child obtained by appending '1' at end. (You can prove it yourself).

这篇关于SPOJ 370 - 一和零（ONEZERO）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！