方法①
数据1<=n<=1000000,时间复杂度最大O(1000000*6)
暴力足够了,于是,便开始码暴力:
循环枚举i,将i转为字符串,每一位的判断是否超过k:如果每一位都没超过就+1
方法②动态规划
找一找每一位于上一位的关系,可以发现。
设n=236,k=5,如果最后一位的数x大于k,则上一位数,只能取3+1种,所以(k+1)*f[i-1]
设n=234,k=5,如果最后一位x小于或等于k,则上一位数,能取x种,所以g+x*k
方法①代码:
var n,k,i,j,o,l:longint;
s:string;
begin
readln(n,k);
for i:=1 to n do
begin
str(i,s);
o:=0;
for j:=1 to length(s) do
if ord(s[j])-48>k then
begin
o:=1; break;
end;
if o=0 then inc(l);
end;
write(l);
end.
方法②代码:
var n,k,x,g,f:int64;
begin
readln(n,k);
f:=1;
g:=1;
while n>0 do
begin
x:=n mod 10; n:=n div 10;
if x>k then g:=f*(k+1)
else g:=g+f*x;
f:=f*(k+1);
end;
write(g-1);
end.