数位dp
数位dp一般两种解法：递推和记忆化搜索。解决的问题大多是某个数或某几个相邻的数在某位上出现或不出现的问题。
不要62
递推法：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 1000005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ull res = 233;
using namespace std;
int dp[12][10];//dp[i][j] i为最高位是j的个数
void init()
{
dp[0][0] = 1;
for(int i = 1; i <= 12; i++){
for(int j = 0; j <= 9; j++){
for(int k = 0; k <= 9; k++){
if(j == 4) continue;
if(j == 6 && k == 2) continue;
dp[i][j] += dp[i-1][k];
}
}
}
}
int len,d[12];
int work()
{
int ans = 0;
d[len+1] = 0;
for(int i = len; i > 0; i--){
for(int j = 0; j < d[i]; j++){
if(j == 4) continue;
if(d[i+1] == 6 && j == 2) continue;
ans += dp[i][j];
}
if(d[i] == 4 || (d[i+1] == 6 && d[i] == 2)){
ans--;
break;
}
}
return ans;
}
int solve(int x)
{
len = 0;
while(x){
d[++len] = x%10;
x /= 10;
}
return work()+1;
}
int main()
{
int n,m;
init();
while(~scanf("%d%d",&n,&m)){
if(n == m && (n == 0)) break;
int ans = solve(m)-solve(n-1);
printf("%d\n",ans);
}
} 记忆化搜索：
Bomb
大意：计算[1,m]种含'49'的数的个数
思路：先算出不含49的数量，再用总的减去。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 1000005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
const ull res = 233;
//__int64 x; scanf("%I64d",&x);
using namespace std;
ll dp[25][15];//dp[i][j] i为最高位是j的个数
void init()
{
dp[0][0] = 1;
for(int i = 1; i <= 25; i++){
for(int j = 0; j <= 9; j++){
for(int k = 0; k <= 9; k++){
if(j == 4 && k == 9) continue;
dp[i][j] += dp[i-1][k];
}
}
}
}
int len,d[25];
ll work()
{
ll ans = 0;
d[len+1] = 0;
for(int i = len; i > 0; i--){
for(int j = 0; j < d[i]; j++){
if(d[i+1] == 4 && j == 9) continue;
ans += dp[i][j];
}
if(d[i+1] == 4 && d[i] == 9){
//ans--;
break;
}
}
return ans;
}
ll solve(ll x)
{
len = 0;
while(x){
d[++len] = x%10;
x /= 10;
}
return work();
}
int main()
{
ll n,m,t;
init();
while(~scanf("%lld",&t)){
while(t--){
scanf("%lld",&m);
ll ans = solve(m+1);
cout << m-ans+1 << endl;
}
}
}
