题目描述
blablabla
样例
blablabla
算法1
(数位dp+记忆化搜索) $O(x)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n,m;
int memo[12][12];
int f(string& s,int i,int mask,bool limt,bool num)
{
if(i == s.size()) return int(num);
if(!limt && num && memo[i][mask]!=-1) return memo[i][mask];
int res = 0;
if(!num) res += f(s,i+1,mask,false,false);
int up = limt?s[i]-'0':9;
for(int d=1-int(num);d<=up;d++)
{
if(d != 4)
{
if(mask == 6 && d == 2) continue;
res += f(s,i+1,d,limt && d==up,true);
}
}
if(!limt && num) memo[i][mask] = res;
return res;
}
int main()
{
while(1)
{
memset(memo, -1, sizeof memo);
scanf("%d%d", &n, &m);
if(n == 0 && m == 0) break;
string s1 = to_string(n-1);
string s2 = to_string(m);
int res1 = f(s1,0,0,true,false);
memset(memo, -1, sizeof memo);
int res2 = f(s2,0,0,true,false);
printf("%d\n",res2 - res1);
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla