Digital DP (template)

digit dp The question type is often like this ：

Give an interval [L,R], Find that this interval satisfies “ Some condition ” The total number of the number of .

subject ： Find interval [L,R] How much is in the range of 3 Number of numbers , So called band 3 The number of is this number. There is at least one digit in the decimal representation 3

such as 3,,123,3333, All with 3 Number of numbers , Such as 12,456,1000 It's all without 3 Number of numbers

Input : One line contains two integers L,R（1<=L<R<1e12）

Output ： Output an integer to represent the interval [L,R] Within the range with 3 The number of

Example ： Input 100 2000

Output ：19

In digital dp Because the number is too large , Basically use memory search , Through analysis, we can know , stay dfs A lot of numbers and the front dfs The calculated number is the same , As long as it's not in the limit bit , Let's just save it and use it directly

 

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 15
int num;
int* a = new int[maxn];
int f[15];
//int a[maxn];
int b[maxn];//b Save the first p What you save for is that number 
int ten[maxn];
int L, R;
int t;
int dfs(int p, bool limit) {//p Said in the first p position ,limite Indicates whether it is in the limit bit at this time 
	if (p < 0) {
		//for (int i = 2; i >= 0; i--)cout << b[i];// Infinite recursion , Remember to add the end return
		//cout << endl;
		return 0;// End of the search , return 
	}
	if (!limit && f[p] != -1) {// Memory search , Not in the limit bit , also f[p] It's been counted 
		return f[p];
	}
	int up = limit ? a[p] : 9;// Judge whether it is in the limit position , If so, you can only get a[p] by , Otherwise, the highest position can be taken 9

	int ans = 0;

	for (int i = 0; i <= up; i++) {
		//b[p] = i;
		if (i == 3) {
			if (limit && i == up) {
				ans += 1;
				for (int j = p - 1; j >= 0; j--)// Count all conditions below the limit 
					ans += a[j] * ten[j];
			}
			else// If you are not in a restricted condition, add 10 Of p Power 
				ans += ten[p];
		}
		else ans += dfs(p - 1, limit && i == up);// Fill in here a[p] You can fill in up It's OK , At a time of limitation up be equal to a[p]

	}
	if (!limit)// Memory search , If you are not in a restricted condition, you can directly use the number that has been calculated once , Can save a lot of time 
		f[p] = ans;
	return ans;
}

int handle(int num) {
	int p = 0;
	while (num) {// hold num Put each bit in the array 
		a[p++] = num % 10;
		num /= 10;
	}
	// explain a The array is written in , But what does it mean to read invalid data , It didn't seem like this before , terms of settlement , Dynamically creating an array 
	/*for (int i = 0; i < p; i++) {
		cout << a[i];
	}*/
	return dfs(p - 1, true);// The highest corresponding position is p-1 position , by True Indicates that it is not in the limit bit 
}

void init() {
	ten[0] = 1;
	for (int i = 1; i < 15; i++) {
		ten[i] = ten[i - 1] * 10;
	}
	memset(f, -1, sizeof(f));
}
int32_t  main() {
	cin>>t;
    while(t--){
        cin>>L>>R;
        //handle(23);
	    init();// Remember to initialize ,TM Yes, I've been stuck here for half a month 
	    cout << handle(R)-handle(L) << endl;
	    delete[]a;
    }
    return 0;
}

If you want to output without 3 Just modify the function of the above code

dfs The function is modified as follows ： If it's a belt 3 The number of is directly continue fall , Instead of taking 3 Add up the numbers

int dfs(int p, bool limit) {//p Said in the first p position ,limite Indicates whether it is in the limit bit at this time 
	// Beg without 3 The number of 
	if (p < 0)return 1;// It shows that the number of bits is completely recursive 
	if (!limit && f[p] != -1)return f[p];// Memory search , Directly return the calculated value , Reduce computing time 
	int up = limit ? a[p] : 9;
	int ans = 0;
	for (int i = 0; i <= up; i++) {
		if (i == 3)continue;
		ans += dfs(p - 1, limit && i == up);
	}
	if (!limit)f[p] = ans;// Memory search 
	return ans;
}

handle Function modification ： Because we have to use num therefore num The value of cannot be changed , To define another num To calculate num Every digit of ：

int handle(int num) {
	int p = 0;
	int x = num;
	while (x) {// hold num Put each bit in the array 
		a[p++] = x % 10;
		x /= 10;
	}
	// explain a The array is written in , But what does it mean to read invalid data , It didn't seem like this before , terms of settlement , Dynamically creating an array 
	/*for (int i = 0; i < p; i++) {
		cout << a[i];
	}*/
	return num + 1 - dfs(p - 1, true);// The highest corresponding position is p-1 position , by True Indicates that it is not in the limit bit 
	// stay 0 To num There is num+1 Number 
}

  The following is whether to take 3 The number of all the codes ：

#include<iostream>
using namespace std;
#define int long long
#define maxn 15
int num;
int* a = new int[maxn];
int f[15];
//int a[maxn];
int b[maxn];//b Save the first p What you save for is that number 
int ten[maxn];
int L, R;
int t;
int dfs(int p, bool limit) {//p Said in the first p position ,limite Indicates whether it is in the limit bit at this time 
	// Beg without 3 The number of 
	if (p < 0)return 1;// It shows that the number of bits is completely recursive 
	if (!limit && f[p] != -1)return f[p];// Memory search , Directly return the calculated value , Reduce computing time 
	int up = limit ? a[p] : 9;
	int ans = 0;
	for (int i = 0; i <= up; i++) {
		if (i == 3)continue;
		ans += dfs(p - 1, limit && i == up);
	}
	if (!limit)f[p] = ans;// Memory search 
	return ans;
}

int handle(int num) {
	int p = 0;
	int x = num;
	while (x) {// hold num Put each bit in the array 
		a[p++] = x % 10;
		x /= 10;
	}
	// explain a The array is written in , But what does it mean to read invalid data , It didn't seem like this before , terms of settlement , Dynamically creating an array 
	/*for (int i = 0; i < p; i++) {
		cout << a[i];
	}*/
	return num + 1 - dfs(p - 1, true);// The highest corresponding position is p-1 position , by True Indicates that it is not in the limit bit 
	// stay 0 To num There is num+1 Number 
}

void init() {
	ten[0] = 1;
	for (int i = 1; i < 15; i++) {
		ten[i] = ten[i - 1] * 10;
	}
	memset(f, -1, sizeof(f));
}
int32_t  main() {
	cin >> t;
	while (t--) {
		cin >> L >> R;
		//handle(23);
		init();// Remember to initialize ,TM Yes, I've been stuck here for half a month 
		cout << handle(200) - handle(100) << endl;
		delete[]a;
	}
	
	return 0;
}

Hangzhou people call those stupid and sticky people 62（ The sound ：laoer）.
Hangzhou Traffic Management Bureau often expands some taxi license plates , A good news is coming out recently , License plate later , No more unlucky numbers , thus , It can eliminate the psychological barriers of individual taxi drivers and passengers , Serve the public more safely .
The unlucky numbers for all contain 4 or 62 Number . for example ：
62315 73418 88914
All belong to unlucky numbers . however ,61152 Although it contains 6 and 2, But it's not 62 Serial number , So it's not one of the unlucky numbers .
Your task is , For one license plate interval number given at a time , Infer how many new taxis will actually be licensed by the traffic control bureau this time .

Input

All the input are integer pairs n、m（0<n≤m<1000000）, If it's all 0 An integer pair of , Then the input ends .

Output

For each pair of integers , Output a number of statistics that do not contain unlucky figures , This value takes up one line .

Sample Input

1 100
0 0

Sample Output

80

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define LL long long
using namespace std;
int digit[10];
LL dp[10][2];
LL dfs(int len, int if6, int limit)
{
	if (len == 0) return 1; // Count to 0 Bit return 1, because 0 eligible 
	if (!limit && dp[len][if6]) return dp[len][if6];
	// If not the upper limit , You don't have to count again , Go straight back to , The embodiment of memory search 
	LL ans = 0, up;
	if (limit)  up = digit[len];
	else up = 9;
	for (int i = 0; i <= up; i++)
	{
		if (if6 && i == 2) continue;
		if (i == 4) continue;
		ans += dfs(len - 1, i == 6, limit && i == digit[len]);
		//  limit&&i==up It's fine too 
	}
	if (!limit) dp[len][if6] = ans;// Memory search 
	return ans;
}
LL cal(LL x)
{
	int len = 0;
	while (x)
	{
		digit[++len] = x % 10;
		x /= 10;
	}
	return dfs(len, 0, 1);
}
int main()
{
	int n, m;
	while (~scanf("%d%d", &n, &m))
	{
		if (!n && !m)
			break;
		// printf("%lld  %lld\n",cal(m),cal(n));
		printf("%lld\n", cal(m) - cal(n - 1));
	}

	return 0;
}

The following is the same without 49 Number of numbers

subject ： Find interval [1,n] The range includes a band 49 Number of numbers .

A number is a number with 49 Number of numbers , If and only if there are two consecutive digits in his decimal mark value , The high position is 4, The lower order is 9, such as 49,149,1234987 etc. ; and 4,12345,94,9999444 Are not

Input format ： Enter an integer n（1<=n<=2^63）

Output format ： Output an integer to represent the interval [1,n] How many bands exist in the range 49 Number of numbers

sample output ：

Input ：500 

Output ：15

#include<iostream>
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[22], f[22][10];// This one at the back 10 Used to determine which of the previous numbers is 
int n;
int t;
int dfs(int p, int pre, bool limit) {//p It means the first one p digit ,pre Express p+1 digit 
	if (p < 0) {
		return 1;
	}
	if (!limit && f[p][pre] != -1) {
		return f[p][pre];
	}

	int up = limit ? a[p] : 9;
	int ans = 0;
	for (int i = 0; i <= up; i++) {
		if (pre == 4 && i == 9) {
			continue;
		}
		ans += dfs(p - 1, i, limit && i == up);
	}
	if (!limit)f[p][pre] = ans;
	return ans;
}
int handle(int num) {
	int p = 0;
	int x = num;
	while (x) {
		a[p++] = x % 10;
		x /= 10;
	}
	return num + 1 - dfs(p - 1, 0, true);
}

void init() {
	memset(f, -1, sizeof(f));

}
int32_t main() {
	cin >> t;
	while (t--) {
		cin >> n;
		init();
		cout << handle(n) << endl;
	}

	return 0;
}