CF1811E Living Sequence

这道题洛谷题解的思路比我的更好，可以参考一下题解，但是没人提到我这种做法

题意

给定一个正整数 \(k\) \((1\le k\le10^{12})\)，请你输出第 \(k\) 个数字里没有 4 的正整数。

思路

设 \(f_i\) 表示前 \(10^i\) 个 \(i\) 位数里边不含4的数的个数，列举几个如下：

而估计一下，可以枚举到\(i=15\)

所以，就可以按位进行一个估计，拿\(100\)举例子：

最开始，一直从\(i=15\)枚举到\(i=2\)，才发现第一个\(f_i\)比\(100\)小，于是当前的数加上\(100\)，而前\(100\)个数里边，一共有\(81\)个不包含\(4\)的数

换句话说，\(100\)是第\(81\)个不包含4的数

接着，如果当前数再加\(100\)的话，个数就变成\(162\)了，比\(100\)要多，所以就不能加\(100\)了，转而到了\(i=2\)，加\(10\)

接着进行如上操作，发现进行两次后，当前的数变成了\(119\)，个数变为了\(99\)，此时就应将\(i\)更改为\(i=1\)

随后就能够发现\(120\)就是不包含\(4\)的第\(100\)个不包含\(4\)的正整数

最后需要注意，由于我的规律是从\(0\)开始的，但是题目中要求的是正整数，所以在最开始的\(100\)就应该加一，相当于是把\(0\)给算进去了

还有一个要点，就是计算当前数的时候，如果遇到首位含有\(4\)的数，要跳过

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=20;
int f[Maxn];
int n,now,cnt;
int p(int x)
{
	int re=1;
	while(x--) re*=10;
	return re;
}
void run()
{
	cin>>n;n++;now=0;cnt=0;
	for(int i=15;i>=0;i--)
	{
		int x=0;
		while((x==4?now:now+f[i])<n) 
		{
			cnt+=p(i);
			if(x!=4) now+=f[i];
			x++;
		}
	}
	cout<<cnt<<"\n";
	return;
}
signed main()
{
	f[0]=1,f[1]=9;
	for(int i=2;i<=15;i++) f[i]=f[i-1]*9;
	int t;
	cin>>t;
	while(t--) run(); 
	return 0;
}