AcWing 1085. 不要62
原题链接
中等
作者:
最后五分钟
,
2025-04-04 22:11:25
· 江西
,
所有人可见
,
阅读 3
#include<bits/stdc++.h>
#define int long long
#define deg(a) cout << #a << " = " << a << "\n";
#define de(a) cout << #a << " = " << a << " ";
#define x first
#define y second
using namespace std;
const int N=20;
int f[N][10];
int dp(int t)
{
vector<int> num;
num.push_back(t%10),t/=10;
while(t)num.push_back(t%10),t/=10;
int res=0;
int ls=0;
for(int i=num.size()-1;~i;i--)
{
int x=num[i];
for(int j=0;j<x;j++)
{
if(ls==6&&j==2)continue;
if(j==4)continue;
res+=f[i+1][j];
}
if(x==2&&ls==6||x==4)break;
ls=x;
if(!i)res++;
}
return res;
}
void init()
{
for(int i=0;i<10;i++)
{
if(i==4)continue;
f[1][i]=1;
}
for(int i=2;i<N;i++)
for(int j=0;j<10;j++)
for(int k=0;k<10;k++)
{
if(j==4||k==4)continue;
if(j==6&&k==2)continue;
f[i][j]+=f[i-1][k];
}
}
void sol(int l,int r)
{
cout<<dp(r)-dp(l-1)<<endl;
}
signed main()
{
int l,r;
init();
while(cin>>l>>r,l&&r)
{
sol(l,r);
}
return 0;
}