欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

codeforces 977D(DFS)

程序员文章站 2022-03-23 11:29:18
题意描述给你n个数字,要求你改变数字顺序,使后一个数字是前一个数字的2倍或者三分之一思路由于题目保证一定有解,所以我们使用dfs来解决,如果两个数字间满足题目条件,就连一条单向边,最后dfs找到一个能够遍历全部的路径即可AC代码#include#define x first#define y second#define IOS ios::sync_with_stdio(false);cin.tie(0);using namespace std;t...

题意描述

给你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