H、Happy Number(2024牛客国庆集训派对day7)

题目链接：

H-Happy Number_2024牛客国庆集训派对day7 (nowcoder.com)

题目描述：

 翻译为中文：

数据范围：

输入样例：

680

输出样例： 

326623

分析:

 本来以为是dfs，但是看到数据范围1e9, 联想到是找规律的题。

先去写个代码，去打表找一下规律。打表的代码是：

#include<bits/stdc++.h>
#define int long long
 
using namespace std;

int cnt = 0; // 个数 
set<int>se;

void dfs(int len, int sum) {
	//cout << "len = " << len << " sum = " << sum << endl;
	if(sum > 1000000000) {
		return ;
	} 
	if(len > 6) {
		return ;
	} 
	se.insert(sum);
	dfs(len + 1, sum * 10 + 2);
	dfs(len + 1, sum * 10 + 3);
	dfs(len + 1, sum * 10 + 6);
}

int a[3] = {6, 2, 3};
signed main() {
	dfs(1, 0);
	int t = 0;
	se.erase(0);
	for(int i : se) {
		cout << ++ t << " " << i << endl;
	}
	return 0;
}

运行的结果如下：

 自己又去推了一下大概的公式：

 联想到了进制之间的问题，以为是3进制问题，然后拿样例%3 除3 但是得到结果是不对的，就中间错了一位，然后手动推了一下，发现错的那一位是%3 == 0 出的问题，然后又进行了十几分钟的推公式+联想(蒙) ，最后发现当是3的倍数时候，n要进行-1的操作，后面想想也是对的。咱们在二进制的时候是 0 1 10 11, 但是我想先出现的是11，那就是当%2==0的时候后退以为。同理映射到3进制上面: 0 1 2 10 11 12 20 ... 但是我想让出现的是0(6) 1(2) 2(3) 11(22) 12(23) 10(26) , 这个时候怎么办呢？当n%3==0的时候，让n除3之后在减去1，那么下次再进行%3的时候就会后退(前进)。

代码：

#include<bits/stdc++.h>
#define int long long
 
using namespace std;

int a[3] = {6, 2, 3};

signed main() {
	int n;
	cin >> n;
	string t = ""; 
	while(n > 0) {
		t = (char)(a[n % 3] + '0') + t;
		if(n % 3 == 0)
		n = n / 3 - 1;
		else n = n / 3;
	}
	cout << t << endl;
	return 0;
}

代码二：

#include<bits/stdc++.h>
#define int long long
 
using namespace std;

int a[3] = {6, 2, 3};

signed main() {
	int n;
	cin >> n;
	string t = ""; 
	while(n > 0) {
		t = (char)(a[n % 3] + '0') + t;
		n --;
		n /= 3;
	}
	cout << t << endl;
	return 0;
}

运行结果：

别人的代码：

#include<bits/stdc++.h>
using namespace std;
long long n;
string s;
char a[3]={'2','3','6'};
int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0);
	cin>>n;
	while(n)
	{
		n--;
		s+=a[n%3];
		n/=3;
	}
	for(int i=s.size()-1;i>=0;i--) 
	{
		cout<<s[i];
	}
	return 0;
}