C/C++教程

2022牛客暑假第三场C、A、J、H、F题

本文主要是介绍2022牛客暑假第三场C、A、J、H、F题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

咕咕咕了好久,因为H题去学了后缀自动机,顺手学了后缀数组,学了好久(其实主要还是因为懒)

C-Concatenation_"蔚来杯"2022牛客暑期多校训练营3 (nowcoder.com)

C题本意不是签到题,也刻意卡了log算法,但是卡得不够彻底,sort的cmp加个引用就过了。

数据量特别大,而且全是string,不可能把log卡得太死,猜也应该能莽掉。

正解trie树+扩展kmp(不会),想办法优化排序的比较。

莽过CODE:

bool cmp(string &a, string &b)
{
	string res1 = a + b;
	string res2 = b + a;
	if(res1 < res2) return true;
	else return false;
}

string ss[2000100];
int n;

int main()
{
	cin>>n;
	for(int i=0; i<n; i++) cin>>ss[i];
		
	sort(ss, ss+n, cmp);
	
	for(int i=0; i<n; i++) cout<<ss[i];
    return 0;
}

A-Ancestor_"蔚来杯"2022牛客暑期多校训练营3 (nowcoder.com)

这是第一道在赛场写出来的比较长代码(150行)的题目。

方法一:分类讨论,在比赛时上想出来的(其实是最笨的方法了感觉,害容易漏情况)

方法二:前后缀LCA

方法三:按照dfs序编号后,只有序相差最大的两个点会影响到LCA

分类讨论法CODE:

分类讨论注意到会改变lca的情况非常少,对于A树和B树都至多只有一个点。

因此思路是先判断是否去掉一个的点会使lca变化,如果会变化则搜索找到这个点,最后枚举删点的时候特判就可以了。

以下就是分类的方法。(图片来自网络,侵删)

const int N=1e5+5,M=2e5+5;
int e[M],ne[M];
int ah[N],bh[N],idx;
int n,k;
int x[N],inx[N];
int a[N],b[N];
int adep[N],bdep[N],fa[18][N],fb[18][N];
int anum[N],bnum[N];

void adde(int h[],int x,int y){
	e[idx]=y; ne[idx]=h[x]; h[x]=idx++;
}

void bfs(int h[],int dep[],int f[][N]){
	queue<int>q;
	dep[0]=0; dep[1]=1; f[0][1]=0;
	q.push(1);
	
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=h[u];~i;i=ne[i]){
			int v=e[i];
			if(dep[v]>dep[u]+1){
				dep[v]=dep[u]+1;
				f[0][v]=u;
				for(int j=1;j<=17;j++)f[j][v]=f[j-1][f[j-1][v]];
				q.push(v);
			}
		}
	}
}

int dfs(int h[],int num[],int u,int fa){
	num[u]=(inx[u]==1);
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		num[u]+=dfs(h,num,v,u);
	}
	return num[u];
}

int lca(int dep[],int f[][N],int a,int b){
	if(dep[a]<dep[b])swap(a,b);
	for(int j=17;j>=0;j--){
		if(dep[f[j][a]]>=dep[b])a=f[j][a];
	}
	if(a==b)return a;
	
	for(int j=17;j>=0;j--){
		if(f[j][a]==f[j][b])continue;
		a=f[j][a];
		b=f[j][b];
	}
	return f[0][a];
}

int dfs_find(int h[],int num[],int u,int fa){
	if(inx[u]==1)return u;
	
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		int tt=dfs_find(h,num,v,u);
		if(tt!=0)return tt;
	}
	return 0;
}

int find_point(int h[],int num[],int u){
	int cnt=0;
	for(int i=h[u];~i;i=ne[i]){
		if(num[e[i]])cnt++;
	}
	if(cnt>2)return -1;

	int dv=-1;
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(num[v]==1)dv=v;
	}

	if(dv==-1)return -1;
	else return dfs_find(h,num,dv,u);
}

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++){
		scanf("%d",&x[i]);
		inx[x[i]]=1;
	}
	
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int tt;
	memset(ah,-1,sizeof(ah));
	for(int i=1;i<n;i++){
		scanf("%d",&tt);
		adde(ah,tt,i+1);
	}
	
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	memset(bh,-1,sizeof(bh));
	for(int i=1;i<n;i++){
		scanf("%d",&tt);
		adde(bh,tt,i+1);
	}
	
	memset(adep,0x3f,sizeof(adep));
	memset(bdep,0x3f,sizeof(bdep));
	bfs(ah,adep,fa); bfs(bh,bdep,fb);
	dfs(ah,anum,1,0); dfs(bh,bnum,1,0);
	
	int alca=x[1]; int blca=x[1];
	for(int i=2;i<=k;i++){
		alca=lca(adep,fa,alca,x[i]);
		blca=lca(bdep,fb,blca,x[i]);
	}
	
	int ta,tb;
	if(inx[alca])ta=alca;
	else ta=find_point(ah,anum,alca);
	if(inx[blca])tb=blca;
	else tb=find_point(bh,bnum,blca);
	
	int ans=0;
	for(int i=1;i<=k;i++){
		int t1=-1,t2=-1;
		if(ta==x[i]){
			for(int j=1;j<=k;j++){
				if(i==j)continue;
				
				if(t1==-1)t1=x[j];
				else t1=lca(adep,fa,t1,x[j]);
			}
		}
		else t1=alca;
		if(tb==x[i]){
			for(int j=1;j<=k;j++){
				if(i==j)continue;
				
				if(t2==-1)t2=x[j];
				else t2=lca(bdep,fb,t2,x[j]);
			}			
		}
		else t2=blca;
		if(a[t1]>b[t2])ans++;
	}
	cout<<ans<<endl;
	return 0;
}

J-Journey_"蔚来杯"2022牛客暑期多校训练营3 (nowcoder.com)

这一题主要是建图有点麻烦,我们把每条路径看成一个点,用二元组\((x,i)\)来表示一条路径,其中x是十字路口,i是指向十字路口的方向,和题目输入对应。

using namespace std;

const int N=5e5+5,INF=0x3f3f3f3f;
typedef pair<int,int>PII;
typedef long long ll;
int n;
int node[N][4];
int dis[N][4],vis[N][4];
PII st,ed;

void _01bfs(PII st,PII ed){
	memset(dis,0x3f,sizeof(dis));
	deque<PII>q;
	q.push_front(st); dis[st.x][st.y]=0;
	
	while(!q.empty()){
		PII u=q.front();
		q.pop_front();
		
		if(vis[u.x][u.y])continue;
		vis[u.x][u.y]=1;
		
		for(int i=0;i<4;i++){//遍历的写法稍微有一点麻烦
			PII v;
			v.x=node[u.x][i]; int val;
			
			if(v.x==0)continue;

			for(int j=0;j<4;j++){
				if(node[v.x][j]==u.x)v.y=j;
			}
			
			if(i==(u.y+1)%4)val=0;
			else val=1;
			
			if(dis[v.x][v.y]>dis[u.x][u.y]+val){
				dis[v.x][v.y]=dis[u.x][u.y]+val;
				if(val==0)q.push_front(v);//套01bfs即可
				else q.push_back(v);
			}
		}
	}
}

int main(){
	scanf("%d",&n);
	int a,b,c,d;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		node[i][0]=a; node[i][1]=b;
		node[i][2]=c; node[i][3]=d;
	}
	scanf("%d%d%d%d",&st.y,&st.x,&ed.y,&ed.x);
    //把起点和终点转化成我们需要的形式
	for(int i=0;i<4;i++)if(node[st.x][i]==st.y){ st.y=i; break;}
	for(int i=0;i<4;i++)if(node[ed.x][i]==ed.y){ ed.y=i; break;}
	
	_01bfs(st,ed);
	
	if(dis[ed.x][ed.y]!=INF)cout<<dis[ed.x][ed.y]<<endl;
	else cout<<-1<<endl;
	return 0;
}

H-Hacker_"蔚来杯"2022牛客暑期多校训练营3 (nowcoder.com)

后缀自动机缝合线段树。

假设母串A和需要匹配的B串,问题可以转化成:求出\(B_i\)为后缀的与A能匹配最长子串的长度\(len\),然后求出\([i-len+1,i]\)这个区间的最大字段和。

问题的前一个部分可以用后缀自动机来求,后一个部分用线段树预处理。

const int N=1e5+5;
typedef long long ll;
typedef struct Segtree{
	int l,r;
	ll sum,ssm,ls,rs;
}Seg;
Seg tr[4*N];
int las=1,tot=1;
struct SAM{
	int fa,len;
	int ch[26];
}node[2*N];
int n,m,k;
char s[N];
int w[N];

void extend(int c){
	int p=las, np=las=++tot;
	node[np].len=node[p].len+1;
	for(;p && !node[p].ch[c];p=node[p].fa)node[p].ch[c]=np;
	if(!p)node[np].fa=1;
	else{
		int q=node[p].ch[c];
		if(node[q].len==node[p].len+1)node[np].fa=q;
		else{
			int nq=++tot;
			node[nq]=node[q], node[nq].len=node[p].len+1;
			node[q].fa=node[np].fa=nq;
			for(;p && node[p].ch[c]==q; p=node[p].fa)node[p].ch[c]=nq;
		}
	}
}

void pushup(Seg &u,Seg &l,Seg &r){
	u.sum=l.sum+r.sum;
	u.ssm=max(l.rs+r.ls,max(l.ssm,r.ssm));
	u.ls=max(l.ls,l.sum+r.ls);
	u.rs=max(r.rs,r.sum+l.rs);
}

void pushup(int u){
	pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}

void build(int u,int l,int r){
	if(l>=r)tr[u]={l,r,w[l],w[l],w[l],w[l]};
	else{
		tr[u]={l,r};
		int mid=(l+r)>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(u);
	}
}

Seg query(int u,int l,int r){
	if(tr[u].l>=l && tr[u].r<=r)return tr[u];
	int mid=(tr[u].l+tr[u].r)>>1;
	if(r<=mid)return query(u<<1,l,r);
	else if(l>mid)return query(u<<1|1,l,r);
	else{
		Seg lft=query(u<<1,l,r),rit=query(u<<1|1,l,r),sum;
		pushup(sum,lft,rit);
		return sum;
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&k);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)extend(s[i]-'a');
	for(int i=1;i<=m;i++)scanf("%d",&w[i]);
	build(1,1,m);

	ll ans;
	while(k--){
		ans=0;
		scanf("%s",s+1);
		int p=1, len=0;
		for(int i=1;s[i];i++){
			int c=s[i]-'a';
			while(p>1 && !node[p].ch[c])p=node[p].fa, len=node[p].len;
			if(node[p].ch[c])p=node[p].ch[c], len++;
			if(len>0)ans=max(ans,query(1,i-len+1,i).ssm);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

F-Fief_"蔚来杯"2022牛客暑期多校训练营3 (nowcoder.com)

点双连通分量+结论题。

一补题才发现自己根本没有学明白点双....

题目分析:如果原图不连通,一定不能满足条件;如果图只有一条链,那么只有选择两端的城市才可以满足条件;如果图是一棵树,无论怎么选择都没办法满足条件;如果图是孤立的环(只没有链延申出去的,可以是几个共用点大于1的环合在一起),无论怎么选择都可以满足条件。

于是可以想到用V-DCC来把环缩掉,最后判断图是否是一条链,如果是链,再对输入判断是否位于链的两个端点即可。

const int N=2e5+5,M=4e5+5;
int e[M],ne[M];
int h[N],idx;
int n,m,q;
int dfn[N],low[N],timestamp,root;
int stk[N],cut[N],dcc_cnt,top,num;
vector<int>dcc[N],to[N];
int d[N],id[N];
int block_cnt,link,cut_cnt;

void adde(int x,int y){
	e[idx]=y; ne[idx]=h[x]; h[x]=idx++;
}

void vdcc(int u){
	dfn[u]=low[u]=++timestamp;
	stk[++top]=u;
	
	if(u==root && h[u]==-1){
		dcc_cnt++;
		dcc[dcc_cnt].push_back(u);
		return;
	}
	
	int cnt=0;
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(!dfn[v]){
			vdcc(v);
			low[u]=min(low[u],low[v]);
			
			if(dfn[u]<=low[v]){
				cnt++;
				if(u!=root || cnt>1){
					cut_cnt++;//记录割点数量,如果割点数量为0说明是孤立环
					cut[u]=1;
				}
				
				dcc_cnt++;
				int y;
				do{
					y=stk[top--];
					dcc[dcc_cnt].push_back(y);
				}while(y!=v);
				dcc[dcc_cnt].push_back(u);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	int x,y;
	memset(h,-1,sizeof(h));
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		adde(x,y); adde(y,x);
	}
	
	for(root=1;root<=n;root++){
		if(!dfn[root]){
			vdcc(root);
			block_cnt++;//判断连通性的
		}
	}
	
	num=dcc_cnt; link=1;
	for(int i=1;i<=dcc_cnt;i++){
		for(int u:dcc[i]){
			if(cut[u]){
				if(!id[u])id[u]=++num;//割点需要重新编号
				to[id[u]].push_back(i);//给缩点后的新图建立边
				to[i].push_back(id[u]);
				d[id[u]]++; d[i]++;//记录节点度数
				if(d[id[u]]>=3 || d[i]>=3){ link=0; break;}
			}
			else id[u]=i;
		}
	}
	
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&x,&y);
		if(block_cnt>1 || link==0)printf("NO\n");//不连通或者不是链
		else if(cut_cnt==0)printf("YES\n");//孤立环
		else if(d[id[x]]==1 && d[id[y]]==1 && id[x]!=id[y])printf("YES\n");//满足条件
		else printf("NO\n");
	}
	return 0;
}
这篇关于2022牛客暑假第三场C、A、J、H、F题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!