UVA11308 How many O's
可以说很经典的数位DP。
但是有一种有趣的更快的做法：
将问题变化一下，如果对于第 \(i\) 位，把它变为 \(0\) ，那么由于不能有前置 \(0\) 且保证构造出的数不能大于原数，所以比 \(i\) 大的位就是 \(1—那么多\)。额，不好说，比如要求 \(0到1145\)，那么假设现在使得 \(4\) 这一位为 \(0\) 了，那么前面能取的数无非就是 \(1到11\)，就是这个意思。还要注意判断前面如果取满了，如对应刚刚例子中的 \(11\)，那么后面就只能取 \(0 \rightarrow 5\)了。
ll n,m;
inline ll solve(ll x){
if(x<0) return -1;
ll res=0;
ll t=0,p=1;
while(x>=10){
ll nx=x/10;
res+=(nx-1)*p+((x%10)?p:(t+1));
t+=x%10*p;
p*=10,x/=10;
} return res;
}
int main(){
IOS
while(cin>>n>>m&&n!=-1&&m!=-1)
cout<<solve(m)-solve(n-1)<<'\n';
return 0;
}
easy.
· EOF