序列重排

题意：

给定一个长度为 n 的整数序列 a1,a2,…,an。

请你对序列进行重新排序（也可以保持原序列）

要求新序列满足每个元素（第 1 个除外）都恰好是前一个元素的两倍或前一个元素的三分之一。

题解：

因为要求新序列满足每个元素（第 1 个除外）都恰好是前一个元素的两倍或前一个元素的三分之一。

所以，从1~n的数中，其包含质因子2的个数一定是不降的，其包含质因子3的个数一定是不增的。

根据这个，我们可以求出来每一个数的质因子2和3的个数，以他们作为关键字排序。

排序规则可以以2的个数为第一关键字，以3的个数为第二关键字。

因为题目保证有解，所有排序完之后直接输出即可。

代码：

#include <iostream>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll get(ll x,ll a){
    ll ans=0;
    while(x){
        if(x%a==0) ans++,x/=a;
        else break;
    }
    return ans;
}

vector<ll> q[105];
int main(){
   int n;
   cin>>n;
   for(int i=0;i<n;i++){
       ll x;
       cin>>x;
       q[i]={get(x,2),-get(x,3),x };// vector排序 先排第一个元素那一列 相同看第二个元素
   }
  
   sort(q,q+n);
   for(int i=0;i<n;i++)
   if(i==0) cout<<q[i][2];
   else cout<<" "<<q[i][2];
    return 0;
}

C. Not Assigning

题意：

构建一个素数树 素数树是由一条或两条边组成的每条路径的权重都是素数的树 无法构建 输出-1

 思路：

经过思考可知：

 一个节点的度大于等于三则无法构建

树应该是连成一条线可以构建 如下：
     V1⟷V2⟷V3⋯⟷Vn−1⟷Vn

DFS 对边2 3 2 3... 赋值；

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

 void dfs(int v,int u,int s,map<pair<int,int>, int>&mp, vector<int> p[]){
    for(int i=0;i<p[v].size();i++){
       int x=p[v][i];
       if(x!=u){
         if(s!=2){
            mp[{v,x}]=2;
            dfs(x,v,2,mp,p);
         }else{
            mp[{v,x}]=3;
            dfs(x,v,3,mp,p);
         }

       }
    }
   return ;
}




int main()
{
    int t,mark;
    cin>>t;
    while(t--){
            int n;
       vector<pair<int,int> >c;
         mark=0;
       cin>>n;
       map<pair<int,int>, int>mp;
       vector<int> p[n+5];
       vector<int>sum(n+1);
        for(int i=0;i<n-1;i++){
            int u,v;
            cin>>u>>v;
            sum[u]++;
            sum[v]++;
            p[u].push_back(v);
            p[v].push_back(u);
            if(sum[u]>2||sum[v]>2) mark=1;
            c.emplace_back(u,v);
        }
        if(mark==1){
            cout<<-1<<endl;
            continue ;
        }
        int m1,m2; //从节点1的俩节点开始 dfs
        if(p[1].size()==2){
             m1=p[1][0];
             m2=p[1][1];
        }else{
            m1=p[1][0];
            m2=0;
        }

        mp[{1,m1}]=3; //对节点1俩边2 3 赋值
        mp[{1,m2}]=2;
        dfs(m1,1,3,mp,p);
        dfs(m2,1,2,mp,p);

        for(int i=0;i<c.size();i++){
             p[i+1].clear();
            int u=c[i].first;
            int v=c[i].second;
            int ans=max(mp[{u,v}],mp[{v,u}]);
            cout<<ans<<" ";
        }
        cout<<endl;

    }
    return 0;
}