首先，这显然是一道比较简单数位dp题，不会的可以去看一下这篇教程。
这题和版子题一样，只不过状态变了一些，直接记忆化搜索即可。
附上代码(详见注释)。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=15;
// len 表示数字的长度
// dp 数组用于记忆化搜索，存储已经计算过的状态
// num 数组用于存储数字的每一位
ll len,dp[N][N][N][2][2][2],num[N];
// dfs 函数进行深度优先搜索
// pos 表示当前处理到数字的第几位
// last 表示上一位数字
// sum 表示当前连续相同数字的个数
// limit 表示当前位是否受到上限的限制
// isok 表示是否已经存在连续三个相同的数字
// is4 表示数字中是否包含 4
// is8 表示数字中是否包含 8
ll dfs(int pos,int last,int sum,bool limit,bool isok,bool is4,bool is8)
{
ll ans=0;
// 如果数字中同时包含 4 和 8，不满足条件，返回 0
if(is4&&is8)return 0;
// 如果已经处理完所有位，判断是否存在连续三个相同的数字
if(pos==0)return isok;
// 如果当前位不受上限限制且不是最高位，并且该状态已经计算过，直接返回结果
if(!limit&&last!=-1&&dp[pos][last][sum][isok][is4][is8]!=-1)return dp[pos][last][sum][isok][is4][is8];
// 确定当前位的上限
int up=(limit?num[pos]:9);
// 枚举当前位可能的数字
for(int i=0;i<=up;i++){
// 跳过前导 0
if(i==0&&pos==len)continue;
if(i==last)
// 如果当前数字和上一位相同
// 如果连续相同数字个数大于等于 2，说明已经有连续三个相同数字，更新 isok 为 true
ans+=(sum>=2 ? dfs(pos-1,i,sum+1,limit&&i==up,true,is4||i==4,is8||i==8) :
// 否则继续搜索，isok 状态不变
dfs(pos-1,i,sum+1,limit&&i==up,isok,is4||i==4,is8||i==8) );
else
// 如果当前数字和上一位不同，重新开始计数
ans+=dfs(pos-1,i,1,limit&&i==up,isok,is4||i==4,is8||i==8);
}
// 如果当前位不受上限限制且不是最高位，记录该状态的结果
if(!limit&&last!=-1)dp[pos][last][sum][isok][is4][is8]=ans;
return ans;
}
ll solve(ll x)
{
len=0;
// 将数字的每一位存储到 num 数组中
while(x){
num[++len]=x%10;
x/=10;
}
// 如果数字长度不是 11 位，不满足条件，返回 0
if(len!=11)return 0;
memset(dp,-1,sizeof(dp));
// 从最高位开始进行深搜
return dfs(len,-1,0,true,false,false,false);
}
signed main()
{
ll a,b;
cin>>a>>b;
cout<<solve(b)-solve(a-1);
return 0;
}
健康查询