Znzryb's Blog
0%

ABC-387-C - Snake Numbers 

Posted on Edited on

思路讲解

数位dp记忆化搜索做法

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
// dp装的在top位为n的情况下，第i位符合要求的数字数量
ll L,R,digit[25],dp[15][25];
// 为什么要开两维？因为top位不同的情况下，结果没有加和性
//                                isTop是指该位是不是最高位
ll dfs(ll len,ll isMax,ll top,bool isTop){
	if(len==0)
		return 1;
	if(dp[top][len]!=-1 && !isMax)
		return dp[top][len];
	ll maxx,res=0;
	maxx= isMax ? digit[len]:9;
	for(int i=0;i<=maxx && i<top;++i){
		if(isTop){ // 是首数，再考虑0和非0的情况
			if(i==0){
				//                                  top=10 就是指不限制
				res+=dfs(len-1,isMax && i==digit[len],10,true);
				// 不限制的原因是前导为0，没有资格作首数
			}else{
				// 是top数，可以改top
				res+=dfs(len-1, isMax && i==digit[len], i, false);
			}
		}else{
			// 不是top数，没有资格改top
			res+=dfs(len-1, isMax && i==digit[len], top, false);
		}
	}
	if(!isMax)
		dp[top][len]=res;
	return res;
}

以下为思维做法，了解数位dp后觉得有点玄学

我的思路就是先算出1～两个数之间的snake number数量，再将两者相减。

我们以1～90011来解释我们的运算过程

90011可以拆成首位为0～9的情况，其中2～8的计算相对简单，首位已经确定，后面每位有首位种选择，snake number 数量就是 首位^后面的位子数

0的情况就是

1
2
3
4
5
6
7
8
// 假设首位为0情况
if(i==0){
	for(int j=0;j<s.size()-1;++j){
		for(int k=1;k<=9;++k){
			res+=pown[k][j];
		}
	}
}

9的情况就是和2～8一样正常算，然后把不可行的情况数剪掉

1
2
3
4
5
if(i==s[0]-'0'){
	for(int j=0;j<s.size()-1;++j){
		res-=(s[0]-'0'-1-(s[s.size()-j-1]-'0'))*pown[i][j];
	}
}

具体而言如下图

image

AC代码

AC https://atcoder.jp/contests/abc387/submissions/61678607

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
#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装的在top位为n的情况下，第i位符合要求的数字数量
ll L,R,digit[25],dp[15][25];
// 为什么要开两维？因为top位不同的情况下，结果没有加和性
//                                isTop是指该位是不是最高位
ll dfs(ll len,ll isMax,ll top,bool isTop){
	if(len==0)
		return 1;
	if(dp[top][len]!=-1 && !isMax)
		return dp[top][len];
	ll maxx,res=0;
	maxx= isMax ? digit[len]:9;
	for(int i=0;i<=maxx && i<top;++i){
		if(isTop){
			if(i==0){
				//                                  top=10 就是指不限制
				res+=dfs(len-1,isMax && i==digit[len],10,true);
				// 不限制的原因是前导为0，没有资格作首数
			}else{
				// 是top数，可以改top
				res+=dfs(len-1, isMax && i==digit[len], i, false);
			}
		}else{
			// 不是top数，没有资格改top
			res+=dfs(len-1, isMax && i==digit[len], top, false);
		}
	}
	if(!isMax)
		dp[top][len]=res;
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>L>>R;
	L-=1;
	ll idx=0;
	while(L){
		digit[++idx]=L%10;
		L/=10;
	}
	memset(dp, -1, sizeof(dp));
	// 刚传进去该位肯定是最高位
	ll lRes=dfs(idx,true,10,true);
	idx=0;
	while(R){
		digit[++idx]=R%10;
		R/=10;
	}
//	memset(dp, -1, sizeof(dp));
	ll rRes=dfs(idx,true,10,true);
	cout<<rRes-lRes<<'\n';
	return 0;
}

AC https://atcoder.jp/contests/abc387/submissions/61423141

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
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;
typedef unsigned long long ll;
string L,R;
string Ls,Rs;
ll pown[11][21];

void init(){
	Ls.assign(L);
	Rs.assign(R);
	bool isChange=false;
	// 通过这种方法可以得到最靠近原数的snake number
	for(int i=1;i<Rs.size();++i){
		if(Rs[i]<Rs[0] && !isChange){
			continue;
		}
		isChange=true;
		Rs[i]=static_cast<char> (Rs[0]-1);
	}
	isChange=false;
	for(int i=1;i<Ls.size();++i){
		if(Ls[i]<Ls[0] && !isChange){
			continue;
		}
		isChange=true;
		Ls[i]=static_cast<char> (Ls[0]-1);
	}
	// 通过递推得到pow数组，方便后续计算
	for(int i=1;i<=10;++i){
		pown[i][0]=1;
		for(int j=1;j<=19;++j){
			pown[i][j]=i*pown[i][j-1];
		}
	}
}
inline ll getAns(string &s){
	ll res=0;
	for(int i=0;i<=s[0]-'0';++i){
		// 假设首位为0情况
		if(i==0){
			for(int j=0;j<s.size()-1;++j){
				for(int k=1;k<=9;++k){
					res+=pown[k][j];
				}
			}
		}else{
			// 首数为i，后面有i^(size-1)种选择
			res+=pown[i][s.size()-1];
		}
		if(i==s[0]-'0'){
			for(int j=0;j<s.size()-1;++j){
				res-=(s[0]-'0'-1-(s[s.size()-j-1]-'0'))*pown[i][j];
			}
		}
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>L>>R;
	init();
	// 先算出1-R，再算出1-L,两者相减
	ll Rto1=0,Lto1=0;
	Rto1=getAns(Rs);
	Lto1=getAns(Ls);
	if(L==Ls){
		cout<<Rto1-Lto1+1<<endl;
	}else{
		cout<<Rto1-Lto1<<endl;
	}
	return 0;
}
/*
AC https://atcoder.jp/contests/abc387/submissions/61423141
29 55

90011 98888

*/

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