自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 23:02:56，当前版本为作者最后更新于2024-12-11 09:36:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

数位 dp 经典题，今天能在洛谷看到十分激动。

记忆化搜索实现的数位 dp 真的太好写也太好理解了吧。

代码中 $l1,l2$ 分别为上一位和上上位是否为 $6$。

可以用二分找到对应的数。

不知道多久以前写的代码，十分易懂：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[20][2][2];
int a[20];
int dfs(int p,bool l2,bool l1,bool lim){
	if(p==-1)return 1;
	if(!lim&&dp[p][l2][l1]!=-1)return dp[p][l2][l1];
	int up=lim?a[p]:9;
	int s=0;
	for(int i=0;i<=up;i++){
		if(l2&&l1&&i==6)continue;
		s+=dfs(p-1,l1,i==6,lim && i==a[p]);
	}
	if(!lim)return dp[p][l2][l1]=s;
	return s;
}
int solve(int x){//返回 1-x 之间有几个非恶魔数 
	int p=0;
	while(x){
		a[p++]=x%10;
		x/=10;
	}
	return dfs(p-1,0,0,1);
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	for(int i=0;i<20;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)dp[i][j][k]=-1;
	int t;cin>>t;
	while(t--){
		int n;cin>>n; 
		int l=665,r=9999999999ll;
		while(l<r){
			int mid=(l+r)>>1;
			if(mid+1-solve(mid)<n){
				l=mid+1;
			}else{
				r=mid;
			}
		}
		cout<<l<<endl;
	} 
	return 0;
}