2022 年牛客多校第三场签到题题解

A Ancestor

题意：给出两棵 $nn$ 个节点的树 $A,BA,B$，$A,BA,B$ 树上每个节点均有一个权值，给出 $kk$ 个关键点的编号 $x_1,x_2,\cdots ,x_{k}x\_1,\; x\_2,\; \backslash cdots,\; x\_k$，问有多少种方案，使得去掉恰好一个关键点使得剩余关键点在树 $AA$ 上 lca 的权值大于树 $BB$ 上 lca 的权值。$1\le k\le n\le 1\times 10^{5}1\; \backslash leq\; k\; \backslash leq\; n\; \backslash leq\; 1\backslash times\; 10^5$。

解法：由于 LCA 是可合并但没有逆的，因而对于这种挖去一个的情况，可以考虑维护序列的 lca 前缀和 $pr{e}_{i}pre\_i$ 与 LCA 的后缀和 $su{f}_{i}suf\_i$。对于挖去 $jj$ 的情况就是 $\mathrm{l}\mathrm{c}\mathrm{a}(pr{e}_{j-1},su{f}_{j+1})\{\backslash rm\; lca\}(pre\_\{j-1\},\; suf\_\{j+1\})$。时间复杂度 $\mathcal{O}(n\log n)\backslash mathcal\; O(n\; \backslash log\; n)$。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=2e5+3;
struct hh{
	int to,nxt;
};
int n,k,nd[N];
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
struct tree{
	hh e[N<<1];int num,fir[N],val[N],dep[N],fa[N][20],lf[N],rf[N];
	IL void add(int x,int y){
		e[++num]=(hh){y,fir[x]},fir[x]=num;
	}
	void dfs(int u,int f){
		dep[u]=dep[f]+1,fa[u][0]=f;
		for(int i=0;fa[u][i];++i)
		  fa[u][i+1]=fa[fa[u][i]][i];
		for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
		  dfs(v,u);
	}
	IL int Lca(int x,int y){
		if(dep[x]<dep[y]) swap(x,y);
		for(int i=18;~i;--i)
		  if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
		if(x==y) return x;
		for(int i=18;~i;--i)
		  if(fa[x][i]^fa[y][i])
		    x=fa[x][i],y=fa[y][i];
		return fa[x][0];
	}
	IL void init(){
		lf[1]=nd[1];
		for(int i=2;i<=k;++i)
		  lf[i]=Lca(lf[i-1],nd[i]);
		rf[k]=nd[k];
		for(int i=k-1;i;--i)
		  rf[i]=Lca(rf[i+1],nd[i]);
	}
	IL int get(int n){
		if(n==1) return val[rf[2]];
		if(n==k) return val[lf[k-1]];
		return val[Lca(lf[n-1],rf[n+1])];
	}
}A,B;
void solve(){
	n=in(),k=in();int ans=0;
	for(int i=1;i<=k;++i) nd[i]=in();
	for(int i=1;i<=n;++i) A.val[i]=in();
	for(int i=2;i<=n;++i) A.add(in(),i);
	for(int i=1;i<=n;++i) B.val[i]=in();
	for(int i=2;i<=n;++i) B.add(in(),i);
	A.dfs(1,0),B.dfs(1,0),A.init(),B.init();
	for(int i=1;i<=k;++i) ans+=(A.get(i)>B.get(i));
	printf("%d\n",ans);
}
int main()
{
	solve();
    return 0;
}

C Concatenation

题意：给定 $nn$ 个仅由 0、1、2、3、4构成的字符串，问 $n!n!$ 种排列中字典序最小的那一个。$n\le 2\times 10^{6}n\; \backslash leq\; 2\backslash times\; 10^6$，$\sum \mathrm{\mid }{s}_i\mathrm{\mid }\le 2\times 10^7\backslash sum\; |s\_i|\backslash leq\; 2\backslash times\; 10^7$。

解法：本题暴力使用 sort可以通过，排序规则为 ，其中 $a,ba,b$ 均为字符串。

考虑如何 $\mathcal{O}(n)\backslash mathcal\; O(n)$ 的实现。首先将全部串插入 Trie 树，不妨设 ，对于 ，如果 $aa$ 不是 $bb$ 的前缀，则可以根据 $aa$ 和 $bb$ 在 Trie 树上的 dfs 序大小来判断。

若 $aa$ 是 $bb$ 的前缀，则需要比较依次比较 $b_{\mathrm{\mid }a\mathrm{\mid }+j}b\_\{|a|+j\}$ 与 $b_{j}b\_\{j\}$ 的大小关系。这个可以通过对每个串进行一次 Z 函数得到每个串后缀和原串的 $\mathrm{l}\mathrm{c}\mathrm{p}\backslash rm\; lcp$ 长度，从而实现 $\mathcal{O}(1)\backslash mathcal\; O(1)$ 的比较。因而一个前缀的比较等效于对应的未匹配后缀。由于 $bb$ 的前缀个数仅 $\mathcal{O}(\mathrm{\mid }b\mathrm{\mid })\backslash mathcal\; O(|b|)$ 个的，因而对这些前缀排序仅需 $\mathcal{O}(\mathrm{\mid }b\mathrm{\mid })\backslash mathcal\; O(|b|)$ 的时间。

J Journey

题意：有 $nn$ 个十字路口，左转、掉头、直行都要等红灯，右转不用。这些十字路口相互连接成一个图，问从某个十字路口的某个方向开始到目的地的目标方向需要等几次红绿灯。$n\le 5\times 10^{5}n\; \backslash leq\; 5\backslash times\; 10^5$。

解法：对于每个方向的道路看作一个点，边权为道路与道路之间的路口是否要等红绿灯，那么问题转化为边权仅有 $0,10,1$ 的图的单源最短路问题，01 bfs 或者 Dijkstra 即可。复杂度 $\mathcal{O}(n\log n)\backslash mathcal\; O(n\; \backslash log\; n)$ 或 $\mathcal{O}(n)\backslash mathcal\; O(n)$。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=5e5+3;
struct hh{
	int to,nxt,w;
}e[N<<4];
struct kk{
	int x,y;
}S,T;
int n,c[N][4],dis[N][4];
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL kk turn(int x,int y){
	int pos=0;
	for(int i=1;i<4;++i)
	  if(c[x][i]==y) pos=i;
	return (kk){x,pos};
}
deque<kk>q;
void bfs(){
	q.push_front(S);dis[S.x][S.y]=0;
	while(q.size()){
		kk u=q.front();q.pop_front();
		kk v=turn(c[u.x][u.y],u.x);
		int op=(v.y+1)%4;
		if(c[v.x][op]&&dis[v.x][op]>dis[u.x][u.y]){
			dis[v.x][op]=dis[u.x][u.y];
			q.push_front((kk){v.x,op});
		}
		for(int i=0;i<4;++i)
		  if(i^op&&c[v.x][i]&&dis[v.x][i]>dis[u.x][u.y]+1){
		  	dis[v.x][i]=dis[u.x][u.y]+1;
		  	q.push_back((kk){v.x,i});
		  }
	}
	if(dis[T.x][T.y]>1e9) printf("-1\n");
	else printf("%d\n",dis[T.x][T.y]);
}

void solve(){
	n=in();memset(dis,63,sizeof(dis));
	for(int i=1;i<=n;++i)
		for(int j=0;j<4;++j)
			c[i][j]=in();
	int x=in(),y=in();S=turn(x,y);
	x=in(),y=in();T=turn(x,y);
	bfs();
}
int main()
{
	solve();
    return 0;
}