The Counting Problem

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 392K, 提交时间: 2019-11-15 23:54:41

#include <bits/stdc++.h>
using namespace std;

int dp[10][10], tp[10][10][10], t[10], nb[10], b[10], res[10], ans[10];
void init()
{
	t[0] = 1;
	for(int i = 1; i < 10; i++) t[i] = 10*t[i-1];
	memset(dp, 0, sizeof(dp));
	memset(tp, 0, sizeof(tp));
	for(int i = 0; i < 10; i++) tp[0][i][i] = 1;
	dp[0][0] = 1;
	for(int i = 1; i < 9; i++){
		for(int j = 0; j < 10; j++){
			for(int k = 0; k < 10; k++){
				for(int p = 0; p < 10; p++)
					tp[i][j][k] += tp[i-1][p][k];
				if(j == k) tp[i][j][k] += t[i];		
			}
		}
	}
	
	for(int i = 1; i < 9; i++){
		for(int j = 0; j < 10; j++){
			for(int p = 0; p < 10; p++){
				if(j) dp[i][j] += tp[i-1][p][0];
				else dp[i][j] += dp[i-1][p];	
			}
		}
	}
}
int query(int n)
{
	int cnt = -1, cpy = n;
	memset(res, 0, sizeof(res));
	if(!n){res[0] = 1; return 0;}
	while(n){
		nb[++cnt] = n % 10;
		n /= 10;
	}
	for(int i = cnt; ~i; i--)
		b[i] = cpy%t[i], cpy %= t[i];
	for(int i = cnt; ~i; i--){
		for(int j = 0; j < nb[i]; j++){
			for(int k = 0; k < 10; k++)
				res[k] += tp[i][j][k];
			//res[0] += dp[i][j];			
		}
		res[nb[i]] += b[i] +1;
		//printf("%d\n", res[1]);
	}
	for(int j = 0; j < nb[cnt]; j++)
		res[0] += dp[cnt][j] - tp[cnt][j][0];
}

int main()
{
	//freopen("test.txt", "r", stdin); 
	init();
	int n, m;
	while(scanf("%d%d", &n, &m), n&&m){
		if(m < n) swap(n, m);
		query(m);
		for(int i = 0; i < 10; i++) ans[i] = res[i];
		query(n-1);
		for(int i = 0; i < 10; i++)
			printf("%d ", ans[i] - res[i]);
		printf("\n");
	}
}

Java 解法, 执行用时: 45ms, 内存消耗: 10880K, 提交时间: 2021-09-06 17:38:18

import java.util.*;

public class Main {
    static List<Integer> digits;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (true) {
            int a = cin.nextInt();
            int b = cin.nextInt();
            if (a == 0 && b == 0) break;
            for (int i = 0; i < 10; i++) {
                System.out.print((count(Math.max(a, b), i) - count(Math.min(a, b) - 1, i)) + " ");
            }
            System.out.println();
        }
    }
    
    static int count(int n, int x) {
        if (n == 0) return 0;
        digits = new ArrayList<>();
        while (n > 0) {
            digits.add(n % 10);
            n /= 10;
        }
        n = digits.size();
        int res = 0;
        for (int i = n - 1 - (x == 0 ? 1 : 0); i >= 0; i--) {
            if (i < n - 1) {
                res += get(i + 1, n - 1) * power10(i);
                if (x == 0) res -= power10(i);
            }
            if (digits.get(i) == x) res += get(0, i - 1) + 1;
            else if (digits.get(i) > x) res += power10(i);
        }
        return res;
    }
    
    static int get(int l, int r) {
        int res = 0;
        for (int i = r; i >= l; i--) res = res * 10 + digits.get(i);
        return res;
    }
    
    static int power10(int x) {
        int res = 1;
        while (x-- > 0) res *= 10;
        return res;
    }
}

pypy3 解法, 执行用时: 120ms, 内存消耗: 26228K, 提交时间: 2021-08-13 22:44:50

def main():

    while True:
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            break

        if a > b:
            a, b = b, a
        for i in range(10):
            print(count(b, i) - count(a - 1, i), end=" ")
        print()

    return


def count(n, x):
    if n == 0:
        return 0

    num = []
    while n:
        num.append(n % 10)
        n //= 10
    m = len(num)

    res = 0
    start = 0 if x >= 1 else 1
    for i in range(m - 1 - start, -1, -1):
        if i < m - 1:
            res += get(num, m - 1, i + 1) * power10(i)
            if x == 0:
                res -= power10(i)

        if num[i] == x:
            res += get(num, i - 1, 0) + 1
        elif num[i] > x:
            res += power10(i)
    return res


def power10(x):
    res = 1
    while x:
        res *= 10
        x -= 1
    return res


def get(num, l, r):
    res = 0
    for i in range(l, r - 1, -1):
        res = res * 10 + num[i]
    return res


if __name__ == "__main__":
    main()

C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 376K, 提交时间: 2021-03-14 15:08:44

#include<bits/stdc++.h>
using namespace std;
int a[10];
int main()
{
	long long n,m;
	while(cin>>n>>m&&n!=0&&m!=0)
	{
		if(n>m)	swap(n,m);
		long long x=1,f=0;
		while(1)
		{
			for(long long i=1;i<=10;i++)
			{
				if(i<=9&&x*i>m)
				{
					f=1;
					break;
				}
				long long ansn,ansm;
				if(n<x*i)	ansn=0;
				else
				{
					ansn=((n-x*i)/(x*10)+1)*x;
					if(n/x%10==i%10) ansn-=(x-n%x-1);
				}
				if(m<x*i)	ansm=0;
				else
				{
					ansm=((m-x*i)/(x*10)+1)*x;
					if(m/x%10==i%10) ansm-=(x-m%x-1);
				}
				a[i%10]+=ansm-ansn;
				if(n>=x&&n/x%10==i%10)	a[i%10]++;
			}
			x*=10;
			if(f==1)	break;
		}
		for(int i=0;i<=9;i++)
		{
			cout<<a[i]<<" ";
			a[i]=0;
		}
		cout<<endl;
	}
	return 0;
}

Python3 解法, 执行用时: 64ms, 内存消耗: 7184K, 提交时间: 2021-08-13 23:26:59

def main():
    while True:
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            break 
        if a > b:
            a, b = b, a 
        
        for i in range(10):
            print(dfs(b, i) - dfs(a - 1, i), end=" ")
        print()
        
    return 

def dfs(n, x):
    k, p = 0, 1
    res = 0
    last = 0
    while n >= p:
        last = res
        res += (n // (p * 10)) * p + min(max(n % (p * 10) - p * x + 1, 0), p)
        if x == 0:
            res -= p
        k += 1
        p *= 10

    return res if x > 0 else last


if __name__ == "__main__":
    main()

详情