Спой онезеро, как избежать строк?

Question

В спой проблема онезеро

http://www.spoj.com/problems/ONEZERO/

Я пытаюсь сделать BFS. Как и в каждом штате, я использую остаток на каждом уровне. Прочитав комментарии и многие форумы, я понял, что здесь нельзя использовать строки. Итак, как изменить мой код здесь:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<cctype>
#include<cassert>
#include<climits>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<clocale>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>

//containers
#include<vector>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<complex>
#include<string>
#include<stack>
#include<bitset>
#include<istream>
#include<valarray>

//IOs
#include<iostream>
#include<sstream>
#include<iomanip>
#include<fstream>
#include<exception>
#include<ios>
#include<iosfwd>
#include<ostream>
#include<iterator>
#include<stdexcept>
#include<streambuf>


//algorithm & miscellaneous
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<limits>
#include<locale>
#include<memory>
#include<new>

// My Terms
#define pb push_back
#define mp make_pair
#define ins insert
#define fir first
#define sec second
#define PRINT(x)        cout << #x << " " << x << endl
#define pi acos(-1)
#define ll long long
#define EM empty()
#define sz(a) int((a).size())
#define all(c) (c).begin(),(c).end()
#define fill(a,v)     memset(a, v, sizeof(a))


//http://lab.polygonal.de/?p=81

using namespace std;

int exist[20010];

int main()
{
    int test;
    cin>>test;
    while(test--)
    {
        memset(exist,0,sizeof(int)*20010 );
        int  t;
        cin>>t;

        if(t==1)
        {
            cout<<"1\n";
            break;
        }


        int rem=0;
        string num;

        queue < pair<string,int> > q;  // one for number and one for remainder
        q.push(mp("1",1));


        while(q.size())
        {
            num=q.front().first;
            rem=q.front().second;
            exist[rem]=1;

            q.pop();


            if( rem == 0)
            {
                cout<<num<<"\n";
                break;
            }


            if(exist[((rem*10 +1)%t)]==0 &&   ((rem*10 +1)%t)<20000 )
            {
                q.push( mp(num+'1',((rem*10 +1)%t)   ) ) ;
                exist[((rem*10 +1)%t)]=1;
            }

            if(exist[((rem*10 +0)%t)]==0 && ((rem*10 +0)%t)<20000  )
            {
                q.push( mp(num+'0',  (rem*10 +0)%t ) );
                exist[ ((rem*10 +0)%t ) ]=1;
            }

        }





    }




}

Как я могу избежать строк здесь. Пожалуйста, объясните мне, как это сделать.

Answer 1

Вместо нажатия num + '0' и num + '1'; Вы можете просто передать целое число, которое является десятичным эквивалентом строки. Например: вместо q.push(mp('1001', (rem*10)%t)) вы можете выполнить q.push(mp(9, (rem*10)%t)). Таким образом, вы можете достичь немного большей скорости.

Но это все равно даст TLE. Чтобы преодолеть это, у вас должен быть "посещенный" массив, который запоминает остатки, с которыми вы встречались в прошлом, и поэтому вы не должны снова помещать их в очередь.

Используя массив посещенных, я получил AC