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;
}原文地址：https://blog.csdn.net/m0_74304371/article/details/142742666
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！