P6 UVA11038 How Many O's？

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