0WA求调
查看原帖
0WA求调
1414950
a_void楼主2025/8/31 17:54
#include<bits/stdc++.h>
#define int long long
using namespace std;int len,ans,dp[20][10][2][3][3];//position|digit|the same|max same|four&eight
int solve(string a){
	len=a.size();a="~"+a;memset(dp,0,sizeof(dp));dp[0][0][1][0][0]=1;
	for(int pos=0;pos<len;pos++)
	for(int pre=0;pre<=9;pre++)
	for(int same=0;same<=1;same++)
	for(int mxs=0;mxs<=2;mxs++)//0=>1 1=>2 2=>3
	for(int f48=0;f48<=2;f48++)//0=>NULL 1=>only4 2=>only8
	for(int nxt=0;nxt<=9;nxt++){
		int d=a[pos+1]-'0';
		if(same&&nxt>d)continue;
		if((f48==1&&nxt==8)||(f48==2&&nxt==4))continue;
		dp[pos+1][nxt][same&&nxt==d][mxs==2?2:(nxt==pre?min(2ll,mxs+1):0ll)][nxt==4?1:(nxt==8?2:0)]+=dp[pos][pre][same][mxs][f48];
	}
	ans=0;for(int lst=0;lst<=9;lst++)
	for(int same=0;same<=1;same++)
	for(int f48=0;f48<=2;f48++)
	ans+=dp[len][lst][same][2][f48];
	return ans;
}
main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	long long l,r;cin>>l>>r;cout<<solve(to_string(r))-solve(to_string(l-1));
}
2025/8/31 17:54
加载中...