洛谷 P1980 [NOIP2013 普及组] 计数问题

原题链接
是我退化了吗，我记得大一的时候还是大二的时候做过这个，好像还是一道蓝桥杯的题（也有可能是一次模拟周赛的题）
当时，记得用CPP超时，还是一道填空，然后我不得不用一些“脑筋急转弯”的思路去计算，计数是有规律的。
今天感觉有点难想，于是想先写个暴力解解压，结果...AC了

然后我不甘心，还是想看看这题如何更快解出

#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
// 暴力

int num_x(int num, int x) {
    int ans = 0;

    string tt = to_string(num);
    int length = tt.size();
    vector<char> arr(tt.begin(), tt.end());
    for (int i = 0; i < length; i++) {
        if (arr[i] - '0' == x) ans++;
    }
    return ans;
}

int main() {
    int in_a;
    int x;
    cin >> in_a >> x;
    int ans = 0;
    for (int i = 1; i <= in_a; i++) {
        ans += num_x(i, x);
    }
    cout << ans << endl;
    return 0;

}

暴力nlogn

算法logn

不难发现，即使不用计算机，答案也很容易求出，如：

n=728，x=7

可以按照这样的思路：

个位7:73个 7,17,...,727

十位7:70个 70~79,170~179,...,670~679

百位7:29个 700~728

答案是172

后续再补上

cy