90求改!我没过样例
查看原帖
90求改!我没过样例
696431
lijunxi1楼主2023/8/22 19:49
#include<bits/stdc++.h>
using namespace std;
long long s1,s2,wa[15],w,dp[15][15],M;
long long dfs(long long x,long long sf1,bool sf2)
{
	if(x>w)return sf1;
	if(!sf2&&dp[x][sf1]!=-1)return dp[x][sf1];
	long long put=0;
	if(sf2)
	{
		for(long long i=0;i<wa[w-x+1];i++)
		{
			if(i==M)put+=dfs(x+1,sf1+1,0);
			else put+=dfs(x+1,sf1,0);
		}
		if(wa[w-x+1]==M)put+=dfs(x+1,sf1+1,1);
		else put+=dfs(x+1,sf1,1);
		return put;
	}
	else
	{
		for(long long i=0;i<=9;i++)
		{
			if(i==M)put+=dfs(x+1,sf1+1,0);
			else put+=dfs(x+1,sf1,0);
		}
		return dp[x][sf1]=put;
	}
}
long long q(long long a)
{
	memset(dp,-1,sizeof dp);
	w=0;
	while(a>0)
	{
		w++;
		wa[w]=a%10;
		a/=10;
	}
	return dfs(1,0,1);
}
int main ()
{
	cin>>s1>>s2;
	for(long long i=0;i<=9;i++)
	{
		M=i;
		cout<<q(s2)-q(s1-1)<<" ";
	}
}
2023/8/22 19:49
加载中...