UVa1225 - Digit Counting(數論 Math theorm)

題目大意：

給你一個數字，產生一組字串資料有 0 to n，請紀錄此字串 0 到 9 個出現幾次。

舉例： n = 5，那字串為 “12345”

題目連結

重點觀念

• 預處理概念

分析

我們稍微可以進行分析，我們可以發現 \(n = 100\) 是最長的字串，但 \(n = 20\) 的字串則是 \(n = 100\) 的子字串，只要是 \(n < 100\) 的都是 \(n = 100\) 的子字串

然後又發現一件事情，這題的查詢基本上都是 \(n = 100\) 的子字串，因此我們可以預處理，從 n = 1 開始不斷紀錄 0 到 9 個出現幾次，然後用一個陣列紀錄，之後將字串再增加長度(\(n+1\)) 就可以紀錄每一種 n 的 0 到 9 個出現幾次，在題目要查詢 n 時就可以直接輸出。

透過預處理的方式，來省略每次的查詢時間。

心得

這題主要是要給你預處理的概念，你要能夠在寫題目時想到裡面的資料大都具由重疊性抑或是向上、向下延伸，就可以想到預處理。

希望我可以將這些概念應用在生活上，讓我可以變得更優秀。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
const int MAXN = 10000; //最大的字串長度
int record[MAXN][10];  //用來記錄 record[字串為 q 時][i] = i 數字的出現次數 
int n, t;

void pretreatment(){
    for(int i = 1; i < 10000; i++){
        int num = i; //表示增加了一個字串為 num
        while(num){ //將字串進行拆解，把每個數字放到 record 中
            record[i][num % 10]++; //字串為 i 時，[ num 的尾數] 出現次數加一
            num /= 10; //將 num 的尾數去掉
        }

        //把 n = i-1 的紀錄傳給 n = i，
        for(int j = 0; j < 10; j++) record[i][j] += record[i-1][j]; 
    }
}


int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // LOCAL
    pretreatment(); //進行預處理
    cin >> n;
    while(n--){ //輸入資料
        cin >> t; //輸入查詢的字串 n，輸出答案

        //嚴格比對
        cout << record[t][0];
        for(int i = 1; i < 10; i++) cout << ' ' << record[t][i];
        cout << '\n';
    }

    return 0;
}