SPOJ 370 - Ones ve sıfırlar (ONEZERO)

Question

Ben SPOJ problem "Ones and zeros" çözmeye çalışıyorum: örneğin

Bazı pozitif tamsayılar onların ondalık gösterim sadece birler ve sıfırlar oluşan sahiptir ve en az bir rakam biri olan 101. Pozitif bir tamsayı böyle bir özelliğe sahip değilse, ürünün bu özelliğe sahip olup olmadığını öğrenmek için onu bir pozitif tamsayı ile çarpmayı deneyebilirsiniz. Bu sorunun

Benim yaklaşım sadece BFS'ye yapıyordu. Sadece '1''u içeren dizgeyi almak ve daha sonra BFS'yi her adımda '1' ve '0' ekleyerek almak. Dize formunda ve kalan sayıyı bugüne kadar tutmak. Kalan sıfır olduğunda, sayı bulundu.

Sorunum: Test kodlarım için kodum çok uzun sürüyor örn. 9999 veya 99999. Algoritmanın çalışma zamanını nasıl geliştirebilirim?

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

Sadece sorunu çözdüm. Benim parçacığını sonrası değil, ancak kod yavaştır neden puan verecek

1. olarak sukunrt böylece ziyaret ettiği o anda elde modülüne işaretleyebilirsiniz n büyüklüğündeki ait ziyaret bir dizi tutmak gerektiğini söyledi Tekrar ziyaret etmediğiniz için, eğer zaten ziyaret edilmiş bir modülde iseniz, o zamana kadar elde edilen dizginin parçasını sadece daha büyük hale getirdiğinden (minimum ihtiyacımız var), yani x dediğiniz bir modülü ziyaret ederseniz, 0 ve 1'den oluşan en az sayıyı x vererek n'ye bölündüğünüzde geri kalanını bulursunuz.

2. Hep böyle sadece çok bellek ama zaman artmaz çocuğa, elde edilen dize geçmektedir. Bunu önlemek için, her iki boyutta da iki tane daha dizi dizininiz olsun, value[] ve parent[].

   parent[i] mağaza modülü i ana modülü. Modül i'a karşılık gelen mevcut bit olan nolu mağazalar (n = < n).

   Sonuçta sadece tam sayı = 0 değerini oluşturmak için geri dönebilirsiniz. İlk sonunda '1' ekleyerek elde çocuğu sonunda '0' ve sonra ekleyerek elde çocuğu itmek zorunda çünkü

   Ayrıca değişiklik yaptıktan sonra, kodunuz WA verecektir. (Kendinizi kanıtlayabilirsiniz).

Answer 2

İşte bir ipucu. Bu konuda bu şekilde düşünüyorum:

istediğiniz numarayı varsayalım mod N =

0. Yani N yani 0-n-1 devletler sadece saklamak için gereken X. X. 1. ile başlayın ve bfs'yi yapın. Daha önce olduğu gibi aynı kalanı olan dalları atmanız gerekir. Kanıtı sana bırakacağım.