a和b之间总数,其中包含用于至少一个零 [英] Total numbers between a and b which contains atleast one zero
问题描述
如何找到a和b(含)之间的数字的计数,其中包含0作为它们的数字。我不能够得到这与我在code使用下面的想法,就变得非常复杂的情况下前导零
How to find count of numbers between a and b (inclusive) which contains 0 as their digit. I am not able to get this with the idea which i have used below in my code, it becomes very complex in case of leading zeroes
为前如果= 1,B = 200总数应该是29,但我得到39。
for ex if a=1 and b=200 total number should be 29 but i am getting 39.
任何人都可以提出这样做的有效途径?
Can anyone suggest an efficient way of doing it?
约束:
1<=a<=b<=10^17
code:
code:
long long int F(long long int dig, long long int a, long long int num)
{
if(dig == 0) {
if(a>0)
return 1;
else
return 0;
}
if(mem[dig][a])
return D[dig][a];
mem[dig][a] = 1;
long long int ret = 0;
for(long long int i = 0;i<=9;i++) {
if(i==num)
ret=(ret+F(dig-1,a+1,num));
else
ret=(ret+F(dig-1,a,num));
}
D[dig][a] = ret;
return ret;
}
long long int solve(long long int x,long long int num)
{
char cad[100];
long long int ret = 0;
long long int a=0,b=0,c=0,j;
sprintf(cad,"%lld",x);
int len = strlen(cad);
long long int qued = len;
for(long long int i = 0;i < len;i++) {
qued--;
long long int d = cad[i] - '0';
for(j=0;j <d;j++) {
if(j==num) {
if(num==0 && i==0)
a=a+0;
else
a=a+1;
ret=(ret+F(qued,a,num));
}
else
ret=(ret+F(qued,a,num));
}
if(d==num)
a=a+1;
}
return ret;
}
解决方案 - >解决(B + 1,0)-solve(一,0)
solution is -> solve(b+1,0)-solve(a,0)
但我得到这个错误的答案
but i am getting wrong answer with this
我从中得到了上述思想的链接是的http:// codeforces。 COM /博客/项/ 8221
the link from which i got the above idea is http://codeforces.com/blog/entry/8221
推荐答案
一个简单的方法来做到这一点是:
A Simple way to do it would be:
inList = [1, 2, ... n]
outList = []
for i in inList:
for j in len(i):
if i%10 || i==0:
//there is a 0
outList.add(i)
break;
if(i<10)
//i cannot contain a 0
break;
i=i/10
Probibly唯一带正整数的作品,但它的琐碎占negitive号码。
Probibly only works with positive ints, but its trivial to account for negitive numbers.
根据您的约束简单而有效的O(10N)或O(17N)
Simple and efficient O(10N) or O(17N) according to your constraints
这篇关于a和b之间总数,其中包含用于至少一个零的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!