团体程序设计天梯赛-练习集L2篇⑦-Toy模板网

这篇具有很好参考价值的文章主要介绍了团体程序设计天梯赛-练习集L2篇⑦。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🚀欢迎来到本文🚀
🍉个人简介：Hello大家好呀，我是陈童学，一个与你一样正在慢慢前行的普通人。
🏀个人主页：@陈童学哦`CSDN
💡所属专栏：PTA
🎁希望各位→点赞👍 + 收藏⭐️ + 留言📝
⛱️刷题的当下应是享受的！望与诸君共勉！🏄‍♂️

团体程序设计天梯赛-练习集L2篇⑦

下面是PTA的OJ平台

PTA的OJ平台（点击我直跳）

题解

L2-023 图着色问题

图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？

但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。

输入格式：
输入在第一行给出3个整数V（0<V≤500）、E（≥0）和K（0<K≤V），分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数N（≤20），是待检查的颜色分配方案的个数。随后N行，每行顺次给出V个顶点的颜色（第i个数字表示第i个顶点的颜色），数字间以空格分隔。题目保证给定的无向图是合法的（即不存在自回路和重边）。

输出格式：
对每种颜色分配方案，如果是图着色问题的一个解则输出Yes，否则输出No，每句占一行。

输入样例：
6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
4
1 2 3 3 1 2
4 5 6 6 4 5
1 2 3 4 5 6
2 3 4 2 3 4
输出样例：
Yes
Yes
No
No

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e8+10;
struct node{
	int u,v;
}p[N];
int main()
{
	int v,e,k;
	cin>>v>>e>>k;
	int a[501];
	set<int>st;
	for(int i=0;i<e;i++)
		cin>>p[i].u>>p[i].v;
	int q;
	cin>>q;
	while(q--)
	{
        
		for(int i=1;i<=v;i++)
		{
			cin>>a[i];
			st.insert(a[i]);
		}
		if(st.size()!=k)
		{
			cout<<"No"<<endl;
            st.clear();
			continue;
		}
		int flag=0;
		for(int i=0;i<e;i++)
		{
			if(a[p[i].u]==a[p[i].v])
			{
				flag=1;
				break;
			}
				
		}
		if(flag)
			cout<<"No"<<endl;
		else
			cout<<"Yes"<<endl;
		st.clear();
	}
}

L2-024 部落

在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。

输入格式：
输入在第一行给出一个正整数N（≤10
4
），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：

K P[1] P[2] ⋯ P[K]

其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过10
4
。

之后一行给出一个非负整数Q（≤10
4
），是查询次数。随后Q行，每行给出一对被查询的人的编号。

输出格式：
首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。

输入样例：
4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7
输出样例：
10 2
Y
N

AC代码：

#include<bits/stdc++.h>
using namespace std;
int fa[10005];
int find(int i)
{
	if(fa[i]==i)
		return i;
	else
	{
		fa[i]=find(fa[i]);
		return fa[i];
	}
}

int unio(int i,int j)
{
	int x=find(i);
	int y=find(j);
	fa[x]=y;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=10005;i++)
		fa[i]=i;
	set<int>st;
	for(int i=1;i<=n;i++)
	{
		int k,x,x1;
		cin>>k;
		cin>>x;
		st.insert(x);
		for(int j=1;j<k;j++)
		{
			cin>>x1;
			st.insert(x1);
			unio(x,x1);
			
		}
	}
	int ans=0;
	for(int i=1;i<=st.size();i++)
	{
		if(fa[i]==i)
			ans++;
	}
	cout<<st.size()<<" "<<ans<<endl;
	int m;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		if(find(a)==find(b))
			cout<<"Y"<<endl;
		else
			cout<<"N"<<endl;
	}
}

L2-025 分而治之

分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。

输入格式：
输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （≤ 100）和随后的 K 行方案，每行按以下格式给出：

Np v[1] v[2] … v[Np]
其中 Np 是该方案中计划攻下的城市数量，后面的系列 v[i] 是计划攻下的城市编号。

输出格式：
对每一套方案，如果可行就输出YES，否则输出NO。

输入样例：
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 10
2 4
5
4 10 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2
输出样例：
NO
YES
YES
NO
NO

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,k,dt[10010];
vector<int>v[10010];
bool isleagle(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<v[i].size();j++)
		{
			if(dt[i]==0&&dt[v[i][j]]==0)
				return false;
		} 
	}
	return true;
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	int t;
	scanf("%d",&t);
	for(int i=0;i<t;i++)
	{
		memset(dt,0,sizeof(dt));
		scanf("%d",&k);
		for(int j=0;j<k;j++)
		{
			scanf("%d",&a);
			dt[a]=1;
		}
		if(isleagle(n)==true)
			printf("YES\n");
		else
			printf("NO\n");
	}
}

L2-026 小字辈

本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

输入格式：
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。

输出格式：
首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。

输入样例：
9
2 6 5 5 -1 5 6 4 7
输出样例：
4
1 9

AC代码：

#include<bits/stdc++.h>
using namespace std;
int f[100001]={-1};
int h[100001];

int find(int x)
{
	if(f[x]==-1) 
		h[x]=1;
	else if(h[x]==0)
		h[x]=find(f[x])+1;
	return h[x];
}

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>f[i];
	for(int i=1;i<=n;i++)
		find(i);
	int maxn=0;
	for(int i=1;i<=n;i++)
	{
		if(h[i]>maxn)
			maxn=h[i];
	}
	cout<<maxn<<endl;
	bool flag=true;
	for(int i=1;i<=n;i++)
	{
		if(h[i]==maxn)
		{
			if(flag)
			{
				flag=false;
				cout<<i;
			}
			else
				cout<<" "<<i;
		}
	}
}

写在最后

🍉🍉🍉不必偏执于未知的真实，身处的当下即是意义和真实，爱才是解题的答案，也是刻画人生色彩的笔尖，耐心的走下去，总会遇到你爱的人和爱你的人。

🍁🍁🍁好啦，本文的内容就到此结束啦，我们下期再见哦！另外在祝各位小伙伴们要天天开心哦！
🍂🍂🍂如果你觉得本文对你有帮助的话，还请不要吝惜您的三连哦！您的支持就是我创作的最大动力！！爱你们💕💕💕
团体程序设计天梯赛-练习集L2篇⑦ 文章来源地址https://www.toymoban.com/news/detail-506645.html