codeforces 977D（DFS）

题意描述

给你n个数字，要求你改变数字顺序，使后一个数字是前一个数字的2倍或者三分之一

思路

由于题目保证一定有解，所以我们使用dfs来解决，如果两个数字间满足题目条件，就连一条单向边，最后dfs找到一个能够遍历全部的路径即可

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=1e4+10;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
LL a[N],ans[N];
bool used[N];
vector<int> g[N];
int fg=0,n;
void dfs(int u,int k){
    ans[k]=a[u];
    if(fg) return;
    if(k==n-1){
        for(int i=0;i<n;i++) cout<<ans[i]<<' ';
        cout<<endl;
        fg=1;
        return;
    }
    for(int i=0;i<g[u].size();i++){
        if(used[g[u][i]]) continue;
        used[g[u][i]]=true;
        dfs(g[u][i],k+1);
        used[g[u][i]]=false;
    }
}
void solve(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i]*2==a[j] || a[i]==a[j]*3){
                g[i].push_back(j);
            }
        }
    }
    for(int i=0;i<n;i++){
        memset(used,false,sizeof used);
        used[i]=1;
        dfs(i,0);
        if(fg) break;
    }
}
int main(){
    IOS;
    solve();
    return 0;
}

本文地址：https://blog.csdn.net/weixin_45729946/article/details/107318470