G题题解：

知识点：枚举+DFS/记忆化搜索

题目解析：寻找“持久性”最大的数字。利用 DFS 枚举数字 2-9 的出现次数（利用乘积性质），结合记忆化搜索计算变换次数。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
const int N = 500010;
int sum=0,mx=0,m1=0,m2=0;//m1记录最大结果，m2记录第二大的结果，mx记录最大的变换步数（g函数的返回值）
int cnt[10];//表示数字i出现的次数（0-9）
map<int,int>mp;//缓存f函数结果，避免重复计算
int f(int x){//将x的每一位数字相乘的结果,即f(x)函数
	if(x==0) return 0;
	if(mp.find(x)!=mp.end()){
		return mp[x];
	}
	int tmp=1;
	while(x){
		tmp*=x%10;
		x/=10;
	}
	mp[x]=tmp;
	return tmp;
}

int g(int x){//计算x=f(x)所需要的执行次数
	int tmp=0;
	if(x<10) return tmp;
	while(x!=f(x)){
		x=f(x);
		tmp++;
	}
	return tmp;
}

int b(){//根据cnt数组构造最大的数（从9到0拼接）
	int tmp=0;
	for(int i=1;i<=9;i++){//从1开始，保证构造的数是非递减的
		for(int j=1;j<=cnt[i];j++){
			tmp*=10;
			tmp+=i;
		}
	}
	return tmp;
}
//dfs枚举0-9每个数字的出现次数
void dfs(int x){
    // 递归终止条件：已经枚举完0-9所有数字
	if(x==10){
		int num=b();//构造当前次数对应的最大数
		int tmp=g(num);//计算这个数的变换步数
		if(tmp>mx){//找到更大的步数：更新最大步数，重置答案
			m2=m1;//原来的最优答案变成次优
			m1=num;//新的最优答案
			mx=tmp;
		}else if(tmp==mx){
			m2=num;//步数相同,更新次优答案
		}
		return;
	}
    // 枚举当前数字（current_digit）的出现次数i
    // i+sum < 18：保证所有数字总个数不超过18
	for(int i=0;i+sum<18;i++){
		cnt[x]=i;//记录当前数字的出现次数
		sum+=i;//总个数加上i
		dfs(x+1);//递归处理下一个数字
		sum-=i;
	}
}
void solve(){
	dfs(1);//从数字1开始枚举（原代码dfs(1)，跳过数字0的枚举）
	cout<<m1<<" "<<m2<<endl;
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	int T=1;//cin>>T;
	while(T--){
		solve();
	}
	return 0;
}