Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

【3.16高一(第二学期)模拟测试】 T3,T4题解

c1714-gzr 2019-03-16 20:11:00 阅读数:173 评论数:0 点赞数:0 收藏数:0

看到这个标题我想你一定会想为什么小编只发T3,T4的题解,原因有很多:1)小编也不怎么会讲;2)小编搜遍各大OJ,都没有找到可以提交的地方;3)虽然给了测试数据,小编懒得一个一个试。如果你找到了测评网址,欢迎留言。

 

先说T3,题目如下:

C、团伙 
【问题描述】
    TEIAI 集团共有 n 名员工,编号为 1~n。由于长期的权力斗争,他们形成了
复杂的势力网络。对于任意两名员工,他们可能是朋友,可能是敌人,也可能没
什么关系。并且这种关系满足:(1)朋友的朋友是我的朋友;(2)敌人的敌
人也是我的朋友。为了抱团取暖,党同伐异,员工们形成了若干团伙,每个团伙
均满足:团伙内的所有人互为朋友,团伙外的每个人都不是朋友。
 集团的高层认为,这种斗争关系可以加速优胜劣汰的过程,从而促进集团的
盈利。他们通过暗访得到了这样的 m 条信息:每条信息包含 3 个值 p,x,y,
p=F 表示员工 x 与 y 是朋友,p=E 表示员工 x 与 y 是敌人。请你根据这 m 条信
息,判断这些员工最多可能形成多少个团伙?
【输入格式】
  第 1 行为 n 和 m,1<n<1000,1<=m<=5000;
  以下 m 行,每行为 pxy。
【输出格式】
  一个整数,表示这 n 个人最多可能有几个团伙。
【输入样例】 
  64
  E14
  F35
  F46
  E12
【输出样例】 
3
【样例说明】{1},{2,4,6},{3,5}

看起来这道题需要好好思索一番,此题一看就知道必须要用并查集(不会点这里)。首先,题目中出现了两种关系,分别是朋友关系和敌人关系,那么就要分类讨论了,先看朋友关系,这个好说,直接合并就可以了;那么敌人关系呢?根据敌人的敌人是朋友这个条件,只需要分别把敌人和另一个敌人的敌人合并即可。

代码如下:

 1 #include<iostream>
2 using namespace std;
3 int n,m,p,q,a[10000],ans=0,num[10000];char c,ch;
4 int find(int x)//并查集
5 {
6 if(x==a[x]) return x;
7 else return a[x]=find(a[x]);
8 }
9 int main()
10 {
11 //freopen("group.in","r",stdin);
12 //freopen("group.out","w",stdout);
13 cin>>n>>m;
14 for(int i=1;i<=n*2;i++) a[i]=i;//为了后续操作更方便,将1~n存为每一个人的祖先,n+1~n+n为1~n每个人的敌人,例如1和1+n是敌人关系
15 for(int i=1;i<=m;i++)
16 {
17 cin>>c;
18 cin>>p>>q;
19 if(c=='F') a[find(p)]=find(q);//朋友关系直接合并
20 else
21 {
22 a[find(p+n)]=find(q);//将敌人与敌人的敌人合并
23 a[find(q+n)]=find(p);//同上
24 }
25 }
26 for(int i=1;i<=n;i++)
27 if(a[i]==i) ans++;//判断有多少个祖先即可知道有多少个团伙
28 cout<<ans;
29 return 0;
30 }

T4,题目如下:

D、家谱 
【问题描述】 
给定一系列父子关系,求某些人的祖先。“祖先”指的是从该人开始,沿父
子关系向上追溯可以达到的辈分最大的人。
【输入格式】 
每行包含一个人名和一个标识符。标识符紧贴在名字的前面,不同标识符的
含义如下:(人名用 Name 指代)
#Name:从下一行开始,每一个以标识符+开头的人名都是 Name 的儿子,
直至遇到第一个不以+开头的人名;
+Name:上一个用#标识的人的儿子;
?Name:要求输出 Name 的祖先。
最后一行用一个字符$表示输入结束。
【输出格式】
按照输入文件的要求顺序,求出每一个用?标识的人的祖先,格式:本人的
名字+一个空格+祖先的名字+回车。
【输入样例】 
    #George
    +Rodney
    #Arthur
    +Gareth
    +Walter
    #Gareth
    +Edward
    ?Edward
    ?Walter
    ?Rodney
    ?Arthur
    $
【输出样例】 
    EdwardArthur
    WalterArthur
    RodneyGeorge
    ArthurArthur
【数据规模】 
 输入文件的总行数≤200,000。

这道题与之前T3一样,需要用到并查集,但是合并是一件很麻烦的事情,如果装换成序号来做就太麻烦了,还会出现各种不必要的麻烦。那么就要请出传奇的map了。

map是什么呢?用东西总得加头文件吧,要加上#include<map>才能用,map主要用来使两个元素发生联系,并且这两个元素可以是任意类型,这样数组下标就可以用string了。

代码如下:

 1 #include<iostream>
 2 #include<cstring>
 3 #include<map>
 4 using namespace std;
 5 map<string,string>a;//尖括号内的两种类型可以分别当成数组下标与数组值的类型 
 6 string c,s;char ch;
 7 string find(string x)//字符串+并查集 
 8 {
 9 if(a[x]==x) return x;
10 else return a[x]=find(a[x]);
11 }
12 int main()
13 {
14 for(;;)
15  {
16 cin>>ch;
17 cin>>c;
18 if(ch=='$') break;
19 else if(ch=='#')
20  {
21 s=c;
22 if(a[s]=="") a[s]=s;//如果s没有爹,那么就只能让s叫自己爹了 
23  }
24 else if(ch=='+') a[c]=s;
25 else cout<<c<<" "<<find(c)<<endl;
26  }
27 return 0;
28 }
版权声明
本文为[c1714-gzr]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/TFLS-gzr/p/10544118.html

支付宝红包,每日可领(支付宝免费1-2元支付红包)