tôi đang cố gắng để giải quyết SPOJ problem "Ones and zeros":SPOJ 370 - Ones và số không (ONEZERO)
Một số nguyên dương có đại diện thập phân của họ bao gồm duy nhất của những người thân và số không, và có ít nhất một chữ số một, ví dụ 101. Nếu một số nguyên dương không có thuộc tính như vậy, một số có thể cố gắng nhân nó với một số nguyên dương để tìm hiểu xem sản phẩm có thuộc tính này hay không.
Cách tiếp cận của tôi đối với vấn đề này đơn giản là thực hiện BFS. Lấy chuỗi chỉ chứa '1' và sau đó thực hiện BFS với nó và tại mỗi bước thêm '1' và '0'. Theo dõi số ở dạng chuỗi và phần còn lại cho đến bây giờ. Khi số dư còn lại bằng 0, số được tìm thấy.
Sự cố của tôi là: Mã của tôi mất quá nhiều thời gian cho các trường hợp kiểm tra, ví dụ: 9999 hoặc 99999. Làm thế nào tôi có thể cải thiện thời gian chạy của thuật toán?
// 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;
}
@Christian Ammer - Cảm ơn bạn đã chỉnh sửa! –
Bạn được chào đón, luôn luôn là một ý tưởng hay để đưa mô tả sự cố vào câu hỏi và định dạng mã một cách proberly. –