序列重排

语法收获：vector可以用于二元组、三元组和多元组的大小比较，支持字典序，类似于pair

思路

思路1 正解证明

这是一道构造+思维题目，题目本身具有很强的性质，如果能够找到这个性质，就能够很轻松的求解，但是如果没想到，就只能暴搜了。通过证明，我们可以发现符合必要条件的的序列是唯一的，所以我们的必要条件就变成了充要条件，我们就可以利用这个条件轻松求解。

思路2 DFS枚举所有情况

在周赛的时候，我是直接想的DFS，害，刚学DFS没多久，这是第一个自己做出来的DFS😂😂，但是它的正解竟然还不是DFS！

大致思路就是枚举每一位，如果前一个位置的数字确定了，后一位只有两种情况，这样不断地去做选择，当然，还要记录这个数字是否被使用过和是否还存在。这里使用st数组和一个unordered_map进行判断就行了。

因为这道题目解的性质很强，并且是唯一解，所以DFS搜索的多余状态是非常少的，所以真正的时间复杂度也不高，所以就过了。

DFS竟然和正解一样的时间!

代码1

//正解
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 110;

int n;
vector<LL> q[N];

//求解数字x的因子b的个数
int get(LL x, int b)
{
    int res = 0;
    while(x % b == 0)
    {
        res++;
        x /= b;
    }
    return res;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        LL x;
        cin >> x;
        q[i] = {get(x, 2), -get(x, 3), x};
    }

    sort(q, q + n);

    for(int i = 0; i < n; i++)
        cout << q[i][2] << " ";
    cout << endl;

    return 0;
}

代码2

//DFS
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 110;

int n;
LL q[N], res[N];
bool st[N];
unordered_map<LL,LL> s;

//索引为u位置的元素已经确定
void dfs(int u)
{
    if(u == n - 1)
    {
        for(int i = 0; i < n; i++)
            cout << res[i] << " ";
        return;
    }

    LL a = res[u] * 2, b = res[u] / 3;
    if(s.count(a) && !st[s[a]])
    {
        res[u+1] = a;
        st[s[a]] = true;
        dfs(u+1);
        st[s[a]] = false;
    }
    else if(res[u] % 3 == 0 && s.count(b) && !st[s[b]])
    {
        res[u+1] = b;
        st[s[b]] = true;
        dfs(u+1);
        st[s[b]] = false;
    }

}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> q[i];
        s.insert({q[i], i});
    }

    for(int i = 0; i < n; i++)
    {
        res[0] = q[i];
        st[i] = true;//记录q中第i的元素已经被使用了
        dfs(0);
        st[i] = false;//恢复环境
    }

}