Happy Number（思维 / dfs求排列/ 模拟）

柔光的暖阳◎ 2022-09-04 13:57 130阅读 0赞

链接：https://ac.nowcoder.com/acm/contest/11260/H  
来源：牛客网

Digits 2, 3 and 6 are happy, while all others are unhappy. An integer is happy if it contains only happy digits in its decimal notation. For example, 2, 3, 263 are happy numbers, while 231 is not.

## 思维 ##

--------------------

#include<bits/stdc++.h>
    //#define endl "\n"
    
    using namespace std;
    const int N = 1e9+10;
    typedef long long ll;
    int b[N];
    signed main()
    { 
        ios::sync_with_stdio(false);
        cin.tie(0),cout.tie(0);
        int n;
        cin>>n;
        int pos=0;
        while(n){ 
            b[pos]=(n-1)%3;
            n=(n-1)/3;
            pos++;
        }
        for(int i=pos-1;i>=0;i--)
        { 
            if(b[i]==0)cout<<2;
            else if(b[i]==1)cout<<3;
            else cout<<6;
           }
        cout<<endl;
        return 0;
    }

--------------------

## dfs求排列 ##

--------------------

#include<bits/stdc++.h>
    
    using namespace std;
    
    int bit[20],sum[20],to[10];
    
    void dfs(int n,int x)
    { 
    	int y=n/bit[x-1];
    	printf("%d",to[y+1]);
    	if(x==1) return;
    	dfs(n-y*bit[x-1],x-1);
    }
    
    int main()
    { 
    	bit[0]=1;
    	for(int i=1;i<=19;++i) 
    	{ 
    		bit[i]=bit[i-1]*3;
    		sum[i]=sum[i-1]+bit[i];
    	}
    	int n,dep=0;
    	scanf("%d",&n);
    	to[1]=2;
    	to[2]=3;
    	to[3]=6;
    	if(n<=3)
    	{ 
    		printf("%d",to[n]);
    		return 0;
    	}
    	for(int i=0;;++i)
    		if(sum[i]>=n) 
    		{ 
    			dep=i;
    			break;
    		}
    	--n;
    	int y=n-sum[dep-1];
    	y=y/bit[dep-1];
    	printf("%d",to[y+1]);
    	dfs(n-sum[dep-1]-y*bit[dep-1],dep-1); 
    	
    }

--------------------

## 模拟 ##

--------------------

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    using namespace std;
    typedef long long LL;
    const int N = 50;
    int num[N];
    LL n, tmp = 1, sum = 0;
    int cnt = 0;
    void change(int op)
    { 
    	if (op == cnt) 
    	{ 
    		num[cnt ++ ] = 2;
    		return ;
    	} 
    	if (num[op] == 2) num[op] = 3;
    	else if (num[op] == 3)	num[op] = 6;
    	else if (num[op] == 6)
    	{ 
    		num[op] = 2;
    		change(op + 1);
    	}
    }
    int main()
    { 
    	scanf("%lld", &n);
    	if (n == 1)
    	{ 
    		puts("2");
    	} 
    	else if (n == 2)
    	{ 
    		puts("3");
    	} 
    	else 
    	{ 
    		do { 
    			tmp *= 3;
    			if (sum + tmp <= n)
    			{ 
    				sum += tmp;
    				num[cnt ++ ] = 6;
    			} else break;
    		} while (true);
    		for (int t = cnt - 1; t >= 0; t -- )
    		{ 
    			LL tmp = (LL)pow(3, t);
    			while (sum + tmp <= n)
    			{ 
    				change(t);
    				sum += tmp;
    			}
    		}
    		for (int i = cnt - 1; i >= 0; i -- ) printf("%d", num[i]);
    		puts("");	
    	}
    	return 0; 
    }