UVA 11038 - How Many O's?（計數問題）

題目鏈接：11038 - How Many O's?

題意：求[a.b]之間，0出現的次數。 思路：一開始一直往數位DP上去想，結果發現挺復雜的。。 把問題先轉化為求0 - num的個數，在用到b的個數減去到a的個數 其實只要利用計數的乘法和加法原理，把數字對應的每一位的分成左右兩邊，利用乘法原理求總數，在用加法原理把所有的總數加起來就是總情況數。那麼討論一下分成兩邊的情況。舉個例子 比如23045 設中間位為mid，如果mid不為0，假如求到4這個位，那麼左邊的情況就有[1-230]種情況，而右邊則有[0 - 9]種情況，再如果求到3這個位，左邊就有[1- 2]種，右邊有[0 - 999]種，因為右邊不管怎麼取都不會超過數字。 如果mid為0，那麼左邊取[1-22]時，右邊可以隨便取為[1-100]，如果左邊取23，右邊只能取[0-45]。這樣總情況由低位一直往高位去計算就能算出來了 代碼：

#include 
#include 

long long a, b;

long long solve(long long left) {
	if (left < 0) return 0;
	long long ans = 1, mid, right = 0, j = 1;
	while (left >= 10) {
		mid = left % 10; left /= 10;
		if (mid) ans += left * j;
		else ans += (left - 1) * j + right + 1;
		right = right + mid * j;
		j *= 10;
  	}
  	return ans;
}

int main() {
	while (~scanf("%lld%lld", &a, &b) && a != -1 || b != -1) {
		printf("%lld\n", solve(b) - solve(a - 1));
 	}
	return 0;
}