[BZOJ 1833] [ZJOI2010] count 数字计数 【数位DP】

题目链接:BZOJ - 1833

题目分析

数位DP ..

用 f[i][j][k] 表示第 i 位是 j 的 i 位数共有多少个数码 k 。

然后差分询问...Get()中注意一下,如果固定了第 i 位,这一位是 t ,那么数码 t 的答案是要加一个值的(见代码)。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std; const int MaxBit = 15; typedef long long LL; struct ES
{
LL A[11];
}; ES operator + (const ES &a, const ES &b) {
ES ret;
for (int i = 0; i <= 9; ++i) ret.A[i] = a.A[i] + b.A[i];
return ret;
} LL A, B;
LL P10[MaxBit]; ES f[MaxBit][11]; ES Get(LL x) {
ES ret;
for (int i = 0; i <= 9; ++i) ret.A[i] = 0;
if (x == 0) return ret;
int l = 1;
while (P10[l] <= x) ++l;
for (int i = 1; i <= l - 1; ++i) {
for (int j = 1; j <= 9; ++j) {
ret = ret + f[i][j];
}
}
//0没有被统计
++ret.A[0];
LL t;
t = x / P10[l - 1];
x %= P10[l - 1];
//如果只有1位,下面这里也会不统计0,但是已经在上面补上了0
for (int i = 1; i <= t - 1; ++i) ret = ret + f[l][i];
ret.A[t] += x;
for (int i = l - 1; i >= 1; --i) {
t = x / P10[i - 1];
x %= P10[i - 1];
for (int j = 0; j <= t - 1; ++j) ret = ret + f[i][j];
ret.A[t] += x;
}
return ret;
} int main()
{
P10[0] = 1ll;
for (int i = 1; i <= 13; ++i) P10[i] = P10[i - 1] * 10ll;
for (int i = 1; i <= 13; ++i) {
for (int j = 0; j <= 9; ++j) {
for (int k = 0; k <= 9; ++k) {
f[i][j] = f[i][j] + f[i - 1][k];
}
f[i][j].A[j] += P10[i - 1];
}
}
scanf("%lld%lld", &A, &B);
ES TA, TB;
TA = Get(A); TB = Get(B + 1);
for (int i = 0; i <= 9; ++i) {
printf("%lld", TB.A[i] - TA.A[i]);
if (i == 9) printf("\n");
else printf(" ");
}
return 0;
}

  

上一篇:html5的自定义data-*属性和jquery的data()方法的使用


下一篇:hive 全局排序