考试策略

T1->T2->T5->T4->T3这样的吧,除了T3以外的题目都还是很水滴!只不过忽然对T4的32M空间表示疑惑了一下子而已。
经验和教训
这次考试没有什么特别的感悟,就是平时练好就行了,考试的时候发散思维,难题能想到就想到,不能想到就拿稳暴力分。
这次考试总之还是很水滴,boshi大佬早早做完题就开始写作业了QAQ

T1

期望得分:100 实际得分:100
题目描述
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。
规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。
数据输入:
第一行:三个整数n,m,p,(n小于等于5000,m小于等于5000,p小于等于5000),分别表示有n个人,m个亲戚关系,询问p对亲戚关系。
以下m行:每行两个数Mi,Mj,1<=Mi,Mj<=N,表示Ai和Bi具有亲戚关系。
接下来p行:每行两个数Pi,Pj,询问Pi和Pj是否具有亲戚关系。
解题思路
并查集裸题。
代码

T2

期望得分:100 实际得分:100
题目描述
众所周知,香港的黑社会组织猖獗,警方希望能摸清他们的内部构成情况,特派小生前往调查。经过长期的卧底,小生初步获得了一些资料:整个组织有n个人,任何两个认识的人不是朋友就是敌人,而且满足:①我朋友的朋友是我的朋友;②我敌人的敌人是我的朋友。所有是朋友的人组成一个团伙。现在,警方委派你协助调查,拥有关于这n个人的m条信息(即某两个人是朋友,或某两个人是敌人),请你计算出这个城市最多可能有多少个团伙。
数据范围:2≤N≤2000,1≤M≤5000。
输入数据:第一行包含一个整数N,第二行包含一个整数M,接下来M行描述M条信息,内容为以下两者之一:“F x y”表示x与y是朋友;“E x y”表示x与y是敌人(1≤x≤y≤N)。
输出数据:包含一个整数,即可能的最大团伙数。
题目分析
补集思想,每个人有两个并查集,一个代表其朋友集,一个代表其敌人集。如果两个人A和B是敌人,则把A的朋友集和B的敌人集合并,把B的敌人集和A的朋友集合并。如果两个人是朋友,就合并他们的朋友集。最后数一数一共有多少个集合即可。
代码

T3

期望得分:30 实际得分:55
错误原因:因为太蠢了没有想到怎么做,虽然与点连接坐标的并查集这样的思路擦边,但是没有细想。于是写了个离散化+哈希,暴力查找可以获得的新点,哈希确定能否添加。本来只想拿30分暴力分,结果因为哈希复杂度与数据强度有关,迷一般的拿了55...
题目描述
给定平面 n 个黑点,如果平面一个边平行于坐标轴的矩形 3 个角是黑色的那么就把那个矩形的第 4 个角改成黑色,最后平面上将会有多少个黑点
30%的数据 n小于等于100,100%的数据 n小于等于$2*10^5$
坐标绝对值小于等于1e9
题目分析
首先离散化。
然后对于每一个点,将其横坐标和纵坐标加入并查集,最后答案就是所有并查集中横坐标数量*纵坐标数量。
为什么呢?画个图搞一搞应该可以明白,每个并查集的横坐标和纵坐标搭配出的点都是黑的。
汗!这种题目讲不清楚啊!
代码

T4

期望得分:100 实际得分:100
题目描述
由于机器人工作速度惊人,基地很快竣工,科学家来到Smauel星上玩起了格字游戏,这是有两人队战的游戏:
两人轮流在一个n*n (n 小于等于1000)的棋盘上连边(每次只能连两条相邻的边),谁先连出一个连通的图形谁就赢了,此时游戏结束。
由于图形太大科学家下了很久以后不知道到底是谁赢了,于是他们又需要你的帮助。
现在给你他们连边的次数m(m小于等于100000)和位置,你需要判断游戏什么时候结束。
题目分析
一次连线相当于把两个格点加入一个并查集,如果要连的两个格点已经处于同一个并查集了,则连出了连通图形,游戏结束。
代码

T5

期望得分:100 实际得分:100
题目描述
众所周知,我们的lyp神犇外号叫Altman,的确,在另一个平行宇宙,lyp神犇就是一个——Altman。
有一天,lyp神犇遇到了另一个平行宇宙中的他,得知了在其他的宇宙中,Altman是存在的,那么,怪兽也是存在的咯。
作为一个有名的oier,lyp神犇想要统计一下各个宇宙中怪兽的战斗力,他发现,一些怪兽在不同的宇宙都出现过(!. !,难不成怪兽不穿越,算了,不管了),每一个Altman都提供给lyp一些信息,告诉他一个怪兽比另一个怪兽的战斗力大多少(这个数可以是负数)。
Altman神犇为了给你以表现机会,将这些信息都给你,并会时不时地问你两个怪兽之间谁更强。
假设Altman们提到了怪兽都按1~n编号。
Altman们的信息的格式是 X A B C
其中x固定为1,A,B是两个1~n的整数,表示怪兽编号,A怪兽的战斗力比B怪兽的战斗力大C(C为整数),保证信息之间不矛盾。
Lyp的询问的格式是:Y A B
Y 固定为2,A,B是怪兽编号,属于1~n,如果A比B 强,输出A;如果B比A强,输出B,如果无法判断或怪兽们一样强,输出0
题目分析
带权并查集,如果B的战斗力比A大3,那么就连成如图所示:

然后路径压缩,比较两个怪兽代表的节点距离根节点的长度即可判断谁比较强,不在同一并查集则无法判断。
代码