题解：P13929 [蓝桥杯 2022 省 Java B] 山

· · 题解

搜索题。

数据范围很小，所以直接爆搜。我们首先生成一个单调不减序列作为山的前半部分，通过反转这个序列得到山的后半部分，组合成完整的山。

如果回文数长度为偶数，直接将前半部分和后半部分拼起来即可。

否则，我们省掉后半部分的第一个字符，再将两半拼起来即可。

代码如下。注意检查生成的山的合法性。

#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
ull ans;
const ull L=2022,R=2022222022;
int n;
int a[15];
void dfs(int pos,int last,int len,bool odd){
    if(pos==len){
        string s;
        for(int i=0;i<len;i++)s.push_back('0'+a[i]);
        int j=len-1-(odd?1:0);
        for(;j>=0;j--)s.push_back('0'+a[j]);
        if(s[0]=='0')return;
        ull x=0;
        for(char c:s)x=x*10+(c-'0');
        if(x>=L&&x<=R)ans++;
        return;
    }
    for(int d=last;d<=9;d++){
        a[pos]=d;
        dfs(pos+1,d,len,odd);
    }
}
int main(){
    for(int len=2;len<=5;len++){
        dfs(0,0,len,false);
        dfs(0,0,len,true);
    }
    cout<<ans;
}

当然，这是一道结果填空题，所以本题的正确答案是 3138，也就是上面的代码跑出来的结果。