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

￡神魔★判官ぃ 2024-04-17 10:10 111阅读 0赞

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

![在这里插入图片描述][70cc977fd4e242d1b2ded47c6c3938da.png]

> 下面是PTA的OJ平台

[**PTA的OJ平台（点击我直跳）**][PTA_OJ]

#### 题目汇总 ####

*  题解
 *   *  L2-023 图着色问题
     *  L2-024 部落
     *  L2-025 分而治之
     *  L2-026 小字辈
 *  写在最后

## 题解 ##

### 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;
    		}
    	}
    }

## 写在最后 ##

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

???好啦，本文的内容就到此结束啦，我们下期再见哦！另外在祝各位小伙伴们要天天开心哦！  
???如果你觉得本文对你有帮助的话，还请不要吝惜您的三连哦！您的支持就是我创作的最大动力！！爱你们???  
![在这里插入图片描述][8089a73f942d4d32bd355d63c7696d74.jpeg_pic_center]

[CSDN]: https://blog.csdn.net/H1727548?type=lately
[PTA]: https://blog.csdn.net/h1727548/category_12186329.html?spm=1001.2014.3001.5482
[70cc977fd4e242d1b2ded47c6c3938da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/d7204ba1bcc24a7789cf880a10f7be18.png
[PTA_OJ]: https://pintia.cn/problem-sets/dashboard
[8089a73f942d4d32bd355d63c7696d74.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/cbd3404c55b4441bae81a5338cf68687.jpeg