C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 488K, 提交时间: 2019-01-16 15:23:40

#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
int a[20];
long long dp[20][2][2][2];
long long dfs(int l,bool index,bool o,bool v,bool e)
{
    if(l<0)
        return e;
    if(!index&&dp[l][o][v][e]!=-1)
        return dp[l][o][v][e];
    int up=index?a[l]:9;
    long long ans=0;
    for(int i=0; i<=up; i++)
    {
        ans+=dfs(l-1,index&&i==up,i==5,i==2&&o,(!i&&v)||e);
    }
    if(!index)dp[l][o][v][e]=ans;
    return ans;
}
long long wei(long long m)
{
    int cnt=0;
    while(m)
    {
        a[cnt++]=m%10;
        m/=10;
    }
    return dfs(cnt-1,true,false,false,false);
}
int main()
{
    int t;
    cin>>t;
    memset(dp,-1,sizeof(dp));
    while(t--)
    {
        long long n;
        scanf("%lld",&n);
        printf("%lld\n",wei(n));
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 492K, 提交时间: 2020-03-16 21:09:55

#include<iostream>
using namespace std;
typedef long long LL;
int bit[20];
LL dp[20][10][10];
LL dfs(int pos,int f,int s,int limit)
{
	if(pos==-1) return 1;
	if(!limit&&dp[pos][f][s]) return dp[pos][f][s];
	LL res=0,up=limit?bit[pos]:9;
	for(int i=0;i<=up;++i)
	{
		if(f==5&&s==2&&i==0) continue;
		res+=dfs(pos-1,s,i,limit&&i==bit[pos]);
	}
	if(!limit) dp[pos][f][s]=res;
	return res;
}
LL cal(LL x)
{
	int d=0;
	while(x)
	{
		bit[d++]=x%10;
		x/=10;
	}
	return dfs(d-1,0,0,1);
}
int main()
{
	LL t,n;
	cin>>t;
	while(t--)
	{
		cin>>n;
		cout<<n-cal(n)+1<<endl;
	}
	return 0;
}