题解：P12884 [蓝桥杯 2025 国 C] 整齐的数

思路简述

光看题目描述第一反应肯定是打暴力，但观察到

1 \leq n \leq 10^{18}

这惊人的数据范围，这道题是数位 DP 没错了。这边简述一下记忆化搜索的思路。

首先最经典的需要两个变量记录前导零与当前位数上限，再加上三个变量分别记录当前是第几位、当前相邻数位上数字的差的绝对值之和为多少以及上一个数是多少。那接下来就很简单了，套个模板再稍微改一下就 OK 了。代码如下。

C++

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k,num[44],n,m;
int dp[13][22][222][2][2];
int dfs(int last,int pos,int tot,int s,int q){//分别代表上一个数、当前在第几位、当前相邻数位上数字的差的绝对值之和、当前数位的上限、是否有前导零。
	if(pos==0) return tot<=m;
	if(dp[last][pos][tot][s][q]!=0) return dp[last][pos][tot][s][q];
	int up=s?num[pos]:9,ans=0;
	for(int i=0;i<=up;i++){
		if(q){
			if(i==0) ans+=dfs(i,pos-1,0,s&&(i==up),1);
			else ans+=dfs(i,pos-1,0,s&&(i==up),0);
		}
		else ans+=dfs(i,pos-1,tot+abs(i-last),s&&(i==up),0);
	}
	return dp[last][pos][tot][s][q]=ans;
}
int solve(){
	int len=0;
	while(n){num[++len]=n%10;n/=10;}
	return dfs(0,len,0,1,1);
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	cout<<solve();
	return 0;
}

然后，你就会得到一堆大大的 TLE。

想解决也很简单，如果当前相邻数位上数字的差的绝对值之和已经大于

m

了直接结束循环就行了。

最终代码

C++

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k,num[44],n,m;
int dp[13][22][222][2][2];
int dfs(int last,int pos,int tot,int s,int q){
    if(tot>m) return 0;
	if(pos==0) return tot<=m;
	if(dp[last][pos][tot][s][q]!=0) return dp[last][pos][tot][s][q];
	int up=s?num[pos]:9,ans=0;
	for(int i=0;i<=up;i++){
		if(q){
			if(i==0) ans+=dfs(i,pos-1,0,s&&(i==up),1);
			else ans+=dfs(i,pos-1,0,s&&(i==up),0);
		}
		else ans+=dfs(i,pos-1,tot+abs(i-last),s&&(i==up),0);
	}
	return dp[last][pos][tot][s][q]=ans;
}
int solve(){
	int len=0;
	while(n){num[++len]=n%10;n/=10;}
	return dfs(0,len,0,1,1);
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	cout<<solve();
	return 0;
}

题解：P12884 [蓝桥杯 2025 国 C] 整齐的数

文章操作

题解：P12884 [蓝桥杯 2025 国 C] 整齐的数

思路简述

C++

最终代码

C++

The end.

相关推荐

评论

题解：P12884 [蓝桥杯 2025 国 C] 整齐的数