Codeforces Round 863 (Div. 3) E题

题目地址

题意：定义数组a包含所有不含数字4的正整数，给出一个n，要求求出数组a中第n个数

Solution

数位dp+二分，求出[1,mid]中不含数字4的正整数个数，不过因为有可能mid包含4，但是由于贡献是一样的，可以直接把4都变成3，最后处理一下即可

int dp[20];
int a[20];
void init()
{
	dp[0]=1;
	for(int i=1;i<20;i++)
	{
		dp[i]=dp[i-1]*9;
	}
}

int dfs(int x)
{
	int len=0;
	int temp=x;
	while(temp>0)
	{
		a[++len]=temp%10;
		temp/=10;
	}
	int res=0;
	for(int i=len;i>=1;i--)
	{
		if(a[i]<4)res+=a[i]*dp[i-1];
		else if(a[i]>=4)res+=(a[i]-1)*dp[i-1];
		
	}
	return res;
}
int ans[30];

void solve()
{
	int n;cin>>n;
	int l=1,r=1e18;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(dfs(mid)<n)l=mid+1;
		else r=mid;
	}
	int t=0;
	while(l>0)
	{
		int x=l%10;
		if(x!=4)ans[++t]=x;
		else ans[++t]=3;
		l/=10;
	}
	for(int i=t;i>=1;i--)cout<<ans[i];
	cout<<"\n";
	
}