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
推荐阅读
-
Codeforces Round #595 (Div. 3)D1D2 贪心 STL
-
『ACM C++』 Codeforces | 1066B - Heaters
-
迷宫救人——DFS小题
-
数据结构算法(统计封闭岛屿的数目dfs)
-
『ACM C++』 Codeforces | 1003C - Intense Heat
-
Codeforces 939A题,B题(水题)
-
CodeForces 29D Ant on the Tree
-
Codeforces Global Round 9-C. Element Extermination
-
codeforces 712B Memory and Trident
-
CodeForces 962D Merge Equals