H.Happy Number (进制转换/第n个特殊数)(2021牛客暑期多校训练营9 )

传送门

题意： 寻找第n个只包含 ‘2’ ‘3’ 和 ‘6’的数字。

思路：有点类似与二进制，只不过这里是把 n 转换为三进制数 x ，再通过 x 转换为对应的数字。特别需要注意的是 x 中为 0 的位置 其实代表需要向前借一位，再将余下的数对应为相应的数字。

 代码实现：

#include<bits/stdc++.h>
#define endl '\n'
#define null NULL
#define ll long long
#define int long long
#define pii pair<int, int>
#define lowbit(x) (x &(-x))
#define ls(x) x<<1
#define rs(x) (x<<1+1)
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {
   {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
using namespace std;
const int  inf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-6;
const ll   mod = 1e9+7;
const int  N = 2e5 + 5;

inline void read(int &x){
    char t=getchar();
    while(!isdigit(t)) t=getchar();
    for(x=t^48,t=getchar();isdigit(t);t=getchar()) x=x*10+(t^48);
}

int T = 1, n;

int work(int n)  //十进制转三进制
{
    int flag = 1, y = 0, res;
    while(1){
        res = n%3;
        n /= 3;
        y += res*flag;
        flag *= 10;
        if(n==0)break;
    }
    return y;
}


signed main()
{
    IOS;

//    cin >> T;

    while(T --){
        cin >> n;
        int x = work(n);
//        if(n%3==0) cout << x << " " << n << endl;
//        else{
//            cout << "x: " << x << " ";
            string s;
            int tmp = x, cnt = 0;
            while(tmp){ //统计x共有多少位
                tmp /= 10;
                cnt ++;
            }
            while(x){
                int y = x%10;
                x /= 10;
                cnt --;
                if(tmp==-1){  //如果之前有向当前位置借数
                    if(y==0) y = 2;
                    else y --, tmp = 0;
                }
                if(y==0&&cnt){ //如果当前位置为0且不是最高位，便还可以向前借数
                    y = 3;
                    tmp = -1;
                }
                if(y==1) s += '2';
                if(y==2) s += '3';
                if(y==3) s += '6';
            }
            reverse(s.begin(), s.end());
            cout << s << endl;
//        }
    }

    return 0;
}