考试策略

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 是否具有亲戚关系。
解题思路：
并查集裸题。
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,m,p;
int f[5005];
int find(int x){
    if(x==f[x])return x;
    f[x]=find(f[x]);return f[x];
}
int main()
{
    freopen("relation.in","r",stdin);
    freopen("relation.out","w",stdout);
    int x,y,i,r1,r2;
    n=read(),m=read(),p=read();
    for(i=1;i<=n;++i)f[i]=i;
    for(i=1;i<=m;++i){
        x=read(),y=read();
        r1=find(x),r2=find(y);
        if(r1!=r2)f[r1]=r2;
    }
    for(i=1;i<=p;++i){
        x=read(),y=read();
        if(find(x)==find(y))printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

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 的朋友集合并。如果两个人是朋友，就合并他们的朋友集。最后数一数一共有多少个集合即可。
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,m,ans;
int f[4005],vis[4005];
int find(int x){
    if(x==f[x])return x;
    f[x]=find(f[x]);return f[x];
}
int main()
{
    freopen("gangs.in","r",stdin);
    freopen("gangs.out","w",stdout);
    int i,r1,r2,x,y;char ch[5];
    n=read(),m=read();
    for(i=1;i<=n*2;++i)f[i]=i;
    for(i=1;i<=m;++i){
        scanf("%s",ch);x=read(),y=read();
        if(ch[0]=='E'){
            r1=find(x),r2=find(y+n);
            if(r1!=r2)f[r1]=r2;
            r1=find(x+n),r2=find(y);
            if(r1!=r2)f[r1]=r2;
        }
        else {
            r1=find(x),r2=find(y);
            if(r1!=r2)f[r1]=r2;
        }
    }
    for(i=1;i<=n;++i){
        r1=find(i);
        if(!vis[r1])vis[r1]=1,++ans;
    }
    printf("%d",ans);
    return 0;
}

T3

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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
#define LL long long
const int N=400005;
int f[N<<1],s1[N],s2[N];
int xx[N],yy[N],a[N],b[N];
int n,t1=1,t2=1;LL ans;
int find(int x){
    if(x==f[x])return x;
    f[x]=find(f[x]);return f[x];
}
void work(){
    int i,r1,r2;
    for(i=1;i<=t1;++i)f[i]=i,s1[i]=1;
    for(i=1;i<=t2;++i)f[i+t1]=i+t1,s2[i+t1]=1;
    for(i=1;i<=n;++i){
        xx[i]=lower_bound(a+1,a+1+t1,xx[i])-a;
        yy[i]=lower_bound(b+1,b+1+t2,yy[i])-b;
        r1=find(xx[i]),r2=find(yy[i]+t1);
        if(r1!=r2)f[r1]=r2,s1[r2]+=s1[r1],s2[r2]+=s2[r1],s1[r1]=0,s2[r1]=0;
    }
    for(i=1;i<=t1+t2;++i)
        if(find(i)==i)ans+=(LL)s1[i]*s2[i];
}
int main()
{
    freopen("filling.in","r",stdin);
    freopen("filling.out","w",stdout);
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%d%d",&xx[i],&yy[i]);
        a[i]=xx[i],b[i]=yy[i];
    }
    sort(a+1,a+1+n),sort(b+1,b+1+n);
    for(i=2;i<=n;++i)
        if(a[i]!=a[t1])a[++t1]=a[i];
    for(i=2;i<=n;++i)
        if(b[i]!=b[t2])b[++t2]=b[i];
    work();printf("%lld",ans);
    return 0;
}

T4

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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;
const int N=1000005;
int n,m;
int f[N];
int find(int x){
    if(f[x]==x)return x;
    f[x]=find(f[x]);return f[x];
}
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    int i,r1,r2,x,y,xx,yy;char ch[5];
    scanf("%d%d",&n,&m);
    for(i=1;i<=n*n;++i)f[i]=i;
    for(i=1;i<=m;++i){
        scanf("%d%d%s",&xx,&yy,ch);
        x=(xx-1)*n+yy;
        if(ch[0]=='R')y=x+1;
        else y=xx*n+yy;
        r1=find(x),r2=find(y);
        if(r1!=r2)f[r1]=r2;
        else {printf("%d",i);return 0;}
    }
    printf("-1");
    return 0;
}

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，那么就连成如图所示：

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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;
const int N=30005;
int n,m;
int f[N],d[N];
int find(int x){
    if(f[x]==x)return x;
    int t=f[x];
    f[x]=find(f[x]),d[x]+=d[t];
    return f[x];
}
int main()
{
    freopen("lyp.in","r",stdin);
    freopen("lyp.out","w",stdout);
    int i,bj,x,y,w,r1,r2;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)f[i]=i;
    for(i=1;i<=m;++i){
        scanf("%d",&bj);
        if(bj==1){
            scanf("%d%d%d",&x,&y,&w);
            r1=find(x),r2=find(y);
            if(r1!=r2)f[r1]=r2,d[r1]=d[y]-d[x]+w;
        }
        else {
            scanf("%d%d",&x,&y);
            r1=find(x),r2=find(y);
            if(r1!=r2)printf("0\n");
            else if(d[x]==d[y])printf("0\n");
            else if(d[x]>d[y])printf("%d\n",x);
            else if(d[x]<d[y])printf("%d\n",y);
        }
    }
    return 0;
}