题解：P12835 [蓝桥杯 2025 国 B] 蓝桥星数字

注意到

N

的范围是很大的，直接模拟显然会超时，又注意到是统计某些特定的数，很容易想到数位 dp。

通过题意很容易就可以找出规律，即除第一个可以填

9

种数字之外，剩余位数都只能填

5

种，可以先把所有位数的情况打个表，再 dfs 判断。

代码：

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dis[105],ck[105];
ll n,ans;
void dfs(int pos,int last){
	if(pos==0){
		printf("%lld",ans);
		exit(0);//直接结束程序  
		return ;
	}
	int to,i;
	if(last==-1)to=1,i=1;//判断是否为最高位数 
	else{
		to=2;
		if(last%2==0)i=1;
		else i=0;
	}
	for(;i<10;i+=to){
		if(n>ck[pos]){ 
			n-=ck[pos];
			continue;
		}
		ans=ans*10+i;
		dfs(pos-1,i);
	}
}
signed main(){
	dis[1]=9,ck[1]=1;
	for(int i=2;i<=100;i++)dis[i]=dis[i-1]*5,ck[i]=ck[i-1]*5;//打表 
	scanf("%lld",&n);
	int pos=0;
	for(int i=2;i<=100;i++){
		if(n>dis[i])n-=dis[i];
		else{
			pos=i;//找到第N位数的位数 
			break;
		}
	}
	dfs(pos,-1);
	return 0;
}

题解：P12835 [蓝桥杯 2025 国 B] 蓝桥星数字

文章操作

相关推荐

评论

题解：P12835 [蓝桥杯 2025 国 B] 蓝桥星数字