Znzryb's Blog
0%

HDU - 2089- 不要62

Posted on Edited on

思路讲解

我们看看可不可以一题多解，用数位dp解一下这道

主要就是记忆化搜索，具体看黑书还有我的代码注释，还是比较详细的

黑书还是好，让我仿写，但还可以留白一部分，让我自己写，真是对我太友好了

image

AC代码

https://vjudge.net/solution/57465304

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10;
// dp表示第i位符合要求的数字数量,比如dp[1]=9，因为除了4都满足
ll L,R,dp[15][3],digit[15];
// digit是指该数的第i位为几，比如说342，digit[1]=2
//                       上一位是不是6？
ll dfs(ll len,bool isMax,bool is6){
	if(len==0)// 递归结束条件
		return 1;
	// 记忆化结束条件
	if(dp[len][is6]!=-1 && isMax==false)
		return dp[len][is6];
	ll res=0,maxx;
	// 如果不是最大位，那么就直接取9
	maxx= isMax ? digit[len]:9;
	for(int i=0;i<=maxx;++i){
		// 记忆化搜索关键部分来了，数位dp之所以可以这样
		// 是因为 最高位+后面的数=新数
		if(i==4)	// 排除4
			continue;
		if(is6 && i==2)	// 不能组成62
			continue;
		if(i==6){
			res+=dfs(len-1,isMax && i==maxx,true);
		}else{
			// 如果前数进入是最大数，i也是最大数，后面的也要受限制
			// 比如324，百位为3确定了，十位最多为2
			// 但如果324，百位为2确定了，后面的数想写啥写啥
			res+=dfs(len-1,isMax && i==maxx,false);
		}
	}
	if(!isMax)
		dp[len][is6]=res;
	return res;
}

void solve(){
	memset(dp, -1, sizeof(dp));
	string Ls=to_string(L-1);
	for(int i=1;i<=Ls.size();++i){
		digit[i]=Ls[Ls.size()-i]-'0';
	}
	ll lres=dfs(Ls.size(), true,false);
	string Rs=to_string(R);
	for(int i=1;i<=Rs.size();++i){
		digit[i]=Rs[Rs.size()-i]-'0';
	}
	ll rres=dfs(Rs.size(), true,false);
	cout<<rres-lres<<'\n';
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	while (cin>>L>>R) {
		if(L==0 && R==0)
			break;
		solve();
	}
	return 0;
}
// AC https://vjudge.net/solution/57465304

心路历程（WA，TLE，MLE……）