P4124 70pts 求助
  • 板块灌水区
  • 楼主crz_qwq
  • 当前回复4
  • 已保存回复5
  • 发布时间2024/9/11 22:22
  • 上次更新2024/9/12 15:50:06
查看原帖
P4124 70pts 求助
795344
crz_qwq楼主2024/9/11 22:22
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[15],tot,dp[15][15][15][2][2][2][2];
int dfs(int u,int f,int z,bool o3,bool o4,bool o8,bool lim)
{
	if(o4&&o8)
		return 0;
	if(u==0)
		return o3;
	if(~dp[u][f][z][o3][o4][o8][lim])
		return dp[u][f][z][o3][o4][o8][lim];
	dp[u][f][z][o3][o4][o8][lim]=0;
	for(int i=0;i<=(lim?a[u]:9);++i)
		dp[u][f][z][o3][o4][o8][lim]+=dfs(u-1,i,f,
		o3||(i==f&&i==z),o4||(i==4),o8||(i==8),lim&&(i==a[u]));
	return dp[u][f][z][o3][o4][o8][lim];
}
int solve(int n)
{
	memset(a,0,sizeof a);
	memset(dp,-1,sizeof dp);
	tot=0;
	while(n)
		a[++tot]=n%10,n/=10;
	int ans=0;
	for(int i=1;i<=a[tot];++i)
		ans+=dfs(tot-1,i,0,0,i==4,i==8,i==a[tot]);
	return ans;
}
signed main()
{
	int l,r;
	cin>>l>>r;
	cout<<solve(r)-solve(l-1);
}
2024/9/11 22:22
加载中...