d899 - NOIP2010 1.数字统计

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定範圍 [L, R] 內所有整數中，數字 2 出现的次數。

解題思路

此題的核心思想是預處理。首先，我們計算從 1 到 10000 的每個數字中 2 出现的次數，並將結果儲存在 ans 陣列中。然後，對於給定的範圍 [L, R]，我們使用前綴和的思想，計算從 L 到 R 的數字 2 出现的總次數。具體來說，我們遍歷從 L 到 R 的每個數字，並將 ans[i] 加到總和中。

複雜度分析

• 時間複雜度: O(N + M)，其中 N 是預處理的數字範圍 (10000)，M 是查詢的次數。預處理需要 O(N) 的時間，查詢需要 O(M) 的時間。
• 空間複雜度: O(N)，用於儲存 ans 陣列。

程式碼

#include <stdio.h>
int ans[10001]={0};
void count(){
	int n;
	for(int i=1;i<=10000;i++){
		n=i;
		while(n>0){
			if(n%10==2)
				ans[i]++;
			n/=10;
		}
	}
} 
int main(){
	int a,b;
	count();
	while(scanf("%d%d",&a,&b)>0){
		int sum=0;
		while(a<=b){
			sum+=ans[a];
			a++;
		}
		printf("%d\n",sum); 
	}
}