reverse

【问题描述】

我们定义：

我们对于任何正整数，定义一个函数：

比如：reverse(123)=321,reverse(1000)=1,reverse(520)=25。

现在，给出两个正整数L,R，请求出下面这个集合的大小：

【输出文件】

第一行包含三个整数T,a,b分别表示测试数据组数，特殊性质1，特殊性质2(如果该组数据包含特殊性质1，则a = 1，否则a = 0；如果该组数据包含特殊性质2，则b = 1，否则b = 0 )。

接下来T行每行包含两个整数L,R。

【输出文件】

对于每组数据，输出一行，包含一个整数表示答案。

【输入样例】

3 0 0

1 10

10 20

123 12345

【输出样例】

9952

【数据规模和约定】

对于所有数据，T=50。

特殊性质1：L=1。

特殊性质2：R=10k （即所有R都是10的整数次幂）

令1<=L<=R<=N。

一眼看上去是数位dp，但是我并没有做出来qwq

我们只需要求$[1,x]$中的reverse之后在$[l,r]$的数量

我以前数位dp都是递推的，真难写，还是递归版本好写

记录四位状态$f[a,b,x1,x2]$表示还有$a$位可用，该选第$b$位数字了，和$l$,$r$的比较情况是$x1$,$x2$

注意清空数组= =

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define M 110
 4 #define ULL unsigned long long
 5 inline int read() {
 6     char ch = getchar(); int x = 0, f = 1;
 7     while(ch < '0' || ch > '9') {
 8         if(ch == '-') f = -1;
 9         ch = getchar();
10     }
11     while('0' <= ch && ch <= '9') {
12         x = x * 10 + ch - '0';
13         ch = getchar();
14     }
15     return x * f;
16 }
17 ULL dp[M][M][4][4];
18 bool vis[M][M][4][4];
19 int A[M], B[M];
20 int C[M];
21 int at, bt, ct;
22 inline void split(ULL x, int a[],  int &t) {
23     t = 0;
24     while(x) {
25         a[++ t] = x % 10;
26         x /= 10;
27     }
28 }
29 inline int Next(int x, int y, int lst) {
30     if(x < y) return 0;
31     if(x == y) return lst;
32     return 2;
33 }
34 inline ULL dfs(int a, int b, int x1, int x2, bool flag) {
35     if(vis[a][b][x1][x2] && !flag) {
36         return dp[a][b][x1][x2];
37     }
38     if(a == 1) {
39         if(b < at) x1 = 0;
40         if(b < bt) x2 = 0;
41         if(x1 != 0 && x2 != 2) {
42             return 1;
43         }
44         return 0;
45     }
46     int mx = (flag ? C[a - 1] : 9);
47     ULL wt = 0;
48     for(int i = 0; i <= mx; ++ i) {
49         wt += dfs(a - 1, b + 1, Next(i, A[b + 1], x1), Next(i, B[b + 1], x2), flag && (i == mx));
50     }
51     if(!flag) {
52         vis[a][b][x1][x2] = 1;
53         dp[a][b][x1][x2] = wt;
54     }
55     return wt;
56 }
57 inline ULL Do() {
58     ULL Ans = 0;
59     memset(vis, 0, sizeof(vis));
60     memset(dp, 0, sizeof(dp));
61     for(int i = 1; i <= ct; ++ i) {
62         int lim = (i == ct ? C[ct] : 9);
63         for(int j = 1; j <= lim; ++ j) {
64             Ans += dfs(i, 1, Next(j, A[1], 1), Next(j, B[1], 1), (i == ct && j == lim));
65         }
66     }
67     return Ans;
68 }
69 int main() {
70     int T = read();
71     read(), read();
72     while(T --) {
73         memset(A, 0, sizeof(A));
74         memset(B, 0, sizeof(B));
75         memset(C, 0, sizeof(C));
76         ULL L, R;
77         scanf("%llu%llu", &L, &R);
78         split(L, A, at);
79         split(R, B, bt);
80         ULL Ans = 0;
81         split(R, C, ct);
82         Ans += Do();
83         if(L) {
84             split(L - 1, C, ct);
85             Ans -= Do();
86         }
87         printf("%llu
", Ans);
88     }
89 }