题目大意
Tweetuzki 有一个长度为 \(n\) 的序列 \(a_1, a_2, \cdots, a_n\)。
他希望找出一个最大的 \(k\)，满足在原序列中存在一些数 \(b_1, b_2, \cdots, b_k\)（可打散在原序列中的顺序），满足对于任意的 \(i(1 \le i < k)\)，\(b_i \div 3 = b_{i+1}\)（这时 \(b_i\) 必须能够被 \(3\) 整除）或 \(b_i \times 2 = b_{i+1}\)。并输出这个序列。
解题思路
有个很明显的性质：每个数只会出现一次。（大概是因为 \(2\) 和 \(3\) 互质）
可以感性理解一下：每次除以 \(3\) 或乘以 \(2\) 之后，得到的因子 \(2\) 永远不可能再失去，失去的 \(3\) 也不可能再回来。
所以可以考虑建边，对于每个 \(x\) 向 \(x \div 3(x\%3=0)\) 和 \(2x\) 连边有向边，前提是这两个目标数存在。
这样很明显就构成了一个 DAG。要求的就是最长链，考虑拓扑排序和 DP（很基础的）。
还有一点就是要记录每个点转移来的点是谁，最后 dfs 输出路径。
具体细节看代码吧。
#include<bits/stdc++.h>
#define Code using
#define from namespace
#define yolanda std
Code from yolanda;
#define int long long
inline int read(){
int sum=0,f=1;char a=getchar();
while(a<'0' || a>'9'){if(a=='-') f=-1;a=getchar();}
while(a>='0' && a<='9') sum=sum*10+a-'0',a=getchar();
return sum*f;
}
unordered_map<int,int> pre,d,f;//直接用map就不用离散化了
//f[x]就是到当前点的最长长度
int n,ma,ans;
int a[100005];
void topo(){//拓扑排序
queue<int> q;
for(int i=1;i<=n;++i)
if(!d[a[i]]) q.push(a[i]);
while(q.size()){
int x=q.front();q.pop();
if(f[x]>ma) ma=f[x],ans=x;//ma是最大值，ans是终止点
if(f[x*2]){
--d[x*2];
if(f[x]+1>f[x*2]) f[x*2]=f[x]+1,pre[x*2]=x;
if(!d[x*2]) q.push(x*2);
}
if(x%3==0 && f[x/3]){
--d[x/3];
if(f[x]+1>f[x/3]) f[x/3]=f[x]+1,pre[x/3]=x;
if(!d[x/3]) q.push(x/3);
}
}
}
void print(int x){//输出
if(!x) return;
print(pre[x]);
printf("%lld ",x);
}
signed main(){
cin>>n;
for(int i=1;i<=n;++i)
a[i]=read(),f[a[i]]=1;
sort(a+1,a+n+1);
n=unique(a+1,a+n+1)-a-1;
for(int i=1;i<=n;++i){//建边
if(f[a[i]*2]) ++d[a[i]*2];
if(a[i]%3==0 && f[a[i]/3]) ++d[a[i]/3];
}
topo();
printf("%lld\n",ma);
print(ans);
return 0;
}