求$A$，$B$之间所有满足相邻两位之间差$geq2$的整数。
对于$100$%的数据，
$1 leq A leq B leq 2 times 10^9$。
Solution
数位$DP$模板题。
令$dp_{i,j}$表示第$i$位，上一位为$j$的总方案数（一直到结束）。
然后逐位$DP$即可。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
ll dp[110][11], d[110];
inline ll (int x, int p) {
if(dp[x][p] + 1) return dp[x][p];
if(!x) return dp[x][p] = 1;
ll res = 0;
for(int q = 0; q < 10; q++)
if(abs(p - q) >= 2)
res += calc(x - 1, q);
return dp[x][p] = res;
}
inline ll solve(ll x) {
int m = 0, ans = 0, pre = -110;
while(x) d[m++] = x % 10, x /= 10;
for(int i = 1; i < m; i++)
for(int j = 1; j <= 9; j++)
ans += calc(i - 1, j);
for(int i = m - 1; i >= 0; i--) {
for(int j = (i == m - 1); j < d[i]; j++)
if(abs(pre - j) >= 2)
ans += calc(i, j);
if(abs(pre - d[i]) < 2) break ;
pre = d[i];
} return ans;
}
int main() {
ll l, r;
memset(dp, -1, sizeof(dp));
scanf("%lld%lld", &l, &r);
printf("%lldn", solve(r + 1) - solve(l));
return 0;
}
|
近期评论