e528 - 01225 - Digit Counting

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算從 1 到 N 的所有整數序列中，每個數字 (0 到 9) 出現的次數。

解題思路

這題的核心思想是利用前綴和的概念進行預處理。首先，我們建立一個二維陣列 ans[10001][10]，其中 ans[i][j] 表示從 1 到 i 的序列中，數字 j 出現的次數。我們可以通過迭代地計算每個數字的出現次數來填充這個陣列。具體來說，對於每個數字 i，我們將其分解為各位數字，並將對應的數字計數器加 1。然後，對於每個測試案例，我們直接輸出 ans[N][j] 的值，即可得到從 1 到 N 的序列中，數字 j 出現的次數。

複雜度分析

• 時間複雜度: O(N + T * 10)，其中 N 是預處理的最大值 (10000)，T 是測試案例的數量。預處理需要 O(N) 的時間，每個測試案例需要 O(10) 的時間。
• 空間複雜度: O(N * 10)，用於儲存 ans 陣列。

程式碼

#include <iostream>
using namespace std;
int ans[10001][10],n,t;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	for(int i=1;i<=10000;++i){
		int tmp=i;
		for(int j=0;j<10;++j)
			ans[i][j]=ans[i-1][j];
		while(tmp){
			++ans[i][tmp%10];
			tmp/=10; 
		}
	}
	cin >> t;
	while(t--){
		cin >> n;
		for(int i=0;i<10;++i){
			cout << ans[n][i] ;
			if(i==9)cout << '\n';
			else cout << " ";
		}
	}
}