DP62. [ZJOI2010]COUNT 数字计数
描述
给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。输入描述
输入文件中仅包含一行两个整数a、b，含义如上所述。输出描述
输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。示例1
输入:
1 99
输出:
9 20 20 20 20 20 20 20 20 20
C 解法, 执行用时: 2ms, 内存消耗: 300KB, 提交时间: 2022-01-07
#include <stdio.h>
#include <math.h>
int lengthOf(const char s[]) {
int i = 0;
while (s[i] != '\0')
++i;
return i;
}
long long parseLongLong(const char s[]) {
long long ans = 0;
int i;
for (i = 0; s[i] != '\0'; ++i)
ans = ans * 10 + s[i] - '0';
return ans;
}
void ll2Str(char dst[], int arr_size, long long num) {
int i = -1, j;
while (num > 0) {
dst[++i] = num % 10 + '0';
num /= 10;
}
if (i == -1)
dst[++i] = '0';
for (j = i / 2; j >= 0; --j) {
char t = dst[j];
dst[j] = dst[i - j];
dst[i - j] = t;
}
for (++i; i < arr_size; ++i)
dst[i] = '\0';
}
long long countDigit(char s[], int len, int i, int d) {
int curr = s[i] - '0', k = len;
long long ans;
if (s[i + 1] == '\0')
return curr < d ? 0 : 1;
if (s[i] == '0')
return countDigit(s, len - 1, i + 1, d);
ans = (long long) pow(10, k - 2) * curr * (k - 1) + countDigit(s, len - 1, i + 1, d);
if (curr > d)
ans += (long long) pow(10, k - 1);
else if (curr == d)
ans += parseLongLong(s + i + 1) + 1;
return ans;
}
long long countAll(char s[], int k) {
int i;
long long ans = (parseLongLong(s) - (long long) pow(10, k - 1) + 1) * k, m = 9;
for (i = 1; i < k; ++i) {
ans += m * i;
m *= 10;
}
return ans;
}
int main() {
char a[15], b[15];
scanf("%s %s", a, b);
int len_a = lengthOf(a), len_b = lengthOf(b);
ll2Str(a, 15, parseLongLong(a) - 1);
long long ans[10];
ans[0] = countAll(b, len_b) - countAll(a, len_a);
for (int i = 1; i < 10; ++i) {
ans[i] = countDigit(b, len_b, 0, i) - countDigit(a, len_a, 0, i);
ans[0] -= ans[i];
}
printf("%lld", ans[0]);
for (int i = 1; i < 10; ++i)
printf(" %lld", ans[i]);
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 384KB, 提交时间: 2021-12-10
#include <stdio.h>
#include <math.h>
void calcu(long long num , long long *digit,int flag)
{
if(num < 0) return;
long long temp_num = num , index = 1;
for(int i=0;i<=temp_num%10;++i)
{
digit[i] += temp_num/10 + 1;
}
++index;
//if(flag==0)
// digit[0] += temp_num%10+1;
temp_num /= 10;
while(temp_num)
{
for(int i=0;i<=temp_num%10;++i)
{
if(temp_num <= 9 && i == 0 && flag != 0) continue;
if(i == 0 && flag != 0)
digit[i] += (temp_num/10>0?(temp_num/10):1) * (long long)pow(10,index-1);
else
digit[i] += (temp_num/10>0?(temp_num/10+1):1) * (long long)pow(10,index-1);
}
++index;
temp_num /= 10;
}
}
int main()
{
long long temp_num_l,num_l,index;
long long temp_num_r,num_r;
long long temp_l[100][3]={{0,0,0}};
long long temp_r[100][3]={{0,0,0}};
long long digit_l[10]={[0 ... 9] = 0};
long long digit_r[10]={[0 ... 9] = 0};
scanf("%lld %lld",&num_l,&num_r);
//--num_l;
temp_num_l = num_l;
temp_num_r = num_r;
index = 1;
while(temp_num_l)
{
temp_l[index][0] = temp_num_l%10;
temp_l[index][1] = temp_l[index][0] * (long long)pow(10,index-1);
temp_l[index][2] = num_l - temp_num_l * (long long)pow(10,index-1);
temp_num_l /= 10;
++index;
}
for(int i=index-1;i>0;--i)
{
calcu(temp_l[i][1]-1 , digit_l ,i==index-1);
digit_l[temp_l[i][0]] += temp_l[i][2]+1;
if(i!=index-1 && i!=1 && temp_l[i][0] == 1)
digit_l[0] += temp_l[i][1];
//printf("0~%lld [%lld,%lld,%lld,%lld,%lld,%lld,%lld,%lld,%lld,%lld]\n",temp_l[i][1],
//digit_l[0],digit_l[1],digit_l[2],digit_l[3],digit_l[4],digit_l[5],digit_l[6],digit_l[7],digit_l[8],digit_l[9]);
}
index = 1;
while(temp_num_r)
{
temp_r[index][0] = temp_num_r%10;
temp_r[index][1] = temp_r[index][0] * (long long)pow(10,index-1);
temp_r[index][2] = num_r - temp_num_r * (long long)pow(10,index-1);
temp_num_r /= 10;
++index;
}
for(int i=index-1;i>0;--i)
{
calcu(temp_r[i][1]-1 , digit_r ,i==index-1);
digit_r[temp_r[i][0]] += temp_r[i][2]+1;
if(i!=index-1 && i!=1 && temp_r[i][0] == 1)
digit_r[0] += temp_r[i][1];
//printf("0~%lld [%lld,%lld,%lld,%lld,%lld,%lld,%lld,%lld,%lld,%lld]\n",temp_r[i][1],
//digit_r[0],digit_r[1],digit_r[2],digit_r[3],digit_r[4],digit_r[5],digit_r[6],digit_r[7],digit_r[8],digit_r[9]);
}
for(int i=0;i<10;++i)
digit_r[i] -= digit_l[i];
while(num_l)
{
++digit_r[num_l%10];
num_l/=10;
}
for(int i=0;i<10;++i)
printf("%lld ",digit_r[i]);
return 0;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2021-11-22
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
const int maxn = 15; //最大数字不超过12位
long long dp[maxn][maxn][maxn]; //十进制数中长度为i，开头为j的数中k的个数
long long bin[maxn]; //i位中所有首位为i的数的个数
long long res[maxn]; //记录0~9个数
int d[maxn];
void init(){ //递推计算出每个整数
bin[1] = 1; //1位首位为1只有1个
for(int i = 2; i <= 13; i++) //后续都是前一个的10倍
bin[i] = bin[i - 1] * 10;
for(int i = 0; i <= 9; i++) //长度为1，以i开头中i的个数都是1
dp[1][i][i]=1;
for(int i = 2; i <= 13; i++)
for(int j = 0; j <= 9; j++)
for(int z = 0; z <= 9; z++){
for(int k = 0; k <= 9; k++)
dp[i][j][z] += dp[i - 1][k][z]; //累加前面的
dp[i][z][z] += bin[i - 1];
}
}
void solve(long long x,int flag){ //计算1到x的所有数码出现次数
int dnum = 0; //记录当前数的位数
long long y = x;
memset(d, 0, sizeof(d));
while(y){ //连除法计算当前x的位数
d[++dnum] = y % 10;
y /= 10;
}
for(int i = 1; i <= dnum - 1; i++)//先计算位数小于当前数的位数
for(int j = 1; j <= 9; j++)
for(int k = 0; k <= 9; k++)
res[k] += (dp[i][j][k] * flag); //累加，flag为1加，-1为减
int temp = dnum;
while(temp){//再计算位数等于当前数的位数
for(int i = 0; i < d[temp]; i++){
if(!i && temp == dnum)
continue;//不能重复计算
for(int j = 0; j <= 9; j++)
res[j] += (dp[temp][i][j] * flag);
}
res[d[temp]] += (x % bin[temp] + 1) * flag;
temp--;
}
}
int main(){
init();
long long a, b;
cin >> a >> b;
solve(b, 1); //计算1到b的所有数码次数
solve(a - 1, -1); //减去1到a-1的所有数码出现次数
for(int i = 0; i <= 9; i++) //输出
cout << res[i] << " ";
cout << endl;
return 0;
}
C 解法, 执行用时: 3ms, 内存消耗: 300KB, 提交时间: 2022-06-22
#include <stdio.h>
long long calcForDigit(long long a, int k) {
if (a == 0) {
return 0;
}
long long x, current, suffix, divide = 1, totalCount = 0;
while(1) {
suffix = a % divide + 1;
current = a / divide;
x = current / 10;
current %= 10;
if (k == 0) {
if (current > k) {
totalCount += ((x - 1 + 1) * divide);
} else if (current == k) {
totalCount += ((x - 1) * divide + suffix);
} else {
totalCount += ((x - 1) * divide);
}
} else {
if (current > k) {
totalCount += ((x + 1) * divide);
} else if (current == k) {
totalCount += (x * divide + suffix);
} else {
totalCount += (x * divide);
}
}
if (k == 0) {
if (x <= 9) {
break;
}
} else {
if (x < k) {
break;
}
}
divide *= 10;
}
return totalCount;
}
long long *calcDigitCount(long long a) {
long long *result = (long long *)malloc(sizeof(long long) * 10);
memset(result, 0, sizeof(long long) * 10);
for (int i = 0; i < 10; i++) {
result[i] = calcForDigit(a, i);
}
return result;
}
int main() {
long long a, b;
scanf("%lld %lld", &a, &b);
long long *digitA, *digitB;
digitA = calcDigitCount(a-1);
digitB = calcDigitCount(b);
for (int i = 0; i < 9; i++) {
printf("%lld ", digitB[i] - digitA[i]);
}
printf("%lld", digitB[9] - digitA[9]);
free(digitA);
free(digitB);
return 0;
}
C 解法, 执行用时: 3ms, 内存消耗: 360KB, 提交时间: 2022-05-08
#include <stdio.h>
#include <math.h>
int lengthOf(const char s[]) {
int i = 0;
while (s[i] != '\0')
++i;
return i;
}
long long parseLongLong(const char s[]) {
long long z = 0;
int i;
for (i = 0; s[i] != '\0'; ++i)
z = z * 10 + s[i] - '0';
return z;
}
void ll2Str(char dst[], int arr_size, long long num) {
int i = -1, j;
while (num > 0) {
dst[++i] = num % 10 + '0';
num /= 10;
}
if (i == -1)
dst[++i] = '0';
for (j = i / 2; j >= 0; --j) {
char t = dst[j];
dst[j] = dst[i - j];
dst[i - j] = t;
}
for (++i; i < arr_size; ++i)
dst[i] = '\0';
}
long long countDigit(char s[], int len, int i, int d) {
int curr = s[i] - '0', k = len;
long long z;
if (s[i + 1] == '\0')
return curr < d ? 0 : 1;
if (s[i] == '0')
return countDigit(s, len - 1, i + 1, d);
z = (long long) pow(10, k - 2) * curr * (k - 1) + countDigit(s, len - 1, i + 1,
d);
if (curr > d)
z += (long long) pow(10, k - 1);
else if (curr == d)
z += parseLongLong(s + i + 1) + 1;
return z;
}
long long countAll(char s[], int k) {
int i;
long long z = (parseLongLong(s) - (long long) pow(10, k - 1) + 1) * k, m = 9;
for (i = 1; i < k; ++i) {
z += m * i;
m *= 10;
}
return z;
}
int main() {
char a[15], b[15];
scanf("%s %s", a, b);
int len_a = lengthOf(a), len_b = lengthOf(b);
ll2Str(a, 15, parseLongLong(a) - 1);
long long z[10];
z[0] = countAll(b, len_b) - countAll(a, len_a);
for (int i = 1; i < 10; ++i) {
z[i] = countDigit(b, len_b, 0, i) - countDigit(a, len_a, 0, i);
z[0] -= z[i];
}
printf("%lld", z[0]);
for (int i = 1; i < 10; ++i)
printf(" %lld", z[i]);
return 0;
}