逆天暴力代码0pts求条
查看原帖
逆天暴力代码0pts求条
1058570
tzhengqing楼主2024/7/20 08:56
#include<bits/stdc++.h>
using namespace std;
#define int long long
int l,r,dp[18][10];
int h(int n)
    {
    while(n>=10)n/=10;
    return n;
    }
int p(int n,int ans)
    {
    for(int i=1;i<=n;i++)ans*=10;
    return ans;
    }
unordered_map<int,int>mp;
int d(int n)
    {
    if(n<0)return 0;
    if(n<10)return n+1;
    if(mp[n])return mp[n];
    int ans=0,bn=n,len=0;
    while(bn){len++;bn/=10;}
    int j=h(n);
    for(int i=1;i<j;i++)ans+=dp[len][i];
	//cout<<n<<":"<<ans<<endl;
    ans+=d(p(len-1,1)-1);
	//cout<<n<<":"<<ans<<endl;
    for(int i=0;i<h(n-p(len-1,h(n)));i++)
    	{
    	if(abs(j-i)>1)ans+=d(p(len-2,i))-d(p(len-2,i-1));
		}
	//cout<<n<<":"<<ans<<endl;
    return mp[n]=ans;
    }
signed main()
    {
    cin>>l>>r;
    for(int i=1;i<=17;i++)
        {
        for(int j=0;j<10;j++)
            {
            if(i==1)dp[i][j]=1;
            else 
                {
                for(int k=0;k<10;k++)
                    {
                    if(abs(j-k)>1)dp[i][j]+=dp[i-1][k];
                    }
                }
            }
        }
    cout<<d(r)-d(l-1);
    return 0;
    }
2024/7/20 08:56
加载中...