“蔚来杯“2022牛客暑期多校训练营3 补题题解（A、C、J）

---

觉得有帮助的点个赞！

比赛地址
参考的大佬题解

A Ancestor

感谢队友的思路，大致就是把每个关键点按照输入的顺序放进一个区间，之后对这个区间的（1，2~ n）和（1~n-1,n）分别求这些关键点的最近公共祖先，之后遍历这个区间，去掉每个关键字，直接调用已记录的值求出去掉的关键字左右两个区间的最近公共祖先，再对这两个点求最经过祖先并比较权值，当k的值是2、3时需要特判一下，细节见代码：

#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int>PII;

const int N = 1e5 + 10, M = 2 * N;  //无向图，double边

int n, m;
int h1[N], e1[M], ne1[M], idx1;
int h2[N], e2[M], ne2[M], idx2;
int depth1[N];
int depth2[N];
int fa1[N][17];  //记录祖先节点 
int fa2[N][17];  //记录祖先节点 
int q1[N], q2[N];
map<PII, int>mp1, mp2;  //储存两个节点区间的最近公共祖先 

void add1(int a, int b){
    
	e1[idx1] = b;
	ne1[idx1] = h1[a];
	h1[a] = idx1 ++ ;
}

void add2(int a, int b){
    
	e2[idx2] = b;
	ne2[idx2] = h2[a];
	h2[a] = idx2 ++ ;	
}

void bfs1(){
      //给所有树上节点确定深度和父节点、祖先节点 
	memset(depth1, 0x3f, sizeof depth1);
	depth1[0] = 0, depth1[1] = 1;
	int hh = 0, tt = 0;
	q1[0] = 1;
	
	while(hh <= tt){
    
		int t = q1[hh ++ ];
		for(int i = h1[t]; ~i; i = ne1[i]){
    
			int j = e1[i];
			if(depth1[j] > depth1[t] + 1){
    
				depth1[j] = depth1[t] + 1;
				q1[ ++ tt] = j;
				fa1[j][0] = t;
				for(int k = 1; k <= 16; k ++ ){
    
					fa1[j][k] = fa1[fa1[j][k - 1]][k - 1];  //确定祖先节点 
				}
			}
		}
	}
}

void bfs2(){
      //给所有树上节点确定深度和父节点、祖先节点 
	memset(depth2, 0x3f, sizeof depth2);
	depth2[0] = 0, depth2[1] = 1;
	int hh = 0, tt = 0;
	q2[0] = 1;
	
	while(hh <= tt){
    
		int t = q2[hh ++ ];
		for(int i = h2[t]; ~i; i = ne2[i]){
    
			int j = e2[i];
			if(depth2[j] > depth2[t] + 1){
    
				depth2[j] = depth2[t] + 1;
				q2[ ++ tt] = j;
				fa2[j][0] = t;
				for(int k = 1; k <= 16; k ++ ){
    
					fa2[j][k] = fa2[fa2[j][k - 1]][k - 1];  //确定祖先节点 
				}
			}
		}
	}
}

int lca1(int a, int b){
      //返回a、b点的最近公共祖先 
	if(depth1[a] < depth1[b]) swap(a, b);  //将a置于更深层次的点 
	for(int k = 16; k >= 0; k -- ){
    
		if(depth1[fa1[a][k]] >= depth1[b]){
    
			a = fa1[a][k];
		}
	}
	if(a == b) return a;
	for(int k = 16; k >= 0; k -- ){
    
		if(fa1[a][k] != fa1[b][k]){
    
			a = fa1[a][k];
			b = fa1[b][k];
		}
	}
	return fa1[a][0];  //返回公共祖先节点 
}

int lca2(int a, int b){
      //返回a、b点的最近公共祖先 
	if(depth2[a] < depth2[b]) swap(a, b);  //将a置于更深层次的点 
	for(int k = 16; k >= 0; k -- ){
    
		if(depth2[fa2[a][k]] >= depth2[b]){
    
			a = fa2[a][k];
		}
	}
	if(a == b) return a;
	for(int k = 16; k >= 0; k -- ){
    
		if(fa2[a][k] != fa2[b][k]){
    
			a = fa2[a][k];
			b = fa2[b][k];
		}
	}
	return fa2[a][0];  //返回公共祖先节点 
}

int kk[N];
int v1[N], v2[N];  //权重 
int ans;  //记录答案 
int k;

int main()
{
    
	scanf("%d%d", &n, &k);
	
	memset(h1, -1, sizeof h1);
	memset(h2, -1, sizeof h2);
	
	for(int i = 1; i <= k; i ++ ){
      //读入k个关键字 
		scanf("%d", &kk[i]);
	} 
	
	//读入A树信息
	for(int i = 1; i <= n; i ++ ){
    
		scanf("%d", &v1[i]);
		
	}
	
	for(int i = 2; i <= n; i ++ ){
    
		int a;
		scanf("%d", &a);
		add1(a, i);  //a是i的父节点 
	}

	//读入B树的信息 
	for(int i = 1; i <= n; i ++ ){
    
		scanf("%d", &v2[i]);
	}
	
	for(int i = 2; i <= n; i ++ ){
    
		int a;
		scanf("%d", &a);
		add2(a, i);  //a是i的父节点 
	}

	bfs1();
	bfs2(); 

	
	for(int i = 1; i <= k; i ++ ){
    
		mp1[{
    i, i}] = kk[i];
		mp2[{
    i, i}] = kk[i];
	}

	//查找从0~k-1的最近公共祖先 
	int num1 = kk[1];
	int num2 = kk[1];
	for(int i = 2; i <= k; i ++ ){
    
		mp1[{
    1, i}] = lca1(num1, kk[i]);
		num1 = mp1[{
    1, i}];
		
		mp2[{
    1, i}] = lca2(num2, kk[i]);
		num2 = mp2[{
    1, i}];		
	}	
	
	int iu = kk[k];
	int iu2 = kk[k];
	for(int i = k - 1; i >= 1; i -- ){
    
		mp1[{
    i, k}] = lca1(iu, kk[i]);
		iu = mp1[{
    i, k}];
		
		mp2[{
    i, k}] = lca2(iu2, kk[i]);
		iu2 = mp2[{
    i, k}];		
	}
	
	
	//---------------------------------------
	if(k < 4){
    
		if(v1[mp1[{
    2, 3}]] > v2[mp2[{
    2, 3}]]){
    
		// cout<<"*1*"<<endl;
			ans ++ ;  //去掉第一个点 
		}	
	// cout<<v1[mp1[{1, 1}]]<<' '<<v2[mp2[{1, 1}]]<<endl;
		if(v1[mp1[{
    1, 2}]] > v2[mp2[{
    1, 2}]]){
    
			ans ++ ;  //去掉最后一个点 
		}	
		if(k == 3 && v1[lca1(kk[1], kk[3])] > v2[lca2(kk[1], kk[3])]){
      //去掉中间那个点 
		// cout<<"*6*"<<endl;
			ans ++ ;
		}		
	}
	else if(k >= 4){
    
		if(v1[mp1[{
    2, k}]] > v2[mp2[{
    2, k}]]){
    
		// cout<<"*1*"<<endl;
			ans ++ ;  //去掉第一个点 
		} 
		
		if(v1[mp1[{
    1, k - 1}]] > v2[mp2[{
    1, k - 1}]]){
    
		// cout<<"*2*"<<endl; 
			ans ++ ;  //去掉最后一个点 
		}
		
		if(v1[lca1(kk[1], mp1[{
    3, k}])] > v2[lca2(kk[1], mp2[{
    3, k}])]){
    
		// cout<<"*3*"<<endl;
			ans ++ ;  //去掉点2
		} 
		if(v1[lca1(kk[k], mp1[{
    1, k - 2}])] > v2[lca2(kk[k], mp2[{
    1, k - 2}])]){
    
		// cout<<"*4*"<<endl;
			ans ++ ;  //去掉点k-1 
		} 
		
		if(k >= 5){
    
			for(int i = 3; i <= k - 2; i ++ ){
      //枚举去掉的点 
				int l1 = 1, r1 = i - 1;
				int l2 = i + 1, r2 = k;
				int op1 = lca1(mp1[{
    l1, r1}], mp1[{
    l2, r2}]);
				int op2 = lca2(mp2[{
    l1, r1}], mp2[{
    l2, r2}]);
				if(v1[op1] > v2[op2]){
    
					ans ++ ;
				} 
			}			
		}		
	}
	
	cout<<ans<<endl;
	
	return 0;
}

C Concatenation

依旧是队友的牛逼思路，对任意两个字符串排序，如果ab<ba那就让a排在b的前面，排序之后直接输出即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+4;
string num[maxn];

bool com(string &s1,string &s2)
{
    
    return (s1 + s2 < s2 + s1);
}
int main()
{
    
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
    
		cin>>num[i];
	}
    
    sort(num, num+n, com);
    string res = "";
    
    for(int i=0;i<n;i++){
    
		res+=num[i];
	}
    cout<<res;
	return 0;
 } 

J Journey

赛后补的，不得不说这个题给的挺绕的，给定某个到达i点的四个点，刚开始一直在迷惑到底什么意思，理解题意理解了半天，不过好在最后理解了

#include<bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10, M = 2 * N;

struct Node{
    
	int u, v, w;
	bool operator < (const Node &t) const {
    //w代表遇到的红灯数，按照遇到的红灯数递减排序 
		return w > t.w;  //从大到小放进队列里就是按照从小到达排序，符合计算最短路的条件 
	}
};

int n, m;
map<int, bool> st[N];
priority_queue<Node>q;  //优先队列存储点和权值 
int cross[N][4];  //记录每个点四个方向的来路 
int s1, s2, t1, t2;

int get_f(int u, int v){
      //找到u->v路径的下一个右转方向 
	for(int i = 0;i < 4; i ++ ){
      //遍历四条到达v点的道路
		if(cross[v][i] == u){
      //找到u到v的道路
			return (i + 1) % 4;  //找到uv这条路的下一个右拐的方向 因规定的方向是逆时针，所以从v开始找u，右拐相当于反方向+1
		}
	}
	return -1;
}

int dijkstra(){
    
	q.push({
    s1, s2, 0});  //起点入队，在s1,s2这条路上 
	
	while(q.size()){
    
		auto [u, v, w] = q.top();
		q.pop();
		
		if(st[u][v]) continue;
		st[u][v] = true;
		
		if(u == t1 && v == t2) return w;  //找到了终点就返回红灯数 
		int dir = get_f(u, v);  //此时图上应该是走到v点，找到u->v的下一个右拐方向 
		for(int i = 0; i < 4; i ++ ){
    
			if(st[v][cross[v][i]]) continue;  //如果这个点已经入队 
			if(i == dir) q.push({
    v, cross[v][i], w});  //从v到达下一个点 
			else q.push({
    v, cross[v][i], w + 1});  //如果不是右拐方向，红灯数++ 
		}
	}
	return -1;
}

int main()
{
    
	cin>>n;
	for(int i = 1; i <= n; i ++ ){
    
		for(int j = 0; j < 4; j ++ ){
    
			cin>>cross[i][j];  //逆时针记录到达i点的四个点 红绿灯的j方向的是哪一个红绿灯
		}
	}
	cin>>s1>>s2>>t1>>t2;
	cout<<dijkstra()<<endl;
	return 0;
}