CF1811E题解

SunLegend · 2023-04-09 08:20:35 · 题解

题目大意

给定 t 次询问，每次询问给定一个正整数 n，求第 n 个各个数位上都不含数字 4 的正整数。

解法分析

初次读题后很容易把这道题想成数位 dp 和二分了，但这样会大大增加代码实现难度。

其实有一种更简单的解法，显然输出结果的每个数位上都没有 4，那么每一位就一共只有 9 种数字，由此可以联想到九进制，实际我们要做的就是把十进制转为九进制，再利用一个数组将九进制数的每一数位进行映射即可。

具体实现见代码。

#include<bits/stdc++.h>
using namespace std;
int t,x,a[22];
int m[12]={0,1,2,3,5,6,7,8,9};//用来映射的数组 
long long n; //记得long long！！！ 
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        while(n)
        {
            a[++x]=m[n%9]; 
            n/=9;
        }
        for(int i=x;i>=1;i--) cout<<a[i];
        cout<<endl;
        x=0;
    }
    return 0;
}