CF1036C Classy Numbers 题解
wxzzzz
·
·
题解
思路
数位 DP。
设 f_{i,j,k} 表示所有位数为 i，最高位为 j，有 k 个数位上的数字为 1\sim 9 的数字个数。
转移：
\displaystyle\sum_{c=0}^9 f_{i-1,c,k-1}\ (j\ne 0,k\ne 0)\end{cases}
初始值：f_{1,0,0}=1,f_{1,1\sim 9,1}=1。
定义 len(x) 表示 x 的位数，d(x,i) 表示 x 的第 i 为上的数字，query(x) 表示 1\sim x-1 中有多少个“好数”，答案为 query(r+1)-query(l)。
1. 位数为 $1\sim len(x)-1$ 的“好数”。
总数为 $\displaystyle\sum_{i=1}^{len(x)-1}\sum_{j=1}^9\sum_{k=1}^3 f_{i,j,k}$。
1. 位数为 ${len}(x)$ 的“好数”，因为要去掉前导零，把最高位单独考虑：
- 考虑第 $1\sim len(x)-1$ 位都与 $x$ 相同，且第 $len(x)$ 位不超过 $d(x,len(x))$ 的“好数”，总数为 $\displaystyle\sum_{i=1}^{d(x,len(x))-1}\sum_{j=0}^3 f_{len(x),i,j}$。
- 考虑第 $1\sim i$ 位都与 $x$ 相同，且第 $i$ 位不超过 $d(x,i)$ 的“好数”，总数为 $\displaystyle\sum_{i=1}^{len(x)-1}\sum_{j=0}^{d(x,i)-1}\sum_{k=0}^{3-cnt(i)}f_{i,j,k}$，其中 $cnt(i)$ 表示 $x$ 的 $i\sim len(x)-1$ 位中有多少位为 $1\sim 9$。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int t, d[25];
long long l, r, f[25][25][25];
long long query(long long x) {
int len = 0;
long long ret = 0;
while (x)
d[++len] = x % 10, x /= 10;
for (int i = 1; i < len; i++)
for (int j = 1; j <= 9; j++)
for (int k = 0; k <= 3; k++)
ret += f[i][j][k];
for (int i = 1; i < d[len]; i++)
for (int j = 0; j <= 3; j++)
ret += f[len][i][j];
for (int i = len - 1, cnt = 0; i >= 1; i--) {
if (d[i])
cnt++;
for (int j = 0; j < d[i]; j++)
for (int k = 0; k <= 3 - cnt; k++)
ret += f[i][j][k];
}
return ret;
}
int main() {
cin >> t;
f[1][0][0] = 1;
for (int i = 1; i <= 9; i++)
f[1][i][1] = 1;
for (int i = 2; i <= 19; i++) {
for (int j = 0; j <= 9; j++) {
for (int k = 0; k <= 3; k++) {
for (int c = 0; c <= 9; c++) {
if (!j)
f[i][j][k] += f[i - 1][c][k];
else if (k)
f[i][j][k] += f[i - 1][c][k - 1];
}
}
}
}
while (t--) {
cin >> l >> r;
cout << query(r + 1) - query(l) << '\n';
}
return 0;
}
```