UVA 1640 分块/数位统计/DFS

紫书中给出的解法是分块，非常重要的思想， 但是网上题解给出的更加简单DFS ，统计每位数对答案的贡献即可。 注意边界 具体见代码

#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#define INF 0x3f3f3f3f
#define read(i) scanf("%d",&i)
#define equals(a,b)    (fabs(a-b)<eps)
const int maxn = 1e6 + 5;
const double PI = acos(-1.0);
typedef long long ll;
using namespace std;

int ans[10];

void dfs(int n, int m, int ok) {
    if (n == -1) return;
    int x = n / 10;
    int y = n % 10;
    for (int i = 1; i <= y; i++) ans[i] += ok * m;
    for (int i = 0; i < 10; i++)  ans[i] += ok * m * x;
    int tmp = x;
    while (tmp) {
        ans[tmp % 10] += ok * (y + 1) * m;
        tmp /= 10;
    }
    dfs(x - 1, m * 10, ok);
}


int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2 && n && m) {
        memset(ans, 0, sizeof ans);
        if (n < m) swap(n, m);
        --m;
        dfs(n, 1, 1);
        dfs(m, 1 ,-1);
        for (int i = 0; i < 10; i++) {
            if (i) printf(" ");  printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}