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

· · 题解

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

思路简述

光看题目描述第一反应肯定是打暴力，但观察到 1 \leq n \leq 10^{18} 这惊人的数据范围，这道题是数位 DP 没错了。这边简述一下记忆化搜索的思路。

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

C++

#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++

#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;
}

The end.