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

问题描述

我试图解决 SPOJ问题一和零：

  

某些正整数有其小数重新presentation仅由一和零，并具有至少一个数字1，如101.如果正整数不具有这样的特性，可以尝试通过一些正整数乘以它以找出该产品是否具有这种特性。

我的办法处理这一问题简单地做BFS。以只含 1 字符串，然后做BFS与它在每一步加入 1 和 0 。跟踪字符串形式的数量和剩余至今。当余数为零，则数被发现。

我的问题是：我的code花费的时间太长了测试用例如9999或99999。我怎样才能提高算法的运行时间？

//沙善耆那教 / *      BFS * / ＃包括＆LT;的iostream＆GT; ＃包括＆LT; cstdio＆GT; ＃包括＆LT; CString的GT; ＃包括＆LT; climits＆GT; ＃包括＆LT;字符串＆GT; ＃包括＆LT;算法＆GT; ＃包括＆LT;载体＆GT; ＃包括＆LT; CMATH＆GT; ＃包括＆LT;排队＆GT; ＃包括＆LT;栈＆GT; ＃定义LL得到long long int 使用名字空间std; LL N; 答串; 无效BFS（） {   字符串str，第一，第二;   海峡+ ='1'; //数将启动'1'永远   如果（正== 1）   {     ANS =海峡;     返回;   }   排队＆LT;对＆LT;字符串，LL＆GT; ＆GT;问; //对STRING（数量）和得到long long int                             //（持有其余至今）   对＆LT;字符串，LL指p;   p值= make_pair（海峡，1）;   q.push（对）;   LL REM，缬氨酸，温度;   而（q.empty（）== 0）   {     p值= q.front（）;     q.pop（）;     海峡= p.first;     VAL = p.second;     如果（VAL == 0）//余数为零意味着这是数     {       ANS =海峡;       返回 ;     }     //加入1〜present数量     TEMP = VAL * 10 + 1;     REM =（临时）％N;     firstone =海峡+'1';     P = make_pair（firstone，REM）;     q.push（对）;     //增加0〜present数量     TEMP = VAL * 10 + 0;     REM =（临时）％N;     secondone = STR +'0';     P = make_pair（secondone，REM）;     q.push（对）;   } } 诠释的main（） {   INT T，I;   scanf函数（％d个，＆amp; T公司）;   而（T--）   {     scanf函数（％LLD，和放大器; N）;     BFS（）;     对于（i = 0; I＆LT; ans.size（）;我++）     {       的printf（％C，答[我]）;     }     的printf（\ N）;   }   返回0; }

解决方案

我刚刚解决了这个问题。我不会发表我的片段，但我会给点，为什么你的code是慢

1. 由于sukunrt说你需要保持走访大小为n，在这里你可以为已访问，这样你就不会再访问它标志着当前取得的弹性模量的数组，因为如果你是在一个已经访问过模您并不需要考虑获得至今字符串的一部分，因为它不仅使数字越大（我们需要的最小），也就是说，它一旦你访问你说的模数是指 X 然后你发现最少的0和1组成的，让 X 的其余部分时，用n。隔膜

2. 您总是传递这样得到的孩子，这不仅增加了内存，但时间太长的字符串。为了避免这种情况，只取两个数组说值[] 和父[] 这两个大小为n的。

   父[I] 存储模量的母模量我。

   值[I] 存储作为当前位对应的模量我（0℃= I＆LT ; N）

   在最后，你可以直接原路返回，形成整体数量只为模数= 0。

   另外进行更改后，您的code将使西澳，因为你必须首先推动通过追加'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屋！