阳历劝过,听取蛙声一片
查看原帖
阳历劝过,听取蛙声一片
1420772
liangyimim楼主2025/7/26 11:04
#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[10][2][10];
int dfs(int pos,int limit,int zero,int lst,string &s)
{
	if(pos==s.size())
	{
		return 1;
	} 
	if(!limit&&f[pos][zero][lst]!=-1) return f[pos][zero][lst];
	int res=0;
	for(int i=0;i<=(limit?s[pos]-'0':9);i++)
	{
		if(zero||(!zero&&abs(lst-i)>=2))
		{
			res+=dfs(pos+1,limit&&(i==s[pos]-'0'),zero&&(i==0),i,s);
		}
	}
	if(limit) return res;
	return f[pos][zero][lst]=res;
}
int solve(int x)
{
	memset(f,-1,sizeof(f));
	string s=to_string(x);
	int res=dfs(0,1,1,0,s);
	return res;
} 
signed main()
{
	
	int l,r;
	cin>>l>>r;
	cout<<solve(r)-solve(l-1); 
	return 0;
}

2025/7/26 11:04
加载中...