文章目录
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
D
e
s
c
r
i
t
p
i
o
n
Descritpion
Descritpion
S
o
l
u
t
i
o
n
Solution
Solution
C
o
d
e
Code
Code
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://www.luogu.com.cn/problem/P2657
D
e
s
c
r
i
t
p
i
o
n
Descritpion
Descritpion
定义不含前导0且任意相邻两位的差至少为2的数为
w
i
n
d
y
windy
windy数 求
[
L
,
R
]
[L,R]
[L,R]的
w
i
n
d
y
windy
windy数个数
数据范围：
L
,
R
≤
1
0
9
L,R\leq 10^9
L,R≤109
S
o
l
u
t
i
o
n
Solution
Solution
设
f
r
e
s
t
,
l
a
s
t
f_{rest,last}
frest,last表示剩余
r
e
s
t
rest
rest位，上一位填
l
a
s
t
last
last的
w
i
n
d
y
windy
windy数个数 考虑不含前导0带来的影响转移即可
C
o
d
e
Code
Code
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std
;LL L
,R
;
int a
[15],m
;
LL f
[15][10];
inline LL
read()
{
char c
;LL d
=1,f
=0;
while(c
=getchar(),!isdigit(c
)) if(c
=='-') d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
inline LL
dfs(int rest
,int last
,bool lead
,bool limit
)
{
if(rest
==0) return 1;
if(lead
&&limit
==0&&f
[rest
][last
]!=-1) return f
[rest
][last
];
int cancse
=limit
?a
[rest
]:9;
LL res
=0;
for(register int i
=0;i
<=cancse
;i
++)
{
if(abs(i
-last
)<2) continue;
res
+=dfs(rest
-1,(lead
||i
)?i
:-233,lead
||i
,limit
&&i
==cancse
);
}
if(lead
&&limit
==0) f
[rest
][last
]=res
;
return res
;
}
inline LL
solve(LL x
)
{
if(x
<10) return x
+1;
m
=0;
while(x
) a
[++m
]=x
%10,x
/=10;
memset(f
,-1,sizeof(f
));
return dfs(m
,-233,0,1);
}
signed main()
{
L
=read();R
=read();
printf("%lld",solve(R
)-solve(L
-1));
}
