10pts蒟蒻求助
查看原帖
10pts蒟蒻求助
648772
Liyuqiao11楼主2023/11/6 10:38
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 20;
int l,r,dp[N][N],sum[N],a[N];
int solve(int x){
    int len=0,ans=0;
    bool flag=true;
    if(x==0) return 0;
    while(x>0){
        a[++len]=x%10;
        x=x/10;
    }
    for(int i=1;i<=len-1;i++){
        for(int j=1;j<=9;j++){  
            ans+=dp[i][j];
        }
    }
    for(int i=1;i<a[len];i++){
        ans+=dp[len][i];
    }
    for(int i=len-1;i>=1;i--){
        for(int j=1;j<=i-1;j++){
            for(int k=2;k<=9;k++){
                ans+=dp[j][k];
            }
        }
        for(int k=0;k<a[i];k++){
            if(k==a[i+1]||k==a[i+1]+1||k==a[i+1]-1) continue;
            ans+=dp[i][k];
        }
        if(a[i]==a[i+1]||a[i]==a[i+1]+1||a[i]==a[i+1]-1){
            flag=false;
            break;
        }
    }
    if(flag) ans++;
    return ans;
}
signed main(){
    cin>>l>>r;
    for(int i=1;i<=10;i++){
        for(int j=0;j<=9;j++){
            if(i==1) dp[i][j]=1;
            else{
                dp[i][j]=sum[i-1]-dp[i-1][j-1]-dp[i-1][j+1]-dp[i-1][j];
            }
            sum[i]+=dp[i][j];
        }
    }
    cout<<solve(r)-solve(l-1)<<endl;
    return 0;
}
2023/11/6 10:38
加载中...