牛客春招刷题训练营 - 2025.5.28 题解

活动地址：牛客春招刷题训练营 - 编程打卡活动

Easy 小红浏览论坛

简要题意

给若干对 a b，问有多少对满足 。

Solution

直接判断即可。

Code

void R()
{
	int n,x,ans=0;
	cin>>n>>x;
	while (n--)
	{
		int a,b;
		cin>>a>>b;
		if (abs(a-b)>=x)
			ans++;
	}
	cout<<ans;
	return;
}

Medium 游游的排列构造

简要题意

构造一个恰好有 个前缀 位置的排列，且这 个位置互不相邻。

Solution

把前 大数升序放在前 个奇数位置，其余位置放剩下的数即可。

Code

void R()
{
	int n,k;
	cin>>n>>k;
	vector<int> a;
	for (int i=1,j=n-k+1;i<=n-k||j<=n;i++,j++)
	{
		if (j<=n) a.push_back(j);
		if (i<=n-k) a.push_back(i);
	}
	for (int i=0;i<n;i++)
		cout<<a[i]<<" \n"[i+1==n];
	return;
}

Hard 【模板】最小生成树

简要题意

求一张无向连通图的最小生成树。

Solution

Kruskal 算法的模板题。

Code

void R()
{
	int n,m;
	i64 sum=0;
	cin>>n>>m;
	DSU dsu(n);
	vector<int> ans;
	vector<array<int,4>> edges;
	for (int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		u--,v--;
		edges.push_back({w,u,v,i});
	}
	sort(edges.begin(),edges.end());
	for (auto [w,u,v,id]:edges)
	{
		if (dsu.merge(u,v))
		{
			sum+=w;
			ans.push_back(id);
		}
	}
	cout<<sum<<'\n';
	for (int i=0;i<ans.size();i++)
		cout<<ans[i]<<" \n"[i+1==ans.size()];
	return;
}