题目 在给定范围内不含前导零，相邻两个数字之间的差异至少为 2 的正整数。 数位dp.这里需要注意的是，有一个前导零的情况，即只有个位数前面是0，可以无脑放置。 O(能过)
// Problem: Windy数 // Contest: AcWing // URL: https://www.acwing.com/problem/content/1085/ // Memory Limit: 64 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<iostream> #include<cstdio> #include<algorithm> #include<complex> #include<cstring> #include<cmath> #include<vector> #include<map> #include<unordered_map> #include<list> #include<set> #include<queue> #include<stack> #define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define fir(i,a,b) for(int i=a;i<=b;++i) #define mem(a,x) memset(a,x,sizeof(a)) #define p_ priority_queue // round() 四舍五入 ceil() 向上取整 floor() 向下取整 // lower_bound(a.begin(),a.end(),tmp,greater<ll>()) 第一个小于等于的 // #define int long long //QAQ using namespace std; typedef complex<double> CP; typedef pair<int,int> PII; typedef long long ll; // typedef __int128 it; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const ll inf = 1e18; const int N = 2e5+10; const int M = 1e6+10; const int mod = 1e9+7; const double eps = 1e-6; inline int lowbit(int x){
return x&(-x);} template<typename T>void write(T x) {
if(x<0) {
putchar('-'); x=-x; } if(x>9) {
write(x/10); } putchar(x%10+'0'); } template<typename T> void read(T &x) {
x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){
if(ch == '-')f*=-1;ch=getchar();} while(isdigit(ch)){
x = x*10+ch-48;ch=getchar();}x*=f; } int n,m,k,T; int a[11]; int f[11][11]; int pos; int dfs(int cur,int pre,bool limit,bool lead) {
if(cur==-1) return 1; auto &tmp=f[cur][pre]; if(!limit&&!lead&&~tmp) return tmp; int up = limit?a[cur]:9; int ans = 0; for(int i=0;i<=up;++i) {
if(lead|| abs(i-pre)>=2) ans += dfs(cur-1,i,limit&&i==up,lead&&i==0); } if(!limit&&!lead) tmp = ans; return ans; } int fun(int x) {
for(pos=0;x;x/=10) a[pos++]=x%10; return dfs(pos-1,0,1,1); } void solve() {
int l,r; cin>>l>>r; cout<<fun(r)-fun(l-1); } signed main(void) {
mem(f,-1); T = 1; // OldTomato; cin>>T; // read(T); while(T--) {
solve(); } return 0; }